\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{fancybox}
\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 December 9, 23:59.
\vspace{0.5em}
\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
Brightspace.
\begin{center}
\hfill\shadowbox{
\begin{minipage}{.90\linewidth}
{\textsf{Use the following format to name your file:
\[ {\tt LastName\_StudentId\_a4.pdf}
\]
}}
\end{minipage}
}
\end{center}
\item {\bf Late assignments will not be accepted. I will not reply to
emails of the type ``my internet connection broke down at
23:57'' or ``my scanner stopped working at 23:58'', or
``my dog ate my laptop charger''.}
\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{0.5em}
\begin{question}
Write your name and student number.
\end{question}
\begin{question}
Construct a Turing machine with one tape that gets as input an integer
$x \geq 0$ and returns as output the integer $2x$. 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 $2x$. The tape head is on the
{\bf leftmost} bit of $2x$ 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 two tapes that accepts the language
\[ \{ a^n b^n : n \geq 0 \} .
\]
\vspace{0.5em}
\noindent {\bf Start of the computation:} Tape~1 contains a string
$w$ in $\{a,b\}^*$, its head is on the {\bf leftmost} symbol of $w$
(or at an arbitrary position if $w = \epsilon$).
Tape~2 is empty (that is, it contains only $\Box$'s) and 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:} The computation terminates as
soon as the Turing machine enters the accept state or the reject state.
If the input string $w$ is of the form $a^n b^n$ for some $n \geq 0$,
the Turing machine must terminate in the accept state. Otherwise, the
Turing machine must terminate in the reject state.
\vspace{0.5em}
\noindent {\bf Running time:} On any input string $w$, the number of
steps made by the Turing machine must
be\footnote{The term ``$1+$'' is to deal with the case when
$w = \epsilon$.}
$O(1+|w|)$. (This can be achieved by using the second tape!)
\vspace{0.5em}
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}