The Halting problem for Turing machines which work on a tape of at most $k$ cells can be solved: There is a limited number of distinct configurations available, providing an upper bound of steps before nontermination is determined.

Now let us give each cell an exponent: It stores how often the symbol in the cell is to be repeated, i.e. we use a run-length encoding. The machine then works on this tape under preservation of the exponent.

The number of distinct values is still limited to $k$, but the effective tape length is no longer bounded. I'm fairly certain this class of Turing machines suffers from the Halting problem just like regular, unbounded machines do, but I'm looking for a concise proof.

$k$ can be assumed to be $\geq 7$.


Starting in configuration $x^3$ A $y^2$ $z^5$ with $\delta(A,y) = w,right,A$ and $\delta(A,z) = v,left,B$, execution will be:

  • $x^3$ A $y^2$ $z^5$
  • $x^3$ $w^1$ A $y^1$ $z^5$
  • $x^3$ $w^2$ A $z^5$
  • $x^3$ $w^1$ B $w^1$ $v^1$ $z^4$

In this example, the maximum number of cells used so far is 4 (or 5 if the head is seen as a splitting point), seen in the final step. The total effective tape length is $3+2+5=10$, but this number is not limited for our purposes.

Just for curiosity, to make the example machine nonhalting, replace $\delta(A,z) = v,right,A$ and add $\delta(A,\sqcup) = u,right,A$, and the machine will increase the exponent of $u$ indefinitely.

  • $\begingroup$ Thinking about it a bit more, it seems a basic approach might be to consider the exponent an encoded representation of an unrestricted tape, circumventing the length restriction. $\endgroup$ – mafu Sep 8 '16 at 22:32
  • 3
    $\begingroup$ You can probably simulate a counter machine with two counters using your model. $\endgroup$ – Yuval Filmus Sep 8 '16 at 22:53
  • $\begingroup$ What is the difference between this model and a turing machine with 2k cells, one of which contains values and the other contains run lengths? It seems to me that your exponential tape machine with length k must be able to do a subset of the things a normal turing machine with length 2k can do. $\endgroup$ – Cort Ammon Sep 9 '16 at 0:05
  • $\begingroup$ This is essentially an extension of a Linear Bounded Automaton. Since their acceptance problem is decidable whereas the general model isn't, then they aren't equivalent. $\endgroup$ – Ryan Sep 9 '16 at 0:50
  • $\begingroup$ @YuvalFilmus en.wikipedia.org/wiki/Counter_machine even contains a section `A Turing machine can be simulated by two stacks', which I'm having some trouble understanding yet, but might be an answer. $\endgroup$ – mafu Sep 10 '16 at 0:41

Your Answer

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

Browse other questions tagged or ask your own question.