The halting problem can be solved for a Turing machine with finite tape by a Turing machine with infinite tape. All the infinite Turing machine has to do is enumerate every possible state of the finite Turing machine (and there will be a finite, though very large, number of possible states) and mark which states have been visited by the Turing machine in the course of running a program. Eventually, one of two things will happen:
- The finite Turing machine will halt.
- The finite Turing machine will revisit a state. If it revisits a state, then you know there is an infinite loop, since the machine is deterministic, and the next state is therefore determined entirely by the previous state. If there are
n
states, the machine is guaranteed to revisit one of them on then+1
th step.