\documentclass[12pt]{cas-handout}
\usepackage{multicol,fullpage,xspace}
\usepackage{paralist}

\newtheorem{theorem}{Theorem}
\newtheorem{condition}{Condition}

\newcommand{\BAR}{\ \ |\ \ }
\newcommand{\TM}{\mathsf{TM}}
\anumber{12}
\title{(Un)decidability}
\duedate{Wednesday, December 7}

\begin{document}
\maketitle 

\begin{compactitem}
  \item Emails about this assignment should be directed to
    \helpalias.
  \item The usual collaboration rules apply. You may \emph{discuss} an
    exercise with any other student(s) currently taking CS 81 as long as:
    \begin{compactitem}
      \item You contribute equally;
      \item You come away from this discussion only with
        \emph{understanding in your head} --- no written materials or
        computer notes may be retained;
      \item Your submission is authored solely by you, on a separate
        occasion.
   \end{compactitem}
  \item You should refer only to materials from this semester of CS 81 (lecture
   notes, handouts, textbooks, grutors, profs, etc.).
 \item Bring a writeup/printout to class on the due date. Illegible answers
    will get no credit.
 \item Make sure your submission includes your name!

\end{compactitem}
\smallskip
\mbox{}
\hrule

\noindent

\begin{enumerate}
\item Review Chapter~21 of Rich, paying particular attention
  to the examples.
  Come up with (at least) two questions about the reading
  where you're not sure of the answer.  These may relate to points
  where the book is confusing, or simply to some related question or
  conjecture that occurs to you while doing the reading.

\newcommand{\ADD}{\ensuremath{\mathit{ADD}}\xspace}
\newcommand{\ADDERS}{\ensuremath{\mathit{ADDERS}}\xspace}

\item Consider the following languages (where $M$ ranges over
  TMs). Are they semidecidable?  Are they decidable?  Prove each answer.
\[
\begin{array}{lcl}
L_1 &=& \{\ \langle M\rangle \BAR M \mbox{\ accepts\ at\ least\ 999\
strings}\ \}\\
L_2 &=& \{\ \langle M, w\rangle \BAR M \mbox{\ never moves right twice
  in a row while running on input $w$}\ \}\\
L_3 &=& \{\ \langle M\rangle \BAR M\mbox{'s program includes a transition that writes
  \texttt{a} on the tape}\ \}\\
L_4 &=& \{\ \langle M\rangle \BAR M\mbox{\ eventually writes a non-blank symbol
 to the tape when given input $\varepsilon$}\ \}\\
L_5 &=& \{\ \langle M\rangle \BAR M \mbox{\ accepts the string\ } a\ \}\\
L_6 &=& \{\ \langle M\rangle \BAR M \mbox{\ is the only TM accepting
  $L(M)$}\ \}\\
L_7 &=& \{\ \langle M\rangle \BAR M \mbox{\ halts on input $\epsilon$ in no
     more than 1000 steps}\ \}\\
\end{array}
\] 
\item We know that $A_{TM}$ is semidecidable but not decidable, and
its complement $\lnot A_{TM}$ is neither semidecidable nor decidable. Is the third
  language
\[
R_{TM} = \{\ \langle M, w\rangle \BAR M \mbox{\ rejects\ } w \ \}
\]
decidable, semidecidable, or neither?  Prove your answer.
\goodbreak

\item
Although the language
\[
\ADD = \{\ x\mathtt{=}y\mathtt{+}z \BAR x,y,z \mbox{\ are
  binary integers, and $x$ is the sum of $y$ and $z$}\ \}
\]
can easily be shown not to be regular, you can surely write a program (in Python, or Java,
or Turing-Machine,
etc.) that takes a
string and decides whether it's one of these correct sums of binary
numbers; \ADD is a decidable language.\footnote{
As we've discussed a couple of times now, if \ADD is decidable then
addition is computable; if you want
to add 3 and 5, consider all binary number $s$ in increasing
order, check whether ``$s\mathtt{=11+101}$'' is in \ADD,
and stop when you find an $s$ where the answer is yes.}

Now, even if you restrict yourself to a single programming language,
  (we'll use Turing Machines),
  there might be many programs to decide \ADD; they
  each decide whether the input is a correct binary sum or not, each in slightly
  different (or very different) ways.  We can then consider
  the set $\mathit{ADDERS}$ of all such programs.

\begin{enumerate}
\item Prove that the language
\[\ADDERS = \{\ \langle M\rangle \BAR M \mbox{ is a Turing Machine
  that accepts the language\ } \mathit{ADD}\ \}
\]
is not decidable.
\item 
Prove that $\ADDERS$ is also not semidecidable by showing $\lnot A_{TM} \leq \ADDERS$.
That is, reduce $\lnot A_{TM}$ to $\ADDERS$ 
by showing that if $\ADDERS$ were \emph{semidecidable}, then
$\lnot A_{TM}$ would be semidecidable too.  (You may assume
that \ADD is decidable, i.e., there is at least one Turing Machine
that decides it.)
\item If we assume our encoding of Turing Machines is such that
every string represents a
Turing Machine, then the complement of \ADDERS is the set
\[
\lnot\ADDERS = \{\ \langle M\rangle \BAR L(M) \not= \mathit{ADD}\ \}
\]
Is $\lnot\ADDERS$ decidable? If not, is it semidecidable?
Prove your answers. 
\end{enumerate}
\end{enumerate}

\end{document}
