\documentclass{article}

\input{6045preamble}

\begin{document}

\homework{5}{Prof. Ron Rivest}{Due: 9 April 2003}{}

\begin{problem}
Write a program (in a language other than C or C++) that prints itself
twice. (Please format your solution so that it is easy to read. 
You are allowed to have additional whitespace
in your program which is not present in the output of your program).
\end{problem}

\begin{problem}
Prove that there does not exist an infinite subset of $MIN_{TM}$
that is recognizable. 
\begin{eqnarray*}
MIN_{TM} &=& \{<M> | \mbox{There is no Turing Machine, } N 
                     \mbox{, such that } L(M) = L(N) \\
         & & \mbox{and the description of }N \mbox{ is shorter than
                   the description of }M \}
\end{eqnarray*}
\end{problem}

\begin{problem}
Prove the following generalization of Rice's Theorem:
If $P$ is a non-trivial
property of pairs of recognizable languages, then
$$
A_{p} = \{<M,N> | \mbox{M and N are Turing Machines and } P(M,N) = TRUE\}
$$
is undecidable. (Note: A property, $P$, is
\emph{non-trivial} if there exist Turing Machines $M_1, M_2, N_1$ and $N_2$
such that $P(M_1, N_1) = FALSE$ and $P(M_2, N_2) = TRUE$).
\end{problem}
\end{document}