5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – cody Jan 25 '16 at 18:10
  • $\begingroup$ @cody , I meant a single sided tape.. $\endgroup$ – Dan D-man Feb 5 '16 at 14:47
3
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ It's unclear to me how your question answers the original question. Could you clarify? $\endgroup$ – cody Feb 5 '16 at 15:57
  • $\begingroup$ 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. $\endgroup$ – Denis Pankratov Feb 6 '16 at 18:54
  • $\begingroup$ I meant answer, sorry. Thanks for the clarification. $\endgroup$ – cody Feb 6 '16 at 19:33
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vonbrand Jan 24 '16 at 22:24
  • $\begingroup$ @vonbrand I would use the negative positions. $\endgroup$ – Yuval Filmus Jan 24 '16 at 22:25
  • $\begingroup$ That is cheating! $\endgroup$ – vonbrand Jan 24 '16 at 22:26
  • $\begingroup$ @vonbrand Why? Turing machines are usually defined on two-way infinite tapes. $\endgroup$ – Yuval Filmus Jan 24 '16 at 22:28
  • $\begingroup$ The definitions I've seen have one-way infinite tapes. $\endgroup$ – vonbrand Jan 24 '16 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.