\documentclass{article}

\input{6045preamble}
\usepackage{amssymb,amsmath,graphicx}

\begin{document}

\homework{8}{Prof. Nancy Lynch}{Due: April 9, 2007}{Elena Grigorescu}
\noindent
{\bf Reading:}  Handout 6 (from Hopcroft book); Sipser, Section 6.3



For the final two problems of this unit, you will have to consider
some new definitions that were not covered in class, but are
presented in Section 6.3 of Sipser's book.
Namely, an {\em Oracle Turing Machine\/} is a variant of a Turing
machine that has the ability to query an external source -- an
``oracle'' -- about membership of a string in some particular {\em oracle
language}.
A language is {\em decidable relative to\/} a language $L$ if it can
be decided by an oracle Turing machine that uses $L$ as its oracle set.


\begin{problem} 
(From Sipser Problem 6.19.) \\
Recall the Post Correspondence Problem discussed in class and in
Section 5.2 of Sipser.  Show that PCP is decidable relative to
$A_{TM}$, the acceptance problem for ordinary Turing machines.
\end{problem}


\begin{problem}
(From Sipser Exercise 6.4.) \\
Let $A'_{TM} = \{ \langle M, w \rangle|~M$ is an oracle Turing machine and
$M^{A_{TM}}$ accepts $w\}$.
Thus, $A'_{TM}$ can be thought of as the ``acceptance problem for oracle TMs
relative to the acceptance problem for ordinary TMs''.

Show that $A'_{TM}$ is not decidable relative to $A_{TM}$.  That is,
even with an oracle for the ordinary acceptance problem, the relative
version of the acceptance problem still cannot be decided!  

(Hint: Use a diagonalization argument like the one used to prove 
undecidability of $A_{TM}$.)

\end{problem}

\end{document}




