\documentclass[12pt]{cas-handout}
\usepackage{paralist}

\newtheorem{theorem}{Theorem}
\newtheorem{condition}{Condition}
\newcommand{\eps}{\ensuremath{\varepsilon}}

\newcommand{\BAR}{\ |\ }
\newcommand{\TM}{\mathsf{TM}}


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



\anumber{10}
\title{Decidable, Semidecidable, and Undecidable}
\duedate{Wednesday, December 5}

\begin{document}
\maketitle

\begin{itemize}
  \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. Illegible answers
    will get no credit.
%%%
%%%
 \item Make sure your submission includes your name!
\end{itemize}

\hrule

\bigskip\bigskip
\noindent

\begin{enumerate}
\item Skim Chapters 19, 20, and 21 of Rich, paying particular attention to the examples.

  Come up with two questions about the reading;
  these should be questions 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.



\item Consider the following languages (where $M$ ranges over
  TMs). Are they decidable? If not, are they semidecidable?  Prove each answer.
\[
\begin{array}{lcl}
L_1 &=& \{\ \langle M\rangle \BAR M \mbox{\ accepts\ at\ least\ 999\
strings}\ \}\\
L_2 &=& \{\ \langle M\rangle \BAR M\mbox{'s program includes a transition that writes
  \texttt{a} on the tape}\ \}\\
L_3 &=& \{\ \langle M\rangle \BAR M\mbox{\ eventually writes a non-blank symbol
 to the tape when given input $\varepsilon$}\ \}\\
L_4 &=& \{\ \langle M\rangle \BAR M \mbox{\ accepts the string\ } a\ \}\\
L_5 &=& \{\ \langle M\rangle \BAR M \mbox{\ is the only TM accepting
  $L(M)$}\ \}\\
L_6 &=& \{\ \langle M\rangle \BAR M \mbox{\ halts on input $\epsilon$ in no
     more than 1000 steps}\ \}\\
     L_7 &=& \{\ \langle M,w\rangle \BAR M \mbox{\ accepts $w$ in an even number of 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{\ halts in the reject state when run on\ } w \ \}
\]
decidable, semidecidable, or neither?  Prove your answer.
\goodbreak

\item
Although the language of correct addition statements
\[
\ADD\ \  =\ \  \{\ x\mathtt{=}y\mathtt{+}z \BAR x,y,z \mbox{\ are
  decimal 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.

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 (\textit{semidecides}) 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 It is possible to encode Turing Machines as strings so that
  \emph{every} string represents some Turing Machine. In this case,
the complement of the formal language \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}

\clearpage

\item \textbf{The Elusiveness of Undecidability.}  It is widely known
  that Halting (membership in $H = \{\ \langle M,w \rangle \BAR M
  \mbox{\ halts\ on\ input\ } w\ \}$) is not decidable.  But:
 \begin{enumerate}
  \item
\label{part:halt1}
Consider the following machine, which we will call $\TM_1$.
It first confirms that the tape contains a number expressed in binary
(and if not, rejects). It then enters the following loop:
\begin{itemize}
\item All digits are zero, it halts
and accepts (ending the loop).
\item Otherwise, it decrements the binary number by 1 (by completely
  overwriting it) and restarts the loop
\end{itemize}
Does the machine $\TM_1$ halt on the input $10000000000000$?
\item
\label{part:halt2}
 Consider a similar machine, which we will call $TM_2$. It is
  exactly the same as $TM_1$, except that each time around the
  loop it \emph{increments} the binary number by 1.
   Does the machine $\TM_2$ halt on the input $10000000000000$?
\item
\label{part:halt3}
We proved in class that Halting is undecidable. Yet you just decided it twice. Why isn't this a contradiction?
\item $\TM_1$ and $\TM_2$ are admittedly not very interesting.
  You are probably wondering, since Halting is undecidable, where
  the hard Turing Machines are.
  Suppose I were to design a very complicated
  $\TM_3$, and prove mathematically that ``there is no series of steps
  by which you can determine whether $\TM_3$ terminates on the
  input $10000000000000$''  (essentially, that ``you will not and cannot
  know, even in principle, whether $TM_3$ terminates on this input'').
  Show that this supposition leads to a contradiction.

  (It follows that, although there's no algorithm to solve the
  halting problem in general, we cannot point to any \emph{specific} instance
  as the undecidable input.)
\end{enumerate}


\end{enumerate}

\end{document}
