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.
Please see Reiner Czerwinski's answer; that is a better answer than mine.
I will assume the problem is as follows: given inputs $x,n,T$, where $x$ is an input word, $T$ is a Turing machine, and $n$ is a positive integer, determine whether $T$ accepts $x$ using at most $n$ bits of memory.
If so, the problem is PSPACE-hard. In other words, any PSPACE problem can be reduced to this problem. Consider any PSPACE problem. Since it is in PSPACE, there must be a Turing machine $T$ that solves the problem in polynomial space. Let $p$ be the polynomial, so that $T$ takes space at most $p(|x|)$ on input $x$, where $|x|$ is the length of $x$. Modify $T$ so that if $T$ accepts, it halts, and if $T$ rejects, it enters an infinite loop. This gives us a new Turing machine $T'$; notice that the space usage of $T'$ is the same as $T$ (and $T'$ has at most one more state than $T$). Now, if you have an algorithm for your problem, then you can use it to test whether $x$ is a yes-instance for the problem by running your algorithm on the input $x,T',p(|x|)$. So, if you could solve the halting problem for polynomial-space Turing machines, you could solve every PSPACE problem.
The problem is in PSPACE if $n$ is represented in unary. You can test whether such a machine halts in space polynomial in $n$ and the length of $x,T$, 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; the rest follows by a pigeonhole argument.
If $n$ is represented in binary, then the problem is in EXPSPACE, by a similar argument.
The answer depends on the coding of $n$. The set $\{(M,x,1^n) | \text{ TM } M \text{ accepts }x \text{ within } n \text{ tape space } \}$ is $PSPACE$-complete. But the set $\{(M,x,n) | \text{ TM } M \text{ accepts }x \text{ within } n \text{ tape space } \}$ where $n$ is binary coded is $EXPSPACE$-complete.
