Question

Let is an oracle TM and ${M_{TM}}^A$accepts w}. Show that $A_{TM}\text{'}$is undecidable relative to $A_{TM}$.

Short answer

It is proved that ${A_{TM}}^{\text{'}}$ is undecidable relative to $A_{TM}$.

Step-by-step solution

Undecidability

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

Proving Undecidability

Use strategy $A_{TM}\text{'}$is undecidable relative to$A_{TM}$ by means of contradict that we will assume that A_TM’ decidable relative to$A_{TM}$ .

So if this is true, then there must be a Turing Machine N with oracle to$A_{TM}$ which acts as decider for $A_{TM}\text{'}$.

So we will design an oracle Turing Machine T as follows:

T=on input

• Run N on input
• If N accepts, T rejects

Else

N rejects, T accepts.

So T will accept only if M rejects.

This means, when the input is for TM T, then ${T_{TM}}^A$accepts only if T rejects .

But the above sentence is contradictory to our assumption that A_TM’ decidable relative to$A_{TM}$is wrong.

Thus we can say that, $A_{TM}\text{'}$is undecidable relative to $A_{TM}$.