So I\'m reviewing my Computability notes for my final, and I understand how redu

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:

Take Turing machine M and string x as inputs.
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.
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.

Explanation / Answer

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 M1,M2, and L(M1)=L(M2), then M1?Undecidable<=>M2?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.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.