0
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • $\begingroup$ Where $n=|w|$ is the input length? $\endgroup$ – nir shahar Jun 9 '20 at 16:07
  • $\begingroup$ No, n is the number of bits of memory that the turing machine has access to. $\endgroup$ – blademan9999 Jun 9 '20 at 16:08
  • $\begingroup$ is it constant? $\endgroup$ – nir shahar Jun 9 '20 at 16:09
  • $\begingroup$ The machine cannot increase the amount of memory it has access to. $\endgroup$ – blademan9999 Jun 9 '20 at 16:10
  • $\begingroup$ If its constant, then its in $DTIME(O(1))$ $\endgroup$ – nir shahar Jun 9 '20 at 16:11
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.