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.

• Aryeh: Can you make this more formal, perhaps in the language of configurations? I don’t fully understand the question.
• holf: 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.
• exfret: @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.
• holf: 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.
• Aryeh: 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?

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

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

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.