1 of 3
Dan D-man
  • 514
  • 3
  • 9

Is this language computable?

Let $L_{NTF} = \{ <M> | $ 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 $<M>$ only after I will iterate over all possible $x\in \Sigma^* $, and since $\Sigma^*$ is $\aleph_0$ I will never accept a TM $<M>$. 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...

Dan D-man
  • 514
  • 3
  • 9