1
$\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.

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

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ The original problem was halting with constant space, but in the second part you transformed P to a program that uses polynomial space, therefore this would be a different halting problem. Unless I'm missing something? $\endgroup$
    – Ordoshsen
    Jan 6 at 13:44
  • $\begingroup$ @Ordoshsen, see edited answer for a more carefully stated reduction. I don't see an issue here, but I hope you'll let me know if you think I'm missing something. $\endgroup$
    – D.W.
    Jan 7 at 20:58
  • $\begingroup$ The reduction itself is sound, but you have reduced a constant-bound halting problem to PSPACE and then any PSPACE to a polynomial-space bound halting problem, which is a different problem than the original. Also I am not sure that you can actually do this reduction without some knowledge of the program you want to simulate, you need to know the polynom p which binds the space complexity, but I'm not sure you can compute it for any program? $\endgroup$
    – Ordoshsen
    Jan 8 at 22:49
  • $\begingroup$ You are right. That is a serious flaw in my answer. I'm sorry that I didn't understand the first time you left a comment -- thank you for your patience and willingness to continue to explain to me. I think I cannot delete this answer because it was accepted. What do you think would be best to do? $\endgroup$
    – D.W.
    Jan 9 at 0:03
  • $\begingroup$ I think that that the first part of the original answer was correct, that is deciding the halting problem for a turing machine with finite memory (where the finite amount of memory is known) is in PSPACE because of the reason you have provided (and now use as a proof of it being in EXPTIME). The original problem in question is in PSPACE. The problem with the PSPACE-hard reduction is that it is resulting in a different problem (polynomial-bound space vs constant space; therefore not directly answering the question). $\endgroup$
    – Ordoshsen
    Jan 10 at 12:07
1
$\begingroup$

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.

$\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.