snippetMinor
How to prove the following language is not in R
Viewed 0 times
thelanguagefollowingprovehownot
Problem
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.
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.
Solution
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}\}.
$$
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}\}.
$$
Context
StackExchange Computer Science Q#52217, answer score: 4
Revisions (0)
No revisions yet.