= 27d567bc2d48d9f40e9ccc20ea370b15)
gwern comments on What independence between ZFC and P vs NP would imply - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (62)
That would only work for some turing machines. Incidentally, it's perfectly possible to decide for particular finite turing machines whether it halts - basically either set a time-out equivalent to the Busy Beaver for that TM (and it either halts before, or blows the time-out in which case it never halts), or, IIRC, you can store every configuration of the tape it passes through and if it repeats any configuration, then it will not halt. Neither of these is especially useful.
Of course. I made no claim at having solved the halting problem. My response was specifically to,
There is nothing else that will reliably show this for all machines. There are absolutely things that will show this for some machines.