1
$\begingroup$

$$ L=\{<M>|M\ is\ a\ TM\ ;\ ∃x,|x|<5 ;\ M\ rejects\ x\} $$

How can i prove that $L \notin R$? I can't see how Rice's theorem be used here since the conditions are not met (The constrain $M\ rejects\ x$ is about the machine architecture and cannot be expreseed by a non-trivial language)

$\endgroup$
  • $\begingroup$ Try relating this to the halting problem. $\endgroup$ – Yuval Filmus May 15 '17 at 19:49
1
$\begingroup$

Actually "M rejects $x$" just means that $x \notin L(M)$, which is a statement about languages so Rice's theorem applies.


Use the decider for $L$ to solve the halting problem: On input $M$ and $w$, construct the machine $M_w$ that ignores its input and simulates $M$ on $w$. If the simulation halts, $M_w$ accepts. Otherwise, it doesn't.

So $M_w$ either accepts all strings (if $M$ halts on $w$) or no strings (if $M$ doesn't halt on $w$). You apply your decider to $M_w$. If $M_w$ accepts all strings, the decider will REJECT: the machine doesn't reject any short strings. If $M_w$ accepts no strings, the decider will ACCEPT: the machine rejects some short strings (in fact, all of them). We return the opposite answer, solving the halting problem.

It follows that a decider for $L$ can effectively solve the halting problem; therefore, such a decider does not exist.

$\endgroup$

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.