1
$\begingroup$

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

1 Answers 1

2

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

  • 4
    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.2012-12-05