4
$\begingroup$

Let $c\in \mathbb{N}$. Denote: $L _c= \{ \langle M \rangle \mid \exists _{U \subseteq \Sigma ^* }$ s.t. $|U| $ is infinite and for each $w\in U $ the TM $M$ accepts $w$ within no more than $c$ steps $\} $.

I would like to prove that for any given $c$ the language $L_c \notin R $.

I would like to find a language $L \notin R$ and find a reduction $L \leq L_c$, but Im having trouble as to which $L$ should I aim for.

I tried with $L_{acc}$, $L_{\Sigma^*}$ , but could not find what my reduction should be.

Im not necessarily looking for a complete solution, but even a hint from which language and how my reduction should look like (an idea behind the reduction) would be also great, sonce I feel Im at a loss here and dont know whre to start from.

$\endgroup$
4
$\begingroup$

Hint: This language is actually computable for every $c$. If $M$ terminates within $c$ steps, then it only gets to see at most $c$ symbols of its input, so in some sense its domain is finite.

There are some subtleties here. For example, it might be that there are also infinitely many inputs on which $M$ doesn't stop within $c$ steps. Perhaps it's better to first prove that the following language is computable for every $c$: $$ L'_c = \{ \langle M \rangle \mid \text{$M$ stops within $c$ steps on all inputs}\}. $$

$\endgroup$
  • $\begingroup$ You mean $L\in R$? I did consider this, but I need to run $M$ on an infinite number of inputs, and only after this infinite loop will end I can return a true answer (accept $<M>$). But this is an inifite loop, thus it will never end, so I will never return a true answer. This is why I don't see why the language (either $L_c$ or $L^{'}_c$) is computable. $\endgroup$ – Eric_ Jan 24 '16 at 16:39
  • 1
    $\begingroup$ @Eric_ I tried to indicate in my answer a different approach for deciding the language. Please spend some time dwelling on it. $\endgroup$ – Yuval Filmus Jan 24 '16 at 16:42
  • 3
    $\begingroup$ I see! You mean its enough to pass over all the words of length $\leq c$? And then if we take a longer word, we know our TM $M$ will look on at most the first $c$ charcaters of this input, so $M$ after $c$ steps will be in the same situation as it would have been on the prefix of length $c$ of this input. This is for $L^{'}_c$. And for $L_c$ since if we have even a single input of length $\leq c$ s.t. $M$ accepts this input after $\leq c $ steps, then it will accept an infinite number of inputs (inputs that include this accepting input as a prefix). Did I understand your idea correctly? $\endgroup$ – Eric_ Jan 24 '16 at 16:48
  • 1
    $\begingroup$ @Eric_ Yes, that's the idea. $\endgroup$ – Yuval Filmus Jan 24 '16 at 16:49

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.