Are all turing machines paths predictable?
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.


at the beginning it writes $\# \langle M_0 \rangle$ on the tape;
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)


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);
if it halts in $2^{|M_i|^i}$ space it returns back to $H$, otherwise it never visits $H$ again;
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).