Halting really undecidable for computers with limited memory?

Question

Turing proved that the halting problem is undecidable over Turing machines. However, real computers are not actually Turing-complete: They would be, if they had an infinite amount of memory.

Given the fact that computers have a finite amount of memory, hence are not quite Turning-complete, does the halting problem become decidable? My intuition tells me that yes, but the program that solves this restricted halting problem might have a time and space complexity exponential to the size of the memory of the targeted computer.

Answer 1

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:

1. The finite Turing machine will halt.
2. 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 the n+1th step.