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

Question

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

I'm not asking for free lunch, just a push in the right direction.

Answer 1

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