Question

Show that EQ_TM is recognizable by a Turing machine with an oracle for A_TM.

Short answer

The solution is given below.

Step-by-step solution

Turing Recognizable.

A language L is said to be Turing Recognizable if and only if there exist any Turing Machine (TM) which recognize it i.e. Turing Machine halt and accept strings belong to language and will reject or not halt on the input strings that doesn’t belong to language.

The proof is given below.

To prove above statement, we will assume an oracle Turing Machine T for A_TM.

Let us also consider two Turing Machines P and Q such that they will be decider for TM T and T will be decider for A_TM. This in turn makes A_TM as Turing Recognizable for EQ_TM.

We will express above sentence as follow:

We will construct Turing Machine P and Q from above expression:

T = on inputstring w will be made run on P

• Construct TM P and Q such that:

⇒P= on input: Accept in all input

⇒ Q= on input: w run on P

If accepts at w, then accept for any input

• Output: ‹P,Q›

Thus we can conclude that our assumed TM works as decider for A_TM and so A_TM will be decider for EQ_TM.

This proves that EQ_TM is recognizable by a Turing machine with an oracle for A_TM .