# The set of Turing machines that recognize $\{00, 01\}$ is undecidable

$L =\big\{\langle T\rangle \mid T\text{ is a Turing machine that recognizes }\{00, 01\}\big\}$. Prove $L$ is undecidable.

I am really having difficulties even understanding the reduction to use here.

-

That follows from Rice's theorem:

Rice's Theorem.

Let S be a set of languages that is nontrivial, meaning

• there exists a Turing machine that recognizes a language in S
• there exists a Turing machine that recognizes a language not in S

Then, it is undecidable to determine whether the language decided by an arbitrary Turing machine lies in S.

[Copied from Wikipedia]

The language $\{00,01\}$ is nontrivial, thus $L$ is not decidable.

Hint: It is also easy to prove that directly, not using Rice's theorem. Let $M$ be a Turing machine. Consider Turing machine $M'$ defined as

if $x\in\{00,\,01\}$ then

• run $M$ on empty tape

• accept (if $M$ halts)

otherwise, reject

-
Unfortunately, I need to be more precise than this. It has to be constructed. We have to reduce some undecidable language to L to prove by contradiction that L is undecidable, which is where I am confused: what undecidable language do I use? –  user1405177 Dec 5 '12 at 1:59
Rice's theorem is precise. The proof is very rigorous. I added a hint how to prove that $L$ is not decidable directly without using Rice's theorem. (BTW, please, use tag “homework” if it's a homework problem.) –  Yury Dec 5 '12 at 2:08