\documentclass{article}
\input{6045preamble}
\usepackage{fancyheadings}

\begin{document}
\handout{10}{Prof. Ron Rivest}{}{}{Handout 10: Quiz 2}

\Large
Write your full name on each page.
\normalsize

\newpage
\pagestyle{fancy}
\lhead[Name:\hspace{2in}]{Name:\hspace{2in}}
\cfoot[]{}
\begin{problem}
\textbf{Short Answer: (3 points each)}
\begin{enumerate}
  
\item Give a \emph{new} undecidable language, and a short proof that
  it is, in fact, undecidable. (A ``new'' language is one neither
  presented nor discussed in lecture, your recitation section, or the text.) 

\vspace{1in}


\item True or False: Every subset of every regular language is
  recognizable. Briefly explain your answer.

\vspace{1in}


\item True or False: The language $A = \cset{\rep{M}}{L(M) \mbox{ is
      recognizable or } \overline{L(M)} \mbox{ is recognizable }}$ is
  undecidable.  (Note that both $L(M)$ and $\overline{L(M)}$ can be
  recognizable (e.g. if $L(M)=\emptyset$).) Briefly explain your
  answer. 

\vspace{1in}


\item Consider the machine:
  \begin{quotation}
    $M = $ on input $w$
    \renewcommand{\theenumii}{\arabic{enumii}}
    \begin{enumerate}
    \item Obtain, by recursion theorem, $\rep{M}$
    \item Simulate $\rep{M}$ on $w$.
    \item If $\rep{M}$ accepts $w$, reject.
    \item If $\rep{M}$ rejects $w$, accept.
    \end{enumerate}
  \end{quotation}
Can such a machine exist? If so, what is its language? If not, why
not? (What contradiction results?)

\vspace{1in}

\item True or False: If $A$ and $B$ are languages such that $A \leq_m
  (A \cup  B)$ where $B$ is decidable, then $A$ is decidable. Briefly
  explain your answer. 

\end{enumerate}
\end{problem}


\newpage

\begin{problem}
  \textbf{(15 points)} Prove that there exists a Turing Machine $M$
  that accepts exactly one string: $\rep{M}$, the encoding of $M$. For
  the purposes of this problem, assume that each Turing machine $A$
  has a unique representation $\rep{A}$. (Hint: Recursion Theorem)
\end{problem}


\newpage


\begin{problem}
\textbf{(15 points)}
Let 
$$L = \cset{\rep{M_1, M_2}}{M_1 \mbox{ and }M_2 \mbox{ are
    Turing machines and } L(M_1) \subseteq L(M_2)}.$$
Show that $L$ is undecidable.
\end{problem}

\newpage


\begin{problem}
\textbf{(15 points)}
Let $A$ and $B$ be two disjoint languages. We say that a language $C$
\emph{separates} $A$ and $B$ if $A \subseteq C$ and $B \subseteq
\overline{C}$. Show that if $A$ and $B$ are disjoint languages and
both are co-recognizable, then $A$ and $B$ are separated by some
decidable language $C$. (Hint: consider running the enumerators for
$\overline{A}$ and $\overline{B}$ in parallel.) 
\end{problem}



\newpage


\begin{problem}
  \textbf{(15 points)} A \emph{right/reset machine} (RRM) is like an
  ordinary Turing machine (with one semi-infinite tape), except that
  at each step the head can either
  \begin{itemize}
  \item move right one square, or
  \item move back to the leftmost square (a ``reset'' of the head).
  \end{itemize}
This problem has three parts. In any part, you may assume the result
of previous parts:
\begin{enumerate}
\item Suppose that the tape alphabet of a RRM contains two types of
  characters: letters, and letters wearing a hat \^{\null}. Suppose
  that exactly one cell in the tape contains a letter with a hat. Show
  how to move the hat one cell right. (That is, keep the letters the
  same, moving only the hat.)
\item Suppose that exactly one cell in the tape contains a letter with
  a hat. Show how to move the hat one cell left. You may expand the
  tape alphabet to include a second kind of hat \~{\null} if you wish.
\item Prove that RRMs are as powerful as Turing Machines.
\end{enumerate}
\end{problem}

\end{document}




