Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

Question

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a match}\}.$$ $PCP$: The Post Correspondence Problem is to determine whether a collection of dominos has a match. PCP is undecidable

Show that there is an oracle Turing machine having an oracle for $E_{\text{TM}}$ which can be used to decide $PCP$. Show that there is an oracle Turing machine having an oracle for $PCP$ which can be used to decide $E_{\text{TM}}$.

1. $PCP$ is decidable relative to $E_{\text{TM}}$ Can we contrustruct reduction of $PCP$ to $E_{\text{TM}}$ like that?:

   T(Q) =

     if Q is an instance of the Post Correspondence Problem with a match
     then  P
     else reject
   

then we know that language of $T$ is empty exactly when $P$ is not an instance of the Post Correspondence Problem with a match

and then the decider for $PCP$ with access to oracle for $E_{\text{TM}}$ can look like that:

   Write T on the tape.
   Query oracle with contents of tape.
   Output the opposite of what the oracle outputs.

Am I completely wrong? Can somebody help me please? And also I have no idea how to do the opposite direction.

Answer 1

If you have an oracle for PCP, you can decide E_TM.

• On input $\langle M\rangle$, check that $\langle M\rangle$ is a well-formed Turing machine, otherwise reject.
• Given a machine $\langle M\rangle$, you can construct a Post correspondence problem $P_M$ such that $P_M$ has a match just if $M$ accepts a word. The details are similar to the proof on Wikipedia that PCP is undecideable: basically, $P_M$ simulates the operation of $M$. We give it enough dominos to represent any input, so that $P_M$ can simulate the operation of $M$ on any word, and will have a match if $M$ accepts any word.
• Therefore, having constructed $P_M$, query the oracle for PCP. If it accepts, then $M$ accepts some word—its language is nonempty and we reject. Otherwise, the oracle rejects $P_M$ because $M$ has an empty language— we accept.

If you have an oracle for E_TM, you can decide PCP.

• On input $\langle P\rangle$, check that $\langle P\rangle$ is a well-formed Post correspondence problem, otherwise reject.

• Given a PCP $\langle P\rangle$, you can build a nondeterministic Turing machine $M_P$. That machine erases its input. It then nondeterministically picks one of the dominos and writes it on the tape. It checks if the tape contains a PCP match. If so, it accepts. Otherwise, it nondeterministically picks another domino to append to the tape, and repeats. Note that if there's ever a match, the machine accepts. Otherwise, it runs forever, making longer and longer domino chains. Consequently, note that $M_P$ either always accepts (no matter what its input is) or always rejects, based on whether the PCP is solvable or not.

• Therefore, having constructed $\langle M_P\rangle$, query the oracle for E_TM. If the oracle accepts, it means that $M_P$ doesn't accept any words— $M_P$ loops forever because it can't find a PCP match. We reject. If the oracle rejects, $M_P$ accepts all inputs because it finds a PCP match— we accept.