\documentclass{article}
\input{6045preamble}


\begin{document}
\handout{9}{Prof. Ron Rivest}{7 March 2002}{Jonathan
  Herzog}{Handout 9: Recitation Problems}


\begin{problem}
\textbf{Warm up:} Suppose $L_1$ and $L_2$ are decidable
languages. Which of the following are decidable?
\begin{itemize}
\item $L_1 \cup L_2$
\item $L_1 \cap L_2$
\item $L_1 \setminus L_2$
\item $\overline{L_2}$
\item $L_2^*$
\item $L_1 \circ L_2$
\end{itemize}
What if $L_1$ and $L_2$ are recognizable? Which of the above are
recognizable?
\end{problem}

\begin{problem}
  For the TM $M_1$ in exercise 3.4, give the sequence of configuration
  that $M_1$ enters into on the input strings:
  \begin{itemize}
  \item 0
  \item 00
  \item 000
  \end{itemize}
\end{problem}

\begin{problem}
  What can be said about the language $L(M)$ in each of the following
  cases?
  \begin{itemize}
  \item $M$ moves its head right on each move.
  \item There is some integer $n$ such that, no matter what its input
    is, $M$ never moves its head past square $n$.
  \item For at least one input string $x$, $M$ accepts before moving
    its head to the end of $x$.
  \item $M$ never changes any symbol on its tape.
  \end{itemize}
\end{problem}

\begin{problem}
  Show that a language is recognizable iff it is enumerable. (Yes, we
  did this in class.)
\end{problem}

\begin{problem}
  Show that a language is recognizable iff a non-deterministic Turing
  machine recognizes it.
\end{problem}
\end{document}

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