\documentclass{article}
\input{6045preamble}
\newcommand{\spacechar}{\sqcup}
\newcommand{\length}[1]{\left \vert #1 \right \vert}

\begin{document}
\homework{6}{Prof. Ron Rivest}{Due: 10 April 2002}{}

\begin{problem}
  \begin{enumerate}
  \item Exercise 5.7
  \item Problem 5.11. Provide the reduction from $B$ to
    $\overline{B}$.
  \end{enumerate}
\end{problem}


\begin{problem}
  Recognizibility is linked with the idea of \emph{unbounded
    existential search}. Often an algorithm for accepting a
  recognizable language can be characterized in terms of searching for
  a \emph{witness} or \emph{proof} that a given input $x$ is in the
  language.
  
  A binary relation $R$ on strings is called decidable if the language
  $$\cset{\langle x,y\rangle}{R(x,y)}$$
  is decidable. Show that a language $A$ is recognizable if and only
  if there exists a decidable binary relation $R$ such that 
  $$A = \cset{x}{\exists y \mbox{ such that } R(x,y)}$$  
\end{problem}

\begin{problem}
  Formalize and prove the extension of Rice's Theorem about
  \emph{pairs} of recognizable languages: every non-trivial property
  of pairs of recognizable languages is undecidable.
\end{problem}

\begin{problem}
  Consider a one-tape Turing machine constrained so that it cannot
  overwrite the input portion of the tape. It may, however, write as
  much as it pleases on the blank portion to the right of the input
  string.

  \begin{enumerate}
  \item Prove that the language of such a Turing machine must be
    regular.
  \item Prove that despite this, the problem of determining if such a
    Turing machine recognizes the same language as a given DFA is
    undecidable.
  \end{enumerate}
\end{problem}


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
% LocalWords:  Undecidability
