\documentclass{article}

\input{6045preamble}

\begin{document}

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

\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{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}


\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{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}


\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}

\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}


\end{document}