\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{fullpage}
\newcommand{\Halt}{\mathord{\it Halt}}
\newcommand{\HW}{\mathord{\it HW}}
\newcommand{\EMPTY}{\mathord{\it Empty}}
\newcommand{\USELESS}{\mathord{\it UselessState}}
\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}
\begin{document}
\begin{center} \Large\bf
COMP 3803 --- Assignment 4
\end{center}
\noindent {\bf Due:} Thursday April 4, before 11:55pm.
\vspace{0.5em}
\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
cuLearn.
\item Late assignments will not be accepted.
\item You are encouraged to collaborate on assignments, but at the level
of discussion only. When writing your solutions, you must do so
in your own words.
\item Past experience has shown conclusively that those who do not put
adequate effort into the assignments do not learn the material and
have a probability near 1 of doing poorly on the exams.
\item When writing your solutions, you must follow the guidelines below.
\begin{itemize}
\item You must justify your answers.
\item The answers should be concise, clear and neat.
\item When presenting proofs, every step should be justified.
\end{itemize}
\end{itemize}
\vspace{1em}
\begin{question}
Construct a Turing machine with one tape that gets as input an integer
$x \geq 0$ and returns as output the integer $x+1$. Integers are
represented in binary.
\vspace{0.5em}
\noindent {\bf Start of the computation:} The tape contains the binary
representation of the input $x$. The tape head is on the {\bf leftmost}
bit of $x$ and the Turing machine is in the start state.
\vspace{0.5em}
\noindent {\bf End of the computation:} The tape contains the binary
representation of the number $x+1$. The tape head is on the
{\bf leftmost} bit of $x+1$ and the Turing machine is in the final
state.
\vspace{0.5em}
The Turing machine in this question does not have an accept state
or a reject state; instead, it has a final state. As soon as this
final state is entered, the Turing machine terminates. At termination,
the contents of the tape is the output of the Turing machine.
Start by explaining your algorithm in plain English, then mention the
states that you are going to use, then explain the meaning of these
states, and finally give the list of instructions.
\end{question}
\begin{question}
Construct a Turing machine with three tapes that gets as input two
integers $x \geq 0$ and $y \geq 0$, and returns as output the number
$x+y$. Integers are represented in binary.
\vspace{0.5em}
\noindent {\bf Start of the computation:} Tape~1 contains the binary
representation of $x$, its head is on the {\bf rightmost} bit of $x$.
Tape~2 contains the binary representation of $y$, its head is on the
{\bf rightmost} bit of $y$. Tape~3 is empty (that is, it contains only
$\Box$'s), its head is at an arbitrary position. At the start, the
Turing machine is in the start state.
\vspace{0.5em}
\noindent {\bf End of the computation:} Tapes~1 and~2 are empty, and
tape~3 contains the binary representation of the number $x+y$.
The head of tape~3 is on the {\bf rightmost} bit of $x+y$.
The Turing machine is in the final state.
\vspace{0.5em}
The Turing machine in this question does not have an accept state
or a reject state; instead, it has a final state. As soon as this
final state is entered, the Turing machine terminates. At termination,
the contents of the tape is the output of the Turing machine.
Start by explaining your algorithm in plain English, then mention the
states that you are going to use, then explain the meaning of these
states, and finally give the list of instructions.
\end{question}
\begin{question}
In class, we have seen that the language
\[ \Halt = \{ \langle P,w \rangle :
\mbox{ $P$ is a Java program that terminates on
the binary input string $w$}\}
\]
is undecidable.
A Java program $P$ is called a \emph{Hello-World-program}, if the
following is true: When given the empty string $\epsilon$ as input,
$P$ can do whatever it wants, as long as it outputs the string
{\tt Hello World} and terminates. (We do not care what $P$ does when the
input string is non-empty.)
Consider the language
\[ \HW = \{ \langle P \rangle :
\mbox{ $P$ is a Hello-World-program}
\}.
\]
The questions below will lead you through a proof of the claim that
the language $\HW$ is undecidable.
\vspace{0.5em}
\noindent
{\bf (\arabic{ques}.1)} Consider a fixed Java program $P$ and a fixed
binary string $w$.
We write a new Java program $J_{Pw}$ which takes as input an
arbitrary binary string $x$. On such an input $x$, the Java program
$J_{Pw}$ does the following:
\begin{quote}
\begin{tabbing}
{\bf Algorithm} $J_{Pw}(x)$: \\
run $P$ on the input $w$; \\
print {\tt Hello World}
\end{tabbing}
\end{quote}
\begin{itemize}
\item Argue that $P$ terminates on input $w$ if and only if
$\langle J_{Pw} \rangle \in \HW$.
\end{itemize}
\vspace{0.5em}
\noindent
{\bf (\arabic{ques}.2)} The goal is to prove that the language
$\HW$ is undecidable. We will prove this by contradiction.
Thus, we assume that $H$ is a Java program that decides $\HW$.
Recall what this means:
\begin{itemize}
\item If $P$ is a Hello-World-program, then $H$, when given
$\langle P \rangle$ as input, will terminate in the accept state.
\item If $P$ is not a Hello-World-program, then $H$, when given
$\langle P \rangle$ as input, will terminate in the reject state.
\end{itemize}
We write a new Java program $H'$ which takes as input the binary encoding
$\langle P,w \rangle$ of an arbitrary Java program $P$ and an arbitrary
binary string $w$. On such an input $\langle P,w \rangle$, the Java
program $H'$ does the following:
\begin{quote}
\begin{tabbing}
{\bf Algorithm} $H'(\langle P,w \rangle)$: \\
construct the Java program $J_{Pw}$ described above; \\
run $H$ on the input $\langle J_{Pw} \rangle$; \\
{\bf if} $H$ terminates in the accept state \\
{\bf then} terminate in the accept state \\
{\bf else} terminate in the reject state \\
{\bf endif}
\end{tabbing}
\end{quote}
\vspace{0.5em}
Argue that the following are true:
\begin{itemize}
\item For any input $\langle P,w \rangle$, $H'$ terminates.
\item If $P$ terminates on input $w$, then $H'$ (when given
$\langle P,w \rangle$ as input), terminates in the accept state.
\item If $P$ does not terminate on input $w$, then $H'$ (when given
$\langle P,w \rangle$ as input), terminates in the reject state.
\end{itemize}
\vspace{0.5em}
\noindent
{\bf (\arabic{ques}.3)}
Now finish the proof by arguing that the language $\HW$ is undecidable.
\end{question}
\begin{question}
Consider the two languages
\[ \EMPTY = \{ \langle M \rangle : \mbox{ $M$ is a Turing machine for
which $L(M) = \emptyset$} \}
\]
and
\vspace{0.5em}
\begin{tabular}{rl}
$\USELESS= \{ \langle M,q \rangle$: &
$M$ is a Turing machine, $q$ is a state of $M$, \\
& for every input string $w$, the computation of $M$ on \\
& input $w$ never visits state $q \}$.
\end{tabular}
\vspace{0.5em}
\noindent
{\bf (\arabic{ques}.1)}
Use Rice's Theorem to show that $\EMPTY$ is undecidable.
\vspace{0.5em}
\noindent
{\bf (\arabic{ques}.2)}
Use {\bf (\arabic{ques}.1)} to show that $\USELESS$ is undecidable.
\end{question}
\end{document}