# Determine if a language is decidable

$$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)

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

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.