# Is the set of TMs that does not reach most cells to the right computable?

Let $L_{NTF} = \{ \langle M \rangle \mid$ for every $x\in\Sigma^*$ the machine $M$ does not reach the $|x|+10$'th cell during its calculation on $x$. $\}$.

I would like to prove or disprove $L_{NTF} \in RE$.

I know how to easily prove that $L_{NTF} \in Co$-$RE$, because it is enough to find one word $x$ such that $M$ will reach the $|x|+10$'th cell during its calculation on $x$. There is a finite number of configurations as long as the machine does not reach the $|x|+10$'th cell, so if I see a configuration is repeated I can deduce that the calculation will not end, but since I want it not to reach the $|x|+10$'th cell it is fine by me. That is to say, for a given input $x$ I can decide whether or not it reaches the $|x|+10$'th cell during $M$'s calculation on $x$.

So this tells me that $\overline{L_{NTF}}\in RE$, that is $L_{NTF}\in Co$-$RE$.

But this idea will not assist me in proving $L_{NTF}\in RE$ because I may accept a TM $\langle M\rangle$ only after I will iterate over all possible $x\in \Sigma^*$, and since $\Sigma^*$ is $\aleph_0$ I will never accept a TM $\langle M\rangle$. This is my intuition for why $L_{NTF} \notin RE$.

So for proving this I have 2 options:

1. Showing a reduction $L\leq L_{NTF}$ where $L\notin RE$. I've tried using $\overline{L_{acc}}, L_d$ and $L_{\Sigma^*}$, but could not find such a reduction that will hold. I'm not sure which language should i reduce from?
2. Finding a correspoinding property using Rice's theorem. I believe this idea will not work because the property is on the TM and not on the language.
3. An idea similiar to (1), just showing a reduction $L\leq L_{NTF}$ where $L\notin R$. This will also be sufficient because it will prove me that $L_{NTF}\notin R$, and since I know $L_{NTF}\in Co$-$RE$ having $L_{NTF}\in RE$ will lead to a contradiction, thus we can deduce $L_{NTF}\notin RE$.

I believe it is either by option (1) or by option (3), but I could not find a reduction that will prove this...

• As Yuval's answer implies and vonbrand notices, the answer differs in the case that the tape is 2 sided or not. Which case do you have in mind? – cody Jan 25 '16 at 18:10
• @cody , I meant a single sided tape.. – Dan D-man Feb 5 '16 at 14:47

## 2 Answers

Given a Turing Machine $M$ you can effectively construct $M'$ that does the following:

• Given $x$, $M'$ overwrites $x$ with $\langle M\rangle$ up to length $|x|$ or end of $\langle M\rangle$, whichever comes first. Writes blanks on the rest of $x$, and puts an end marker on cell $|x|+1$.
• $M'$ returns to the beginning of input and simulates $M$.
• If $M$ accesses end marker at any point, $M'$ enters an infinite loop without moving any further to the right.
• If $M$ accepts, $M'$ goes infinitely to the right.

Note this $M'$ has the following properties:

• If $M$ halts on $\langle M\rangle$ then $M'$ will access $|x| + 10$th cell for some large enough $x$.
• If $M$ does not halt on $\langle M\rangle$ then $M'$ will never access $|x|+10$th cell.
• It's unclear to me how your question answers the original question. Could you clarify? – cody Feb 5 '16 at 15:57
• What I've written is not a question. What I've shown is that $\overline{L_{NTF}}$ is not decidable (by the reduction from the halting problem). The OP also showed that it is RE. Therefore, its complement ($L_{NTF}$) is not RE. – Denis Pankratov Feb 6 '16 at 18:54
• I meant answer, sorry. Thanks for the clarification. – cody Feb 6 '16 at 19:33

Hints:

1. Show that every Turing machine can be simulated by another Turing machine that never reaches the $|x|+10$th cell.

2. If a Turing machine halts, you can modify it so that it does reach the $|x|+10$th cell.

3. Reduce the halting problem to your language.

• How would you do (1)? I don't see how to simulate e.g. a TM that first duplicates it's input in that space. This restriction is to essentially a linear bounded automaton, the languages they recognize are easily seen to be recursive. – vonbrand Jan 24 '16 at 22:24
• @vonbrand I would use the negative positions. – Yuval Filmus Jan 24 '16 at 22:25
• That is cheating! – vonbrand Jan 24 '16 at 22:26
• @vonbrand Why? Turing machines are usually defined on two-way infinite tapes. – Yuval Filmus Jan 24 '16 at 22:28
• The definitions I've seen have one-way infinite tapes. – vonbrand Jan 24 '16 at 22:32