Turing Machine That Accepts Machines With Undecidable Languages

Question

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

Answer 1

The language you are describing is called an "index-set", which means that it is accepting languages, rather than machines specifically. More formally, if we have two machines $M_1, M_2$, and $L(M_1) = L(M_2)$, then $M_1 \in Undecidable \iff M_2 \in Undecidable$.

There's a theorem called Rice's Theorem that says that index sets are always undecidable. The proof on the Wikipedia page shows how you can reduce the halting problem to any index set.

Answer 2

A machine that accepts an undecidable language is the universal Turing machine. It accepts $A_\text{TM}:=\{ \langle M,w\rangle \mid \text{TM $M$ accepts $w$}\}$ but this language is undecidable.

If you run into this trouble again, try to argue about the complement. If the complement is undecidable, then your language is also undecidable. You approach would then ask for a TM that accepts a decidable language as a submodule.

Answer 3

You must clarify the undecidable language term, Undecidable means not decidable, so Turing Recognizable (recursively enumerable) languages are undecidable and languages that are not Turing Recognizable are undecidable too.