Question

Recall the Post Correspondence Problem that we defined in Section 5.2 and its associated language PCP. Show that PCP is decidable relative to A_TM.

Short answer

The given statement is proved.

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 L and will reject or not halt on the input strings that doesn’t belong to language L.

Proof of the statement.

Post Corresponding Problem is an undecidable problem where we have two list A and B such that

$$\begin{gathered} A=\left\{a_1,a_2,a_3\dots ..a_n\right\}and \\ B=\left\{b_1,b_2,b_3\dots \dots b_n\right\} \end{gathered}$$

then there exist set of integers $I=\left\{i_1,i_2,i_3\dots \right\}$, such that:

$a_1,a_2,a_3\dots ..a_n=\left\{b_1,b_2,b_3\dots \dots b_n\right\}$

To find above relation, we try to find all possible combination of $I=\left\{i_1,i_2,i_3\dots \right\}$

To provePCP is decidable relative to A_TM, we will use contradict of this. Means, we will assume PCP is undecidable relative to A_TMbut our undecidable relative is not related to oracle.

Now we are clear we will first found a match that will find our Post Corresponding Problem.

Here it is sure that if Turing Machine is not related to concept of oracle then this will be undecidable rather than Post Corresponding Problem being decidable relative to A_TM . As A_TMis associated to concept of oracle.

This concludes that Post Corresponding Problem is decidable relative to A_TM.