Are all turing machines paths predictable?

Question

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.

Answer 1

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)

3. 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);

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

5. 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).

Answer 2

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.