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

\begin{document}
\handout{10a}{Prof. Ron Rivest}{}{}{Handout 10a: Alternate 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 True or false: The intersection of two decidable languages is
  decidable. Briefly state a reason for your answer.

\vspace{1in}

\item Suppose a \emph{randomized} TM $M$ had the transition function
  $$\delta : Q \times \Gamma \times \bit \rightarrow Q \times \Gamma
  \times \set{L,R}$$
  That is, it could flip a coin at every
  transition, and the transition depended on the current state, the
  contents of the current tape cell, and the coin flip. Now, instead
  of a machine simply accepting or not accepting a word $w$, it would
  have a probability of accepting. Is the language
  $$\cset{w}{\mbox{Probability that } M \mbox{ accepts is greater than
      } 0}$$
  recognizable, decidable, or neither? Briefly state a reason for your answer.

\vspace{1in}

\item We say that a Turing machine $M$ has \emph{maximal} length if no
  other Turing machine equivalent to $M$ has a larger description. Is
  the following language decidable, recognizable, or neither? Explain
  your answer.
  $$MAX_{TM} = \cset{\rep{M}}{M \mbox{ is maximal}}$$


\vspace{1in}

\item True or False: Every countably infinite language is
  recognizable. Briefly explain your answer.

\vspace{1in}

\item True or false: If $A \leq_m B$ and $B$ is regular, then $A$ is
  regular. Briefly state a reason for your answer.

\end{enumerate}
\end{problem}


\newpage

\begin{problem}
  \textbf{(15 points)} Prove that there exists a Turing Machine $M$
  that accepts only Turing machines with fewer states than $M$
  itself. (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) \cap L(M_2) = \emptyset}.$$
Show that $L$ is undecidable.
\end{problem}

\newpage


\begin{problem}
\textbf{(15 points)}
Show every infinite recognizable language has an infinite decidable
sub-language. (A language $L$ is a sublanguage of a language $L'$ if
$L \subseteq L'$.) Hint: recall that a language is decidable iff there
exists an enumerator that enumerates it in lexicographic order.
\end{problem}



\newpage


\begin{problem}
  \textbf{(15 points)} A \emph{queue} machine is like a Turing
  machine, except that it has a queue instead of a tape. It has a
  finite queue alphabet $\Gamma$ and a finite input alphabet $\Sigma
  \subseteq \Gamma$. If $x \in \Sigma^*$ is the input, then the
  machine starts in its start state with $x\$$
  in the queue (where
  $\$$
  is a special symbol in $\Gamma \setminus \Sigma$. The $\$$
  symbol is at the \emph{end} of the queue.) In each step, it removes
  a symbol from the front of the front of the queue. Based on that
  symbol and the current state, it pushes a string $z \in \Gamma^*$
  onto the back of the queue and enters a new state according to its
  transition function. It accepts by emptying the queue. 

  Show that a queue machine is as powerful as a Turing Machine.
\end{problem}

\end{document}




