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

\begin{document}
\homework{5}{Prof. Ron Rivest}{Due: 20 March 2002}{}

\begin{problem}
  \textbf{[Undecidability via counting argument]} Problem 4.21
\end{problem}

\begin{problem}
  \textbf{[Undecidability via reduction]} Problem 5.12 
\end{problem}

\begin{problem}
  \textbf{[Undecidability via reduction]} Consider a new model of a
  Turing machine which allows, in addition to the standard operations,
  a new operation: ``explode.'' When the Turing machine executes this
  operation it literally explodes, creating a huge mess.

  It would certainly be desirable to be able to test a Turing machine
  to see whether or not it would explode. Formulate this problem as a
  language, and show that it is undecidable. (Note: this is exactly
  the same as Problem 5.16, where ``explode'' is substituted for
  ``writes on the second tape.'')
\end{problem}

\begin{problem}
  \textbf{[Post correspondence problem I]} Problem 5.17. (Hint: for
  each tile, consider the difference between the number of
  characters on the top and the number of characters on the bottom.)
\end{problem}

\begin{problem}
  \textbf{[Post correspondence problem II]} Problem 5.18
\end{problem}


\end{document}

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