Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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
3  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.