2
$\begingroup$

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) is undecidable }. (in words, a Turing machine that accepts encodings of machines that accept undecidable languages.)

I'm trying to reduce the accepting Turing machine (A TM) to Undecidable TM in the following manner:

  1. Take Turing machine M and string x as inputs.
  2. Create M' that works as follows: For input y, M' simulates M on x. If M accepts x, then M' acts on y as some Turing machine that accepts an undecidable language. Else, M rejects y.
  3. Pass M' to Undecidable TM. Iff Undecidable TM accepts M', then M must accept x, else M' does not accept an undecidable language.
  4. Thus, we can decide whether a machine M accepts input x.

The problem is that I cannot create a machine that accepts an undecidable language to put inside M' for this reduction. I have read my lecture notes and looked for advice on Google, but haven't made any headway. I'd appreciate it if someone has some insight on how to finish this proof or approach this another way. Thanks a lot.

$\endgroup$
3
  • 2
    $\begingroup$ Do you know Rice's theorem (en.m.wikipedia.org/wiki/Rice's_theorem)? $\endgroup$
    – PhoemueX
    Dec 14, 2014 at 6:27
  • $\begingroup$ @PhoemueX Haha, I do, and this example was actually in the notes about the theorem. Would you know of a way to construct the reduction for this problem? $\endgroup$
    – Impossibility
    Dec 14, 2014 at 7:00
  • 2
    $\begingroup$ One way would be to just specialize the proof of Rice's theorem (en.m.wikipedia.org/wiki/…) to this case. Rice's theorem is can also be proved using a reduction of the halting problem (see the link). $\endgroup$
    – PhoemueX
    Dec 14, 2014 at 8:43

1 Answer 1

Reset to default
0
$\begingroup$

What you need is a language that is undecidable but still semi-decidable.

The prototypical example of this is the set of indices of all Turing machines that halt on the empty tape.

It is easy enough to accept this language -- simply start simulating $T_y$ on a blank tape until if halts, and accept if it does.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .