54 ms·
Does the proof that the halting problem is not solvable actually make use of the unboundedness of the tape?
by tzs 7y ago
Does the proof that the halting problem is not solvable actually make use of the unboundedness of the tape?
- wolfgke 7y agoOf course it does (implicitly!). Otherwise the number of possible states of the Turing machine T that we want to check whether it halts or not is finite and we just have to "simulate" the program and see whether it terminates or it reaches again a state that it was already in.
- marcosdumay 7y agoHow would the "if this program halts then run forever, else halt" algorithm work on a real computer? I imagine it would fail with stack overflow.
- naasking 7y agoStandard proof is a diagonalization, which depends on infinite sequences. That said, the Halting problem on physical computers is still of extremely high computational complexity, which can be just as high a barrier as incomputability.