# Turing Machine That Accepts Machines With Undecidable Languages

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.

• Do you know Rice's theorem (en.m.wikipedia.org/wiki/Rice's_theorem)? Dec 14, 2014 at 6:27
• @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? Dec 14, 2014 at 7:00
• 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). Dec 14, 2014 at 8:43

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.