Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
What's the complexity class of determining the halting problem of a finite memory Turing machine? What is the computational complexity class of determining whether a machine halts on any input if it is allowed to access no more than $n$ bits of memory.
I know this problem is decidable because due to the limited memory, if it runs for longer then $2^n$ it must be caught in a loop.
The problem is PSPACE-complete.
The problem is in PSPACE. You can test whether such a machine halts in polynomial space, by running the Turing machine for $2^n |Q| n + 1$ steps, where $|Q|$ is the size of the finite control, and checking whether it halts. Why? Each configuration of the Turing machine is determined by the values on the tape, the state of the finite control, and the position of the head, so there are at most $2^n |Q| n$ such configurations.
Any PSPACE problem can be reduced to this problem. In particular, if you have a Turing machine that solves problem $P$ with polynomial space, then you modify $P$ to solve the problem, then if $P$ would accept, halt, and if $P$ would reject, enter an infinite loop. Now if you could solve the halting problem for polynomial-space Turing machines, you could solve $P$.
So, this completely characterizes the difficulty of the halting problem for polynomial-space Turing machines.
