I was recently studying partial solutions to the halting problem and came across the problem which I discuss below. In particular I was studying when it was computable to tell if a turing machine has a certain path in terms of its movement on the tape. A positive answer to the below would give a complete characterization of the paths for which the decision problem of whether a given turing machine has said path is computable.

Define the path of a turing machine to be the sequence of left and right movements it makes on an empty input. For example, this turing machine has a path which looks like LRRRLLRRRLLLRR...

Define a turing machine $M$ to be predictable if there exists another turing machine $N$ (not necessarily computable from $M$) with the following properties:

  1. $N$ has the same path as $M$. That is, when $M$ turns left, so does $N$. When $M$ turns right, so does $N$. Although this seems like a strong restriction at first, $N$ is not required to have the same states or even the same tape alphabet as $M$ so using both of these it may still be able to do some pretty complicated stuff relative to what $M$ does.
  2. There is a subset of $N$'s states, $Q'\subset Q$ such that whenever $N$'s head reads from a square for the last time, it must also be in a state in $Q'$. Also, we require $N$ to only enter a state from $Q'$ if it is reading from a square for the last time. Thus, in a way, $N$ is able to predict the path $M$ and $N$ are simultaneously taking.

My question is: Are all turing machines predictable?

Any help or pointers to reference materials would be appreciated, especially since the terminology here is my own and I don't know what to search to get information on this subject.

  • 1
    Can you make this more formal, perhaps in the language of configurations? I don’t fully understand the question. – Aryeh Nov 28 at 6:42
  • If you really want $Q' \subset Q$ and applying your definition formally, I do not think all machines are predictable. Consider a machine with states Left, Right on alphabets 0,1,2. It starts on state Right, on a tape full of 0. The transitions are : (Right, i): write i+1, move right, go to state Left. (Left, i): write i+1, move left, go to state Right. And (Right, 2) stops. I do not think this machine is predictable, though I may be mistaken. If it is, please explain me how $N$ works so it will give an example of what you are trying to prove. – holf Nov 28 at 8:01
  • @holf Any machine that halts is predictable. Simply add a state for each step taken in the computation and put the state in $Q'$ iff at the corresponding step we've entered a square for the last time. – exfret Nov 28 at 19:10
  • ok so $Q'$ is a subset of the states of $N$ and not the states of $M$. That is really not clear from your definition. – holf Nov 29 at 5:21
  • 1
    You really need to be careful with the quantifiers -- the question is still ill-posed, and I am going to recommend closing it in this form. Must the machine $N$ be able to predict $M$'s last-visit property on every square? A fixed, given square? Chosen by whom and at which point? – Aryeh Nov 29 at 8:25
up vote 3 down vote accepted

This is another way to prove that not all Turing machines are predictable.

First it's easy to note that:

  • all halting machines are predictable;
  • all machines that loop forever on a finite portion of the tape are predictable;
  • all machines that expand towards both sides of the tape are predictable ($N=M, Q' = \emptyset$).

The interesting case is when a machine runs forever and visits an infinite number of cells expanding only in one direction.

The following $M_{u}$ that expands rightwards is unpredictable.

  1. at the beginning it writes $\# \langle M_0 \rangle$ on the tape;

  2. if the rightmost part of the tape contains $...\#\langle M_i \rangle$ then it shift it on the right adding a $H:$ before it:

$$...H:\#\langle M_i \rangle$$

($...$ is the old untouched content of the tape)

  1. then it simulates $M_i$ on empty tape (using the rightmost part of the tape) and check if it halts in $2^{ |M_i|^i}$ space (number of cells);

  2. if it halts in $2^{|M_i|^i}$ space it returns back to $H$, otherwise it never visits $H$ again;

  3. at the end it clears the right part of the tape and leaves

$$...H:\# \langle M_{i+1} \rangle$$

and jump back to step 2.

Suppose that $M_u$ (possibly padded with some dummy states to increase its size) is predictable by $N_u$.

There exists $M_k$ that simulates the whole computation of $M_u$ up to $...\# \langle M_k \rangle$ (recursion theorem) and in parallel simulate $N_u$ using no more than $2^{2|M_{k-1}|^{k-1}}$ space. Indeed $N_u$ has the same path of $M_u$ by hypothesis, so after processing every $M_u(\#\langle M_i \rangle)$, $M_k$ can shift the whole tape to the leftmost cell and continue with $M_u(\#\langle M_{i+1} \rangle)$ (both $M_u$ and $N_u$ will never use space on the left of $\#$ again). Finally it can discover if $M_k$ (itself) halts in space $2^{|M_k|^k}$ immediately after step 2: it's enough to examine whether $N_u$ is in a $Q'$ state when the simulated $M_u$ writes the $H$ or not.

If it uses less than $2^{|M_k|^k}$ space then $M_k$ can loop right and never halt, otherwise it halts; this leads to a contradiction ($M_k$ would be able to diagonalize itself).

  • Pardon me if I'm being dense, but could you be a little more explicit on how to construct $B'$? – exfret Nov 29 at 23:53
  • @exfret: the problem is more tricky than I thought :-), I tried another approach. – Marzio De Biasi Nov 30 at 15:08

If I understood your question correctly, the answer is NO. Let $M$ be any TM and $w$ any input string, and define the TM $M'$ as follows: it reserves the leftmost square of the tape as "special" (e.g., by first moving all of its input 1 space over to the right) and then it interprets its input as an encoding of $\langle M,w \rangle$ and simulates $M$ on $w$. If $M$ accepts $w$, then $M'$ returns to that "special" leftmost square; otherwise it never returns. Since the general decision problem is reducible to the problem of knowing whether the machine is visiting a square for the last time, the latter is undecidable.

  • Edited my question to clarify that I was only looking at empty input but this does not answer my question regardless since my question isn’t to detect if a Turing machine has a certain path but whether another Turing machine with certain properties exists. – exfret Nov 29 at 4:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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