\documentclass{article}

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

\begin{document}

\homework{6}{Nancy Lynch}{Due: April 6, 2005}{Vinod Vaikuntanathan}
\noindent
{\bf Reading:}  Sipser, Sections 6.1, 6.3
\\
\\
\noindent
\begin{problem} 
(Counter Machine Decidability)
Show that the acceptance problem for 1-counter machines is decidable,
by describing a procedure that correctly decides it. \\
(Hint:  Develop a way of detecting situations in which the counter
machine must be in a loop.)
\end{problem}

For the final two problems, you will have to consider some new
definitions that were not covered in lecture, 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.

\bigskip
\noindent
\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}

\noindent
\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}