<p>This is another way to prove that not all Turing machines are predictable.</p>

<p>First it's easy to note that:</p>

<ul>
<li>all halting machines are predictable; </li>
<li>all machines that loop forever on a finite portion of the tape are predictable;</li>
<li>all machines that expand towards both sides of the tape are predictable (<span class="math-container">$N=M, Q' = \emptyset$</span>).</li>
</ul>

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

<p>The following <span class="math-container">$M_{u}$</span> that expands rightwards is unpredictable.</p>

<ol>
<li><p>at the beginning it writes <span class="math-container">$\# \langle M_0 \rangle$</span> on the tape;</p></li>
<li><p>if the rightmost part of the tape contains  <span class="math-container">$...\#\langle M_i \rangle$</span> then it shift it on the right adding a <span class="math-container">$H:$</span> before it:</p></li>
</ol>

<p><span class="math-container">$$...H:\#\langle M_i \rangle$$</span></p>

<p>(<span class="math-container">$...$</span> is the old untouched content of the tape)</p>

<ol start="3">
<li><p>then it simulates <span class="math-container">$M_i$</span> on empty tape (using the rightmost part of the tape) and check if it halts in <span class="math-container">$2^{ |M_i|^i}$</span> space (number of cells);</p></li>
<li><p>if it halts in <span class="math-container">$2^{|M_i|^i}$</span> space it returns back to <span class="math-container">$H$</span>, otherwise it never visits <span class="math-container">$H$</span> again;</p></li>
<li><p>at the end it clears the right part of the tape and leaves </p></li>
</ol>

<p><span class="math-container">$$...H:\# \langle M_{i+1} \rangle$$</span></p>

<p>and jump back to step 2.</p>

<p>Suppose that <span class="math-container">$M_u$</span> (possibly padded with some dummy states to increase its size) is predictable by <span class="math-container">$N_u$</span>.</p>

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

<p>If it uses less than <span class="math-container">$2^{|M_k|^k}$</span> space then <span class="math-container">$M_k$</span> can loop right and never halt, otherwise it halts; this leads to a contradiction (<span class="math-container">$M_k$</span> would be able to diagonalize itself).</p>

CC BY-SA 4.0
2018-11-29T23:53:12.867Z
Pardon me if I'm being dense, but could you be a little more explicit on how to construct $B'$?
exfret
CC BY-SA 4.0
2018-11-30T15:08:17.893Z
@exfret: the problem is more tricky than I thought :-), I tried another approach.
Marzio De Biasi
CC BY-SA 4.0
2018-11-29T21:33:08.303Z
2018-12-03T17:52:26.087Z
2018-12-03T17:52:26.087Z
Marzio De Biasi
<p>If I understood your question correctly, the answer is NO. Let <span class="math-container">$M$</span> be any TM and <span class="math-container">$w$</span> any input string, and define the TM <span class="math-container">$M'$</span> 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 <span class="math-container">$\langle M,w \rangle$</span> and simulates <span class="math-container">$M$</span> on <span class="math-container">$w$</span>. If <span class="math-container">$M$</span> accepts <span class="math-container">$w$</span>, then <span class="math-container">$M'$</span> 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.</p>

CC BY-SA 4.0
2018-11-29T04:41:40.750Z
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
CC BY-SA 4.0
2018-11-28T10:20:25.297Z
2018-11-28T14:05:30.740Z
2018-11-28T14:05:30.740Z
Aryeh
<p>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.</p>

<p>Define the <em>path</em> of a turing machine to be the sequence of left and right movements it makes <strong>on an empty input</strong>. For example, <a href="http://morphett.info/turing/turing.html?fc0ca5b8a7562800f8bc21ec1f9fcfb9" rel="noreferrer">this</a> turing machine has a path which looks like LRRRLLRRRLLLRR...</p>

<p>Define a turing machine <span class="math-container">$M$</span> to be <em>predictable</em> if there exists another turing machine <span class="math-container">$N$</span> (not necessarily computable from <span class="math-container">$M$</span>) with the following properties:</p>

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

<p>My question is: Are all turing machines predictable?</p>

<p>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.</p>

CC BY-SA 4.0
2018-11-28T06:42:22.250Z
Can you make this more formal, perhaps in the language of configurations? I don’t fully understand the question.
Aryeh
CC BY-SA 4.0
2018-11-28T08:01:57.983Z
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
CC BY-SA 4.0
2018-11-28T19:10:36.623Z
@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
CC BY-SA 4.0
2018-11-29T05:21:25.897Z
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
CC BY-SA 4.0
2018-11-29T05:30:47.250Z
@holf Okay I clarified it again
exfret
CC BY-SA 4.0
2018-11-29T08:25:19.930Z
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
CC BY-SA 4.0
2018-11-29T19:40:11.287Z
@Aryeh Checking the last-visit property on only one square is easy - either you visit that square infinitely often or there is a finite time step $t$ at which you visit it for the last time and you can add a new state for each natural less than or equal to $t$ with a transition from the $i^{th}$ new state to the ${i+1}^{th}$ new state that makes the new machine print and move the same way as $M$, then mark the $t^{th}$ new state as distinguished and have a transition from it to the state that $M$ would be in after $t+1$ steps normally.
exfret
CC BY-SA 4.0
2018-11-29T19:43:00.853Z
Regardless, I have rewritten my whole question in the hopes that I will get more informative feedback.
exfret
CC BY-SA 4.0
2018-11-30T13:48:53.570Z
OK, I understand the question now -- and it's a good one!
Aryeh
<automata-theory><turing-machines><halting-problem>
Are all turing machines paths predictable?
exfret
# Are all turing machines paths predictable?

(Asked by: username_0 on 2018-11-28)

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](http://morphett.info/turing/turing.html?fc0ca5b8a7562800f8bc21ec1f9fcfb9) 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.

**Tags:** automata-theory, turing-machines, halting-problem

> **Comments:**
> **username_1**: Can you make this more formal, perhaps in the language of configurations? I don’t fully understand the question.  
> **username_2**: 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.  
> **username_0**: @username_2 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.  
> **username_2**: 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.  
> **username_0**: @username_2 Okay I clarified it again  
> **username_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?  
> **username_0**: @username_1 Checking the last-visit property on only one square is easy - either you visit that square infinitely often or there is a finite time step $t$ at which you visit it for the last time and you can add a new state for each natural less than or equal to $t$ with a transition from the $i^{th}$ new state to the ${i+1}^{th}$ new state that makes the new machine print and move the same way as $M$, then mark the $t^{th}$ new state as distinguished and have a transition from it to the state that $M$ would be in after $t+1$ steps normally.  
> **username_0**: Regardless, I have rewritten my whole question in the hopes that I will get more informative feedback.  
> **username_1**: OK, I understand the question now -- and it's a good one!  

---

## 2 answers

### Answer by username_3 on 2018-11-29. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: Pardon me if I'm being dense, but could you be a little more explicit on how to construct $B'$?  
> **username_3**: @username_0: the problem is more tricky than I thought :-), I tried another approach.  

---

### Answer by username_1 on 2018-11-28. Score: 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.

> **Comments:**
> **username_0**: 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.  

---

