4 ms·
Of 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
by wolfgke 7y ago
Of 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.