# Are all turing machines paths predictable?

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.

• Can you make this more formal, perhaps in the language of configurations? I don’t fully understand the question. Nov 28 '18 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 '18 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. Nov 28 '18 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 '18 at 5:21
• 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? Nov 29 '18 at 8:25

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'$? Nov 29 '18 at 23:53
• @exfret: the problem is more tricky than I thought :-), I tried another approach. Nov 30 '18 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. Nov 29 '18 at 4:41