\documentclass{article}[11pt]
\usepackage{epsfig}


\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}

\begin{document}

\centerline{CSCI 2400 -- Models of Computation, Section 3}
\vspace{0.5cm}
\centerline{\Large Homework 9}
\vspace{0.5cm}
\centerline{Return by: Friday, December 8} 

\vspace{0.5cm}
\noindent
{\bf 1.}
Prove that the following problem is undecidable.
Given any Turing machine $M$, a symbol $a$, 
and string $w$, determine whether or not the symbol $a$
is ever written on the tape when $M$ is applied to input $w$.
(Hint: reduce the halting problem to this problem.)

\vspace{0.5cm}
\noindent
{\bf 2.}
Prove that the following problem is undecidable.
Determine whether or not
an arbitrary Turing machine halts on all input.
(Hint: reduce the halting problem to this problem.)

\vspace{0.5cm}
\noindent
{\bf 3.}
Let $b(n)$ be the maximum number of head moves
made by any $n$-state Turing machine that halts
when started with a blank tape.
Show that $b(n)$ is not computable.
(Hint: look at Example 12.3, page 319.) 

\vspace{0.5cm}
\noindent
{\bf 4.}
Show that the following problem is undecidable.
For two recursively enumerable languages $L_1$ and $L_2$,
determine whether $L_1 \subseteq L_2$.
(Hint: use the result of Theorem 12.3, page 322.)

\vspace{0.5cm}
\noindent
{\bf 5.}
Let $A = 001, 0011, 11, 101$ 
and $B = 01, 111, 111,010$.

(a) Does the pair $A,B$ have a PC-solution?

(b) Does it have an MPC-solution?

\end{document}








































































