notes.tex

\documentclass[english, 12pt]{article}
\usepackage{notes}
% Uncomment these for a different family of fonts
% \usepackage{cmbright}
% \renewcommand{\sfdefault}{cmss}
% \renewcommand{\familydefault}{\sfdefault}
\usepackage{euler}
\usepackage{concmath}
\usepackage{soul}
\usepackage{hyperref}
\usetikzlibrary{chains,fit,shapes}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
 
\urlstyle{same}

\newcommand{\thiscoursecode}{CMPS132}
\newcommand{\thiscoursename}{Computability and Complexity Theory}
\newcommand{\thisprof}{Dr. Seshadhri Comandur}
\newcommand{\me}{Andrew Edwards}
\newcommand{\thisterm}{(Spring) 2015}
\newcommand{\website}{https://users.soe.ucsc.edu/~sesh/cmps132-15/cmps132-15.html}

% Headers
\chead{\thiscoursecode}
\lhead{\thisterm}


%%%%%% TITLE %%%%%%
\newcommand{\notefront} {
\pagenumbering{roman}
\begin{center}

{\ttfamily \url{\website}} {\small}

\textbf{\Huge{\noun{\thiscoursecode}}}{\Huge \par}

{\large{\noun{\thiscoursename}}}\\ \vspace{0.1in}

{Notes by: {\noun \me}} \\\vspace{0.1in}

  {\noun \thisprof} \ $\bullet$ \ {\noun \thisterm} \ $\bullet$ \ {\noun {UC Santa Cruz}} \\

  \end{center}
  }

% Begin Document
\begin{document}

  % Notes front
  \notefront
  % Table of Contents and List of Figures
  \tocandfigures
  % Abstract
  \doabstract{TODO}

  \section{Introduction}
  The various disciplines of computer science can roughly be split into
  those focusing primarily on application or and those focusing on theory. 
  We see the same division in most sciences: theoretical versus experimental
  physics, theories of molecular biology and laboratory experiments,
  pure and applied mathematics, etc. However, in computer science,
  the two sides are more closely intertwined, and the relationship between
  theory and application has a unique and far-reaching feature. \n

  Theoretical computer science research puts physical limitations on what
  is acheivable by computation, and hence by computers. This top-down
  causality is peculiar and noteworthy. In physics, a theory must be 
  supported by experimentation in order to be accepted, and more often than
  not, the theory is physically motivated from the outset. Biology is an even
  more extreme example of scientific law guided by physical experiment. 
  As we will see, the physical ability to harness the power of computation
  is constrained by a purely mathematical result. \n

  But what exactly do we mean by computation? 

  \subsection{What is Computation?}
  For now, we appeal to intuition. Computation is the process of taking a
  set of {\bf inputs} to an {\bf output}, following some well-defined 
  sequence of steps. The description of these steps is called an {\bf algorithm}. \n

  Computation is the mechanism of transforming information via some specific
  set of rules. Hitherto we have not defined {\it what form} this set
  of rules may take, nor have we even defined what form the input can take.
  For now, we simply assume that the input is {\bf finite} and that the
  description for how the computation proceeds is also finite. \n

  Every computer you have ever used operates on these basic principles.
  Program input is received through the keyboard and mouse, and potentially from
  complex commands to fetch input data from storage or from the Internet.
  Output can be displayed on a screen, written to a binary file, or ``piped''
  into another program. Programs themselves come in a multitude of forms. 
  A program is often written in a high level language like \texttt{Java},
  \texttt{C}, or \texttt{Python}. Some other program then either interprets
  (in the case of \texttt{Java} and \texttt{Python}) or compiles (in the case 
  of \texttt{C}) the program, so that the high level commands get converted 
  into a low level, machine executable form. \n

  The capabilities of modern computers are awesome. No human can claim
  superiority to a computer in a game of checkers or chess. Physics and 
  graphics engines generate strikingly realistic scenes and simulations.
  What limits, if any, are there on what we can acheive via computation?
  \subsection{Hilbert's 23 Problems and Hilbert's Program}
  David Hilbert was a prominent mathematician of the late nineteenth and
  early twentieth century. His research areas included functional analysis,
  geometry, and mathematical logic. Hilbert also was one of the first
  mathematicians to distinguish between mathematics and metmathematics.
  \footnote{\url{http://plato.stanford.edu/entries/hilbert-program/}} \n

  In 1900, Hilbert presented a list of 23 unsolved problems at the
  International Congress of Mathematicians in Paris. The tenth problem
  of the list is,
  \begin{quote}
      Find an algorithm to determine whether a given polynomial Diophantine 
      equation with integer coefficients has an integer solution, or prove
      that no such algorithm exists.
  \end{quote}
  In general, a Diophantine equation is one whose sought after solutions must
  be integers. For example, consider
  \[ x^n + y^n = z^n \]
  If $n = 1$, then there are infinitely many solutions. The set 
  \[ \{(x, y, z) = (p, q, p + q) : p, q \in \mathbb{Z}\} \] gives a
  parametrization of all solutions. If $n = 2$, we reach the familiar
  Pythagorean equation. We can parametrize all solutions by the set
  \footnote{See Chapter 0 of Allen Hatcher's {\it 
  \href{http://www.math.cornell.edu/~hatcher/TN/TNpage.html}
       {Topology of Numbers} } for a great exposition of this result.}
  \[ \{ (x, y, z) = (p^2 - q^2, 2pq, p^2 + q^2) : p, q \in \mathbb{Z}, p > q
  \}. \]
  However, for all $n > 2$, this Diophantine equation has no solutions. This
  fact is known as Fermat's Last Theorem, and took mathematicians centuries
  to prove (it was finally proven by Andrew Wiles in 1994). Similarly, the
  (somewhat trivial) example \(x^2 + 1 = 0\) has no integer solutions. So 
  clearly some Diophantine equations have solutions and some do not.
  Hilbert's tenth problem asks for an algorithm that takes as input a 
  Diophantine equation an returns (say) ``TRUE'' if a solution exists and
  ``FALSE'' otherwise. \n

  It turns out that no such algorithm exists. Over the course of 21 years,
  mathematicians Yuri Matiyasevich, Martin Davis, Julia Robins, and Hilary
  Putnam worked on the problem, and eventually produced the MDRP theorem,
  which (essentially) proves that no such algorithm exists. Their proof 
  draws an equivalence between the set of solutions to a given Diophantine
  equiation and computably enumerable sets (a concept we will study later).
  Their proof involves very sophisticated mathematics, so for now we will
  have to trust the mathematical community on the validity of this result.
  \n

  Knowing that Hilbert's tenth problem cannot be solved by an algorithm,
  we have our first theorem:
  \begin{thrm}
      There exist problems unsolveable by computation.
  \end{thrm}
  We will not be able to prove this result just yet; we will come back to
  it in Chapter 2. However, given a specific model of computation, it's to
  not too hard to concoct an unsolveable problem.
  \subsection{Computing Functions}
  Consider the following set of functions
  \[ \mathcal{F} = \{ f | f : \mathbb{N} \rightarrow \{0,1\} \} \]
  In English, $\mathcal{F}$ is the set of all functions mapping each natural
  number \(n \in \mathbb{N} = \{0, 1, \dots \} \) to either zero or one.
  Now, suppose we pick a specific function $f \in \mathcal{F}$. Can we
  compute $f$? \n

  Clearly the answer depends on how we do the computing! As we saw in
  CMPS130, a Pushdown Automaton (PDA) is strictly more powerful than a
  Deterministic Finite Automaton (DFA), and a Turing Machine (TM) is
  strictly more powerful than a PDA. For now, let's not be too concerned
  with formality. Let's pick a familiar, powerful model of computation:
  $\pC$ programs. \n

  As an example, consider the function 
  \[f(n) = \begin{cases} 0 & \text{if $n$ is even} \\
                         1 & \text{if $n$ is odd} \end{cases}\]
  The following $\pC$ function, which we'll call \texttt{f.c}.
  \begin{lstlisting}
  #include <stdio.h>
  int main(int argc, char** argv) {
      int n = argc - 1;
      printf(``%d'', n % 2);
  }
  \end{lstlisting}
  Here is the result of compiling and running this program on a Unix machine:
  \begin{lstlisting}[language=bash]
  $ gcc f.c -o f
  $ ./f
    0
  $ ./f 1
    1
  $ ./f 1 1
    0
  $ ./f 1 1 1
    1
  \end{lstlisting}
  So our program $\texttt{f.c}$ can compute $f(n)$ by passing in 
  $n$ space separated arguments to the compiled program. To keep it simple we
  can use a space separated unary encoding of $n$. We can alter this program
  in a virtually unlimited number of ways to compute other functions, such
  as $g(n) = 1$ if $n$ is odd, $h(n) = 1$ if $n$ is greater than $42$, and 
  $p(n) = 1$ if $n$ is a prime number.\n

  Does every function $f \in \mathcal{F}$ have a corresponding program 
  \texttt{f.c}? We are about to see that the answer is no, which leads us
  to
  \begin{thrm} There exists a function $f \in \mathcal{F}$ such that no
               $\pC$ program computes $f$.
  \end{thrm}
  Note the difference between Theorem 1.1 and Theorem 1.2. The first claims
  that there exist problems that {\bf no} model of computation can solve. The
  second makes a weaker claim: given a specific model of computation ($\pC$ 
  programs), there exist problems that cannot be solved by the model.

  The proof is not too hard, and it takes advantage of the following simple
  fact:\[\text{ 
  {\it Every} $\pC$ {\it program is a finite string of characters}.
  }\]
  We now prove Theorem 1.2.
  \begin{proof}
  Imagine listing {all finite character strings} (say ASCII strings to 
  keep things simple). Most of these won't correspond to a $\pC$ program,
  but some of them do. We can imagine stepping through all the character 
  strings of length 1, all of length 2, ad infinitum, and trying to compile
  the string with \texttt{gcc}. We keep all programs that compile and,
  when run via 
  \texttt{./f} $\underbrace{\texttt{1 1}\dots\texttt{1}}_{n}$, print out
  zero or one. We can just discard those that don't.\footnote{If you are worried
  about the program printing stuff other than zero or one, we can change our model 
  to only allow \texttt{printf(``0'')} and \texttt{printf(``1'')} print statements. Or
  we could interpret any character that is not \texttt{0} to correspond to a \texttt{1}.
  Our intention is not to be overly technical or pedantic at this point.} \n

  We will eventually list all valid programs in our model. Let's label
  the program as \texttt{f\_0.c}, \texttt{f\_1.c}, \dots For each program
  \texttt{f\_i.c}, let $f_i(n)$ be the funciton this program computes.
  We can view all the functions and their outputs with a rectangular grid:
\[
\begin{tabular}{c|c|c|c|c}
$n$             & $0$   & $1$   & $2$   & \dots \\
\hline
$f_0(n)$ & $0$   & $0$   & $0$   & \dots \\
\hline
$f_1(n)$ & $1$   & $0$   & $1$   & \dots \\
\hline
$f_2(n)$ & $1$ & $1$ & $0$ & \dots \\
\hline
\vdots & \vdots & \vdots & \vdots & $\ddots$
\end{tabular}
\]
  Now, consider the following function:
  \[ f(n) = 1 - f_n(n) \]
  This is a well defined function. Given $n$, we can find the $n^{th}$ $\pC$
  program \texttt{f\_n.c} and compute $f_n(n)$. Then $1 - f_n(n)$ gives us $f(n)$.\n

  The question is, does $f$ appear in our list?\n

  This is the crux of the proof: $f$ {\it does not} appear in the list. 
  It disagrees with every function in the list on where to map the input
  $n$. But this list contains all functions computable by $\pC$ programs! 
  Therefore, $f$ is not computable.\n

  This proves Theorem 1.2.
  \end{proof}
  The argument above is called a {\bf diagonal argument}, and its origins
  trace back to the German mathematician Georg Cantor. In 1891 he proved
  that there is no bijection between the set $T$ of all infinite binary 
  sequences and the set of natural numbers. Following this style of reasoning,
  one can show that there is no bijection between the set of real numbers
  and the set of natural numbers, and that there is no bijection between the
  natural numbers and the set of all subsets of natural numbers. \n

  \subsection{A Look Ahead}
  TODO

  \section{Computational Models}
  In this chapter we will explore three models of computation. The first
  we will call $\mathcal{C}$ programs. $\mathcal{C}$ programs are like \pC 
  programs, but they have a much more limited syntax. Each $\mathcal{C}$
  operation has an analogous \pC operation, but not the other way around.
  In fact, there are only {\it three} basic operations $\mathcal{C}$, but as we will 
  see, it is just as powerful as \pC.
   
  limited subset of the language, which is the first surprise of computability
  theory:
  \[ \textbf{1. }\textit{Few rules give rise to all computation.} \]
  The second model is the Turing Machine. We assume the reader has seen
  Turing Machines before, but we will review the notation and the semantics.
  The third model is called $\mu$-Recursive functions. If you have ever
  programmed in a functional programming language, then this formalism will
  be familiar. Unlike $\pC$ programs and Turing Machines, $\mu$-Recursive
  functions operate exclusively on natural numbers. \n

  On the surface, these three models seem to be very different. This brings
  us to the second surprise of computability theory:
  \[ \textbf{2. } \textit{All models of computation are equivalent.} \]
  
  \subsection{$\mathcal{C}$ Programs}
  The first surprise of computability theory is that only a few rules
  are required to acheive the full power of computation. We demonstrate
  that in this chapter. \n

  Writing $\mathcal{C}$ programs is very simple. All programs have the 
  following form: 
  \begin{itemize}
      \item Each take a fixed number of inputs $x_1, x_2, \dots, x_k$,
            give a single output $y$, and have access to a fixed number
            of temporary variables $z_1, z_2, \dots, z_n$. Temporary variables
            and output are initially zero.
      \item All input, ouput, and temporary variables are natural numbers.
      \item The following two operations are valid on any variables:
          \begin{enumerate}
              \item $\inc{v}$, which increments the variable $v$.
              \item $\dec{v}$, which decrements the variable $v$, except at zero, 
                whence $\dec{v})_{v=0} = 0$.
          \end{enumerate}
      \item The description of a program is a sequence of instructions,
            which is either an operation on a variable, a return statement (which
            halts execution), or a conditional branch of the following form:
            \[ \text{If } v \neq 0 \text{, then go to instruction } n
            \text{. Else, continue.} \]
  \end{itemize}
  This turns out to be all we need.  \n
  
  Suppose we want to write a program that copies one variable to another. We would also like the
  input data to be unaltered at the end of the program. Now is a good time to pause and think about
  how you would do this. \n
  
  
  Given that all way can do is increment and 
  decrement, we will have to modify the input data as we copy it. The way we ensure it is unaltered
  at the end of the program is by also storing its value into a temporary variable, and then
  copying it back. Observe,
  \begin{lstlisting}
 copy(x, y, z) {
     if (x != 0)
         goto 5
     return
     dec(x)
     inc(y)
     inc(z)
     if (x != 0)
         goto 5
     dec(z)
     inc(x)
     if (z != 0)
         goto 10
     return
 }
  \end{lstlisting}
  Visualizing the computation is a lot like debugging with \texttt{GDB}. We can view the execution of
  \texttt{copy(10, y, z)}, by listing each instruction with the state of memory on the right
   \begin{lstlisting}
   copy(10, y, z)     ||   (x, y, z) = (10, 0, 0)
   if (x != 0)        ||         10 != 0 is true
       goto 5
   dec(x)             ||   (x, y, z) =  (9, 0, 0)
   inc(y)             ||   (x, y, z) =  (9, 1, 0)
   inc(z)             ||   (x, y, z) =  (9, 1, 1)
   if (x != 0)        ||          9 != 0 is true 
       goto 5         ||
   ...
   dec(x)             ||   (x, y, z) = (1, 9, 9)
   inc(y)             ||   (x, y, z) = (0, 10, 9)
   inc(z)             ||   (x, y, z) = (0, 10, 10)
   if (x != 0)        ||          0 != 0 is false
   dec(z)             ||   (x, y, z) = (0, 10, 9)
   inc(x)             ||   (x, y, z) = (1, 10, 9)
   if (z != 0)        ||          9 != 0 is true
       goto 10        ||
   ...
   dec(z)             ||   (x, y, z) = (9, 10, 0)
   inc(x)             ||   (x, y, z) = (10, 10, 0)
   if (z != 0)        ||          0 != 0 is false
   return
   \end{lstlisting}
      
  \subsection{Turing Machines} 
  We are ready to study our second model of computation: the Turing Machine (TM). \n
   
  %% Draw TM 
  \begin{tikzpicture}[baseline=-250]
      \edef\sizetape{0.7cm}
      \tikzstyle{every path}=[very thick]
      \tikzstyle{tmtape}=[draw, minimum size=\sizetape]
      \tikzstyle{tmhead}=[arrow box, draw, minimum size=0.5cm, arrow box
      arrows={east:0.25cm, west:0.25cm}]
      
      \begin{scope}[start chain=1 going right, node distance=-0.15mm]
          \node [on chain=1, tmtape, draw=none] {$\ldots$};
          \node [on chain=1, tmtape] {};
          \node [on chain=1, tmtape] {0};
          \node [on chain=1, tmtape] {1};
          \node [on chain=1, tmtape] {0};
          \node [on chain=1, tmtape] (input) {1};
          \node [on chain=1, tmtape] {1};
          \node [on chain=1, tmtape] {1};
          \node [on chain=1, tmtape] {0};
          \node [on chain=1, tmtape] {};
          \node [on chain=1, tmtape, draw=none] {$\ldots$};
      \end{scope}

      \begin{scope}
          [shift={(3cm,-5cm)},start chain=circle placed {at=(-\tikzchaincount*60:1.5)}]
          \foreach \i in {q_1, q_2,  \vdots, q_h, \ddots, q_n}
              \node [on chain] {$\i$};
          \node (center) {};
          \draw[->] (center) -- (circle-2);
          \node[rounded corners,draw=black,thick,fit=(circle-1) (circle-2) (circle-3) 
                   (circle-4) (circle-5) (circle-6), label=below:\textbf{Finite Control}] (fsbox) {};
      \end{scope}
      
      
    %% Draw TM head below (input) tape cell
\node [tmhead,yshift=-.3cm] at (input.south) (head) {$q_2$};

%% Link Finite Control with Head
\path[->,draw] (fsbox.north) .. controls (4.5,-1) and (0,-2) .. node[right] 
			(headlinetext)
 			{} 
			(head.south);
  \end{tikzpicture}
  \parbox[b]{8cm}{
   We assume the reader has encountered TM's before, and has studied its use as a language
   recognizer. We will use the following notation to define TM's:
     \begin{definition}
      A {\bf Turing Machine} (TM) is defined by the five tuple \( (Q, q_0, q_h, \Sigma, \Gamma, \delta) \),
      where $Q$ is a finite set of states, $q_0 \in Q$ is the {\it initial state}, $q_h$ is the {\it halt state}, $\Sigma$
      is the input alphabet, $\Gamma$ is the tape alphabet, and 
      $\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times DIR$ is the transition function, where
      \(\delta( q, \sigma) = (q', \sigma', D) \) means
      that reading the character $\sigma$ while at state $q$ causes the machine
      to replace $\sigma$ with $\sigma'$ and transition to state $q'$, and
      move the reading head one step in the direction $D$. \n
      $DIR$ is the set $\{LEFT, RIGHT\}$. \n
      The machine halts execution if it reaches state $q_h$.
  \end{definition}
}

 Alan Turing, the inventor of the TM, writes in his seminal paper of 1936 , 
 \begin{quote}We may compare a man in the process of computing \!...\!\! to a
                        machine which is only capable of a finite number of conditions,
                        $q_1, ..., q_n$, which will be called $m$-configurations.
                         The machine is supplied with a
                       ``tape'' (the analogue of paper) [...] divided into sections 
                       (called ``squares'') each capable of bearing a ``symbol''.
\end{quote}
Since their behavior at any point is completely determined  by the
current state and current symbol being read, Turing called them 
automatic machines. 


  \subsection{$\mu$-Recursive Functions}
  \subsection{Church-Turing Thesis}
  \section{Undecidabilityl}
  \subsection{The Halting Problem}
  \subsection{Reducibility}
  \end{document}