\titletext
Aaron Karper
Aaron Karper
all.tex
\begin{filecontents*}{abstract.tex}
The field of computability and complexity was, where computer science
sprung from. Turing, Church, and Kleene all developed formalisms that
demonstrated what they held "intuitively computable". The times change
however and today's (aspiring) computer scientists are less proficient in
building automata or composing functions and are much more native to the
world of programming languages. This article will try to introduce typical
concepts of computability theory and complexity in a form more fitted for
a modern developer.  It is mostly based on \cite{jones}, but takes input
from other sources to provide examples, additional information, etc.
\end{filecontents*}

\begin{filecontents*}{all.tex}
\end{filecontents*}

\begin{filecontents*}{complexity.tex}
As we saw, not all problems are solvable, but it seems not too far-fetched to
say that a problem not being solvable by any algorithm is seldom a concern for
most applications. Being solvable in a reasonable amount of time and space
however can very easily become a problem. What use is a program that solves our
problem, but takes hundreds of years to complete for any reasonable input? This
is where the field of complexity theory sets in: it characterises the solvable
problems by their "difficulty".

The most intuitive measure of difficulty is arguably time-complexity, i.e.\ how
long any algorithm will take to solve the problem in the worst case. Also
space-complexity needs to be considered, i.e.\ how much storage one needs to
complete the computation.

Since bigger problems are harder to solve and bigger problems need more data to
describe it fully, we analyse the asymptotic complexity in the size of the
input, i.e.\ how the time and space needed develop as the input grows towards
infinity. The most important distinctions here will be if there is a linear
relation or a polynomial of higher order -- or something worse, e.g.\ exponential
time/space.

Another important classification is that of non-determinism: if we could guess
during the computation, how would that affect the complexity of the problem?
Could we solve things faster, if we only guessed good enough? Surprisingly the
answer is that we are not sure (even though it is strongly suspected that being
a good guesser really helps).

As in computability with the Church's thesis, there is the question of what is
intuitively computable in a certain bound and even more than in computability,
this question seems to rely on the chosen formalism, but most of the
distinctions are quite robust. Still the question remains, if some
extraordinary feat of engineering can build a machine that is much faster than
our Turing machine model\footnote{Quantum computing is faster than \TM\@. A 
	quantum computer can search a list for an element in $O(\sqrt{n})$ time as 
	shown in \cite{grover1996fast}.}. 

The problems we discuss are decision problems:
\begin{defn}
	A problem $P$ is called a \emph{decision problem}, if the required output is 
	in $Bool = \{True, False\}$.
\end{defn}

Our high-level \WHILE language served us well in computability, but it would
be more confusing to measure time and space requirements than on the
lower-level Turing machine.

For example, how would we measure the used space in a simple, yet realistic
way: If I set {\tt Y := cons X X}, do I copy {\tt X} twice? Once?  Not at all?
What happens if I reassign a variable, that was used earlier?  This discussion
would surpass the scope of this text\footnote{\cite[p. 325f]{jones} gives a
possible measure.}.

\begin{defn}[Running time]
	For a machine $m\in \TM$ and the input $x$, we will write 
	$\measuretime[\TM]{m}(x)$ or just $\measuretime{m}(x)$ to denote the number 
	of steps that $m$ needs to get from the starting state $q_0$ to the end state 
	$e_{accept}$. If that does not happen, $\measuretime[\TM]{m}(x)=\infty$.
\end{defn}

%We will denote the time that a program $P\in \WHILE$ runs on an input $x$ by
%$\measuretime[\WHILE]{P}(x)$ or just $\measuretime{P}(x)$. To determine what
%that means, let's consider how long statements take to evaluate: we have only
%three kind of statements, assignment, if and while. Assigning a value can be
%thought of as writing an address, which can be done in one time-step. Of
%course, the right hand side might take some time to evaluate, so
%$\measuretime{X := E} = 1 + \measuretime{E}$. If statements take one step to
%check if the value is nil and the evaluation, likewise for while.  Also
%depending on the runtime values, the block its evaluated zero or more times.

%As for expressions, nil takes no time at all, since its not computed and all
%other expressions take one step plus the evaluation of subexpressions.
Not only time is a limited resource, also the memory that is used during the 
computation can limit the applications of an algorithm. Some problems could 
be solved for example just by reading the input and writing a fixed number of 
items into the memory -- for example searching an element in a list --, others
would need to increase their memory usage by a fixed amount each time the 
input doubles, for example calculating the median of a list of numbers, and 
some neen much more space.


\begin{defn}[space usage]
	The space usage $\measurespace{M}(x)$ for $M\in \TM$ is the maximum of the 
	maximum of the space usage of the states of its computation or $\infty$ if 
	the machine does not halt -- even if it looped on the same cells over and over.

	The space usage of a state of computation is the number of cells between the 
	left-most and the right-most non-blank cell. For example {\tt \dots \# \# 0 1 
	0 0 \# 1 0 1 1 \# \# \dots} would use 9 cells.
\end{defn}


\begin{defn}[Complexity Classes]
	\begin{equation*}
		\begin{split}
			\TIME[f]  &:= \{l\in \TM : \forall x\in \Input:  \measuretime{l}(x) \leq f(\abs{x})\} \\
			\SPACE[f] &:= \{l\in \TM : \forall x\in \Input: \measurespace{l}(x) \leq f(\abs{x})\}
		\end{split}
	\end{equation*}
	So
	\begin{enumerate}
		\item A program is in the complexity class $\TIME[f]$, if its running time is always bound 
			by $f$ of the size of the input.
		\item A program is in the complexity class $\SPACE[f]$, if its memory usage is always bound 
			by $f$ of the size of the input.
	\end{enumerate}
	And we call a problem $P$ in a complexity class $C$, if there is an 
	algorithm $p$ that solves it, such that $p\in C$.
\end{defn}

The most important complexity classes are those of the relatively slow 
growing polynomial functions:

\begin{defn}[Polynomial time and space]
	\begin{equation*}
		\begin{split}
			\PTIME &:= \bigcup_{p\text{ is polynomial}}\TIME[p] \\
			&= \left\{l\in \TM \exists p=\sum^n_{k=0}a_k\,x^k: \forall x\in \Input: \measuretime{l}(x)\leq p(\abs{x})\right\}\\
			\PSPACE &:= \bigcup_{p\text{ is polynomial}}\SPACE[p] \\
			&= \left\{l\in \TM \exists p=\sum^n_{k=0}a_k\,x^k: \forall x\in \Input: \measurespace{l}(x)\leq p(\abs{x})\right\} 
		\end{split}
	\end{equation*}

	That is:
	\begin{enumerate}
		\item A program is in the complexity class $\PTIME$, if its running time is always bound 
			by some polynomial.
		\item A program is in the complexity class $\PSPACE$, if its memory usage is always bound 
			by some polynomial.
	\end{enumerate}
\end{defn}

On the other hand the exponential functions grow so fast, that an algorithm 
taking exponentially long is often only feasible for small inputs.

\begin{defn}[Exponential time and space]
	\begin{equation*}
		\begin{split}
			\EXPTIME &:= \bigcup_{p\text{ is polynomial}} \TIME[2^{p(x)}]\\
			\EXPSPACE &:= \bigcup_{p\text{ is polynomial}} \SPACE[2^{p(x)}]\\
		\end{split}
	\end{equation*}
	So here
	\begin{enumerate}
		\item A program is in the complexity class $\EXPTIME$, if its running time is always bound 
			by an exponential of some polynomial.
		\item A program is in the complexity class $\EXPSPACE$, if its memory usage is always bound 
		by an exponential of some polynomial.
	\end{enumerate}
\end{defn}

\section{The complexity hierarchy}
We can clearly see that $\LOGSPACE\subseteq \PSPACE\subseteq\EXPSPACE$ just because of 
the functions involved, but the $\TIME$ and $\SPACE$ 
hierarchy is in fact interleaved, as the following theorems will prove.
\begin{theorem}
	\[\TIME[f] \subseteq \SPACE[f]\]
\end{theorem}
\begin{proof}
	On our tape, the only way to increase the number of cells used is to write 
	something in an blank cell. That we can do at most once per step.
\end{proof}

\begin{theorem}
	There are $a>0$ and $q > 1$ and $\exp(x) := a\cdot q^x$ such that:
	\[\SPACE[f] \subseteq \TIME[\exp\circ f]\]
\end{theorem}
\begin{proof}
	\begin{enumerate}
		\item Assume that $P\in\SPACE[f(x)]$, then $\forall x: \measurespace{P}(x)\leq f(\abs{x})$.
		\item Assume that $\abs{x}$ is fixed, then in how many ways can the 
			memory arranged to hold that property? Each cell can hold any of the 
			symbols of $\Gamma$, so there are $\abs{\Gamma}^{f(\abs{x})}$ ways to 
			arrange that. Multiply that with the number of states that are not
			end states and you get the number of steps after either the machine is in
			a configuration it has seen before or goes to a new configuration --
			necessarily an end state. If the Turing machine is in the same
			configuration, then it will necessarily act in precisely the same way 
			as before, get to the same configuration again and again, and therefore loop. 
		\item But since $\measurespace{P}(x)\leq f(\abs{x})$, 
			$\measurespace{P}(x) \neq \infty$ and therefore 
			\[\measuretime{P}(x)\leq (\abs{Q} - 2)\cdot\abs{\Gamma}^{f(\abs{x})}\]
	\end{enumerate}
\end{proof}

\begin{corollary}
	\[ %\LOGSPACE\subseteq
		\PTIME\subseteq\PSPACE\subseteq\EXPTIME\subseteq\EXPSPACE \]
\end{corollary}

Surprisingly, it is not known, if these inclusions are strict. It has not 
been proven yet, that $\PTIME\neq \PSPACE$ or that $\PSPACE\neq\EXPTIME$. 
Complexity theory is full of these uncertainties, even if it superficially 
mirrors computability theory, it has proven to be hard on much more basic
levels than computability has.

\subsection{Hierarchy Theorems}
While not much is known, there are two important \emph{hierarchy theorems}, 
which give proper inclusions. To formulate that, we need the notion of a \emph{
time constructible function}\/:

\begin{defn}
	A function $f$ is called \emph{time constructible}\/ if there is a 
	$M\in\TM$, such that for sufficiently big $n$, $\TIME[M](1^n) = f(n)$.

	A function $f$ is called \emph{space constructible}\/ if there is a $M\in\TM$, 
	such that for sufficiently big $n$, $\SPACE[M](1^n)=f(n)$.

	Basically, this states, that there are Turing machines with this exact time 
	or space requirement $f(x)$.
\end{defn}
\begin{example}
	\begin{enumerate}
		\item $f(x)=x$ is time and space 
			constructible: Copy the input to the output tape.
		\item If $f$ is space constructible, then $g(x)=(x+1)\cdot f(x)$ time and space
			constructible. Run the machine from above on the output of the
			constructing machine: Running the constructing machine takes $f(x)$ time and space and then running the linear machine adds $x\cdot f(x)$.
		\item If $f$ is time/space constructible, then 
			$\forall c\in \mathbb{N^+}: g(x)=c\cdot f(x)$ is time/space 
			constructible: Run the constructing machine $M$ for $f$, but cicle through $c$ 
			states for each step of $M$.
		\item If $f$ and $g$ are time/space constructible, then $h(x) = f(x)+g(x)$ is time/space
			constructible. Just run them one after the other. 
		\item $f(x)=\sum^n_{k=0}c_k\cdot x^k$ is space and time constructible for 
			$c_i\in N^+$. Follows from above.
		\item $f(x)=2^x$ is time constructible: for the $k$th input symbol, count up 
			to the number $1(0)^k$ in binary.
		\item $f(x)=2^x$ is space constructible: First write $1$ on the output 
			tape, then for each element of the input, copy the output tape to its own end.
		\item If $f(x)\leq x$ for infinitely many $x$ then $f$ is \emph{not}\/ time
			constructible: We can't read the input, so we couldn't know, how long it
			would have been.
		\item This is not true for space constructible functions: We could even 
			read the input and not write anything, thus $f(x)=0$ is time constructible.
	\end{enumerate}
\end{example}

\begin{theorem}[Time Hierarchy]
	If $f$ is time-constructible, then
	\[ \TIME[o\left(f(x)\right)] \neq \TIME[f(x)^3] \]
\end{theorem}
\begin{proof}
	\begin{enumerate}
		\item The proof will show, that we can find a function, that is in 
			$\TIME[O(f(x)^3)]$, but not in any $\TIME[o\left(f(x)\right)]$
		\item The function that does that is 
			\[ \interpret{H_f}(M, n) \peq \begin{cases}
					True, &\text{if }\TIME[M](n) \leq f(\abs(n))\,\text{and $M$ ends in $q_{accept}$}\\
					False, &\text{otherwise}
			\end{cases} \]
			We can run $H_f$ by using an interpreter ($O(steps^2)$) and counting the steps on a 
			separate tape, so pessimistically\footnote{The Time Hierarchy Theorem 
			holds even for $\TIME[f(x)\cdot\log f(x)]$ with a trickier interpreter
			and counting} this is in $\TIME[O(f(x)^3]$. 
		\item On the other hand assume that $H_f\in \TIME[f(\floor{\frac{\abs{x}}{2}})]$, 
			then $\interpret{G}(m) :\peq not\,\interpret{H_f}(m, m)$ runs only
			\[f\left(\floor{\frac{2\abs{m}+1}{2}}\right)=f(\abs{m})\] steps. 
		\item Thus 
			\[\interpret{G}(G)\peq not\, \interpret{H_f}(G,G) \peq not\, True \peq False,\]
			but that would imply, that $H_f$ would reject it, therefore 
			\[\interpret{G}(G)\peq not\, \interpret{H_f}(G,G) \peq not\, False \peq True\]
			and vice versa -- which is a contradiction. Therefore $G\not\in\TIME{f(x)}$ 
			and $H_f\not\in\TIME{f\left(\floor{\frac{x}{2}}\right)}$
	\end{enumerate}
\end{proof}

\begin{corollary}
	\[\PTIME\neq\EXPTIME\]
\end{corollary}
\begin{proof}
	$x^n$ is time constructable for all $n\in \N$, but 
	$x^{3n} < 2^x \Leftrightarrow 3n\cdot \log_2 x < x \Leftrightarrow \frac{\log_2 x}{x} < 3n$
	, which holds for any $n$, if $x$ is big enough, so there is no polynomial 
	close enough to the exponentials, that would allow the \PTIME\/ class to 
	``jump'' into the \EXPTIME\/ class.
\end{proof}

\begin{theorem}[Space Hierarchy]
	If $f$ is space constructible, then $\SPACE[o(f(x))] \neq \SPACE[f(x)]$.
\end{theorem}
\begin{proof}
	This proof is very similar to the Time Hierarchy theorem. Instead of 
	counting the steps, we can write out $f(x)$ in unary on a second tape, and 
	move this in parallel to the computation tape. If at any point, an unmarked 
	cell is hit on the second tape, we know that we used more than $f(x)$ cells 
	and reject.
\end{proof}
This theorem is much stronger than the time hierarchy theorem, because it 
shows that any difference in the asymptotic behaviour leads to a different 
computability class.

\section{Nondeterminism} % (fold)
\label{sec:Nondeterminism}
Up until now, choice did not come into play at any moment: A program gave a 
unique trace of executed instructions for any given input. In many cases 
however, algorithms contain a moment of arbitrariness, where in the 
deterministic case, one fixed way would need to be chosen. The run-time of 
the algorithm can depend very much on the choices we make. 

\begin{defn}
	A non-deterministic Turing machine ($\NTM$) is a deterministic Turing machine, where 
	the transition function $\delta$ returns sets instead of values now.

	\[ \delta: Q\times \Gamma \rightarrow \mathcal{P}(Q\times \Gamma\times \{L, N, R\}) \]
\end{defn}

	The semantics need to adapt to that, a configuration of a non-deterministic 
	Turing machine needs to contain serveral configuration of a deterministic run:

\begin{defn}
	A \emph{configuration} is $C\subset \Gamma^*\times \Gamma \times \Gamma^*\times Q$
	and a step by a \NTM is $C_1\vdash C_2$ if 
	\[ C_2 = \bigcup_{c\in C_1}\set{ step(tape_c, s_c, t) : t\in \delta (c)} \]

	This allows us to define

	\[
		\interpret[\NTM]{M}(tape_1) = \bigcup_{(tape_1, q_0) \vdash^*_M C}\set{ tape : (tape, q_{accept}) \in C}
		\]

	So if any computation for some choices ends in $q_{accept}$, then the 
	computation of the non-deterministic machine succeeds. For decision 
	problems, we only need to know that this set is not empty.
\end{defn}

\begin{example}
	When parsing the string $\mathtt{aabab}$ with the regex 
	$\mathtt{(a|ab)+}$, we can't know after the first letter in which branch of 
	the  \emph{or} we will be. Only after we saw, that a second $\mathtt{a}$ 
	follows, we know that it was the first one.
\end{example}

\begin{defn}
	The time measure $\NTIME$ is the \emph{minimum} of the $\TIME$ measures of 
	the possible traces. Analogously, the space measure $\NSPACE$ is the 
	minimum of possible $\SPACE$ measures of the traces. It denotes the 
	fastest/least space consuming possible way to solve the problem, if guessing
	is allowed.
\end{defn}

At first, this seems like a new mode of computation and thus belong to
computability rather than complexity, but just proving that \emph{some}
computation accepts the input can be done by performing a breadth-first search
on the possible traces. The complexity however seems very different, because 
in the worst case, this approach will take $\mathcal{O}(2^{\mathcal{O}(n)})$ deterministic steps per non-deterministic step, thus an algorithm that takes $\NTIME f(x)$ will take $\TIME 2^{\mathcal{O}(f(x))}$ with this approach.

The most important class, that uses non-determinism is \NPTIME: The 
problems, that can be solved in polynomial time, if guessing is allowed and 
we guess optimally.

\begin{theorem}[Guess and check]
	If $X\in \NPTIME$, then we can find a so-called  \emph{certificate} 
	$w\in \Gamma^*$ for each input $x$, with $\abs{w} \leq p(\abs{x})$ for a polynomial $p$, so that there is a deterministic Turing 
	machine $M$ that decides $X$ given $w$ and $x$ in \PTIME. If we can 
	formulate the problem in such a way, then it is in \NPTIME.

	This means, that we can check our hypotheses for positive answers in
	polynomial time, so the hard part is only coming up with the good hypotheses.
	There is however no requirement for negative solutions, so the algorithm 
	might even fail by looping forever.\footnote{The class of decision problems, that 
	fail in non-deterministic polynomial time, but might run forever to check 
for success is called $co-\NPTIME$.}
\end{theorem}
\begin{proof}
	On one hand, we can code the trace, that lead to the succeeding computation, to the 
	tape. Checking, that a trace is valid for a given Turing machine is trivial. 

	If on the other hand we can produce a certificate for any input and check it in 
	polynomial time in $\abs{x}$ alone, then that certificate can only be $p(\abs{x})$ long for some 
	polynomial $p$ -- otherwise, we wouldn't be able to check the certificate this fast. 

	But then, we can define a non-deterministic machine, that comes up with 
	this input in $p(\abs{x})$ steps and checks that afterwards by simulating 
	the deterministic checker.
\end{proof}

We can see that $\PTIME\subset \NPTIME$, by just outputting singleton sets in 
the non-deterministic $\delta$ and intuitively it seems that non-determinism 
must accelerate the computation significantly.

\begin{thesis}
	$\PTIME\neq\NPTIME$
\end{thesis}

However, up to this point, every try to prove or disprove this statement failed.
\end{filecontents*}

\begin{filecontents*}{langcomplexity.tex}
\section{Complexity in Languages\timeestimation{30h}}
\label{sec:complexity}
While most languages we encounter are turing-complete, that does not need
to be the case. In this chapter, we will discuss the notion of a problem 
description as a programming language.

\subsubsection{Problem descriptions}
There are many different kinds of problems in computer science, for example 
sorting a list or determining if a boolean formula with variables is always
true. Nevertheless, these kind of problems are never singular -- we would not 
want an algorithm\footnote{Most definitions would not even allow this as an 
algorithm}, that could reliably sort the list $4, 8, 2, -9$, but one that 
could sort \emph{all} lists, no matter the size. This means of course, that 
algorithms need data as input to describe the problems they need to solve. 
This data is then called the \emph{problem description}. 

Looking back at the beginning, the semantic function was introduced to give 
meaning to data. Since then, we primarily used it to differentiate between 
\WHILE programs and the functions they denote. In the case of problem
descriptions, we can the interpretation of a problem would be the solution 
that we would expect. 

\begin{example}
	$U = Cons(Nil, Cons(Nil, Cons(Nil, Nil)))$, then $\interpret[unary]{U} = 3$.
\end{example}
\begin{example}
	$L=Cons(4, Cons(8, Cons(2, Cons(-9, Nil))))$ is the problem description for
	sorting the list $4, 8, 2, -9$ if given to a sorting procedure, formally
	$\interpret[sort]{L}= Cons(-9, Cons(2, Cons(4, Cons(8, Nil))))$. When given
	to a procedure, that calculates the minimum, the interpretation would be that
	instead, so $\interpret[min]{L} = -9$.
\end{example}

In this light, a problem description becomes a small and domain specific 
programming language, with the algorithm that solves it being an interpreter.
\subsection{Reductions}
Often in courses on algorithms, the same algorithm can be used in many 
different domains, because it has been observed that the two problems are 
\emph{essentially the same} or that one is \emph{essentially a special case of
another}. 

For example in chapter~\ref{Rice}, we saw that we could formulate any 
non-trivial function property as a halting problem.

\begin{defn}
	For a complexity class $X$, a $X$-\emph{reduction} of a problem $A$ to a
	problem $B$ is a compiler from the problem descriptions of $A$ to the 
	descriptions of $B$, so that compiling a description of $A$ and executing 
	it as a $B$ problem description is in $X$. We write $A\leq_X B$.
\end{defn}

\begin{example}
	The most common reductions are:
	\begin{enumerate}
		\item $\PTIME$-reductions translate and execute a problem in polynomial 
			time and therefore $\NPTIME$ and $\PSPACE$ are closed under these reductions. Nearly every $\PTIME$ problem can be $\PTIME$-reduced to any other\footnote{All instances that have accepting and rejecting answers}.
		\item Linear time reductions give much stronger bounds, so that for example
			a $O(n^2)$ problem to which another is linearly reduced, proves that the other 
			problem is $O(n^2)$ as well.
		\item Computable reductions are used to show the computability or 
			incomputability of problems.
	\end{enumerate}
\end{example}

\subsection{Examples}
The following examples should give a good impression of how the results of 
complexity can be used and what typical problems can look like. Since 
diversity was important in the writing, some results use techniques and 
helpers that have not been introduced here, but should be familiar for many nonetheless.
\subsubsection{Problems}
\paragraph{Factorization of binary numbers}
Given an integer $N$ to be factored and an upper bound $1<M<N$, is there a 
$1<d\leq M$ so that $\exists x\in \N: N = d\,x$. Or put in another way: is 
there a non-trivial divisor for $N$, that is no bigger than $M$.

It is obvious that the problem is contained in \NPTIME by the guess-and-check 
method. At first it might seem, that it is actually linear time: Just check 
up to $M$ if the counter divides $N$, but since $M$ is written in binary, it 
only takes $\log_2(M)$ space for the input, therefore counting up to the 
number is actually exponential in the input.
\begin{example}[Relevance] 
	The RSA algorithm for public key encryption allows to deduce the private keys
	from the public keys -- but only, if the attacker can factorize a big
	integer.
\end{example}

\paragraph{Context Free Grammar membership (CFG)}
A context-free grammar is a set of rules, how non-terminal symbols can be replaced by 
a mixture of again non-terminal symbols or terminal symbols (which can not be 
changed afterwards).

An easy example is the language of balanced braces:

\begin{grammar}
	<word> ::= <empty>
						\alt `(' <word> `)' <word>
						\alt `[' <word> `]' <word>
						\alt `{' <word> `}' <word>
\end{grammar}
which contains words like \texttt{([()()]\{\})} but not \texttt{(()}.

The problem is now, given a set of rules $R$, a start-token $A$ and a string 
$s$, to check whether $s$ could be produced from $A$ under the rules $R$. 
Without loss of generality, we can assume that each step produces at least 
one non-terminal character\citationneeded.

This is surely in \NPTIME, because if we were given the steps that expand $A$ 
to $s$, we could check that they do indeed produce $s$. There are however 
serveral algorithms, that efficiently expand the currently possible 
interpretations and can find the solution in
$\mathcal{O}\left( \abs{s}^3\,\abs{R} \right)$ time\footnote{See 
	\cite{sipser2006introduction}} and therefore the problem is also in \PTIME.
\begin{example}[Relevance]
	The syntax of programming languages is often
	described as a context free grammar (for example
	the syntax of \FOR in table~\ref{tab:FOR-syntax}).
\end{example}

\paragraph{Traveling Salesman Problem (TSP)}
A salesperson wants to travel to a number of locations across the country, 
but is interested in getting home as soon as possible. Given a map with 
travel times between the cities, is it possible to do the trip in time for 
their wedding anniversary in $k$ days?

More abstractly: Given a graph with weighted edges, is it possible to find a 
path crossing all nodes, so that the sum of the weights of the edges crossed 
is no bigger than $k$?
\begin{center}
	\includegraphics[height=3cm]{tsp}
\end{center}
\begin{example}[Relevance]
	A circuit is basically a round-trip over a board. As such, minimizing 
	the resistance, \dots encompasses solving the TSP.
\end{example}

\paragraph{Satisfiability of boolean expressions (SAT)}
Given a boolean expression with variables, is there a way to assign the 
variables, so that the whole expression is true?
\begin{example}[Relevance]
	When modelling certain domains, for example in a system of artificial
	intelligence, constraints are often expressed as boolean expressions or can
	be converted to them\footnote{See \cite{russell1995artificial}}. Checking
	whether the constraints can be satisfied at all can already solve problems:
	If we have the facts $F$ and the hypothesis $H$, then $H$ fits the facts, if
	and only if $F\wedge\lnot H$ is \emph{not} satisfiable.
\end{example}
\subsubsection{Polynomial reductions}
SAT is an extremely handy problem to reduce to, so the following reductions 
will mostly feature that.
\paragraph{SAT reduces to TSP}
It can be shown, that SAT can be reduced to a special case of itself, namely 
$3-cnf SAT$, the satisfiability of formulas in the so-called 3-clause normal form

\[ \bigwedge_{i=1}^n a^1_i\vee a^2_i \vee a^3_i \].
where $a^j_i$ can be any $x_k$ or $\lnot x_k$. The 
$a^1_i\vee a^2_i \vee a^3_i$ are known as the \emph{clauses}.

How this could be done might become apparent when looking at the proof of
theorem~\ref{sat-np}. Without loss of generality then, we can assume, that 
the formula is in this form, when we try to reduce it to TSP. This has the 
advantage, that we know, that all clauses must be true and that in all 
clauses, one of the atoms must be true.

TSP takes as an input the maximum summed cost, but it is clear, that there is 
a special case, in which only the existance of a round-trip is asked for, not 
the limit of the cost\footnote{One could for example set all costs to zero 
and check for any number $M$}. This case is known as the Hamiltonian Cycle problem.

Now we need to create a graph, that is polynomially large in the length of 
the formula, but contains a round-trip if and only if the formula is 
satisfiable. The trick is of course using the clause-normal-form: Represent 
all clauses as a node $n_k$. The idea is now to only allow connections to 
$n_k$, if the representation of the atom makes the clause true\footnote{This 
construction is based on \cite[p. 286-291]{sipser2006introduction}}.

Variables have a more complex structure

\begin{itemize}
	\item a start node, in which the decision takes place, if the variable is 
		set to $True$ (left) or $False$ (right). Depending on choice, the steps 
		through the middle will allow of disallow checking off clauses.
	\item a bridge in the middle, that can either be just walked through, but 
		also has some connections to the $n_k$ nodes that will be explained shortly.
	\item an end node, which will be the start node to the next variable.
\end{itemize}

\begin{figure}[htb]
	\includegraphics[width=0.97\textwidth]{satastsp}
	\caption{The tour for the expression $(x_1\vee\lnot x_2)\wedge x_2$}
	
\end{figure}

It is clear, that the only 
round-trip possible leads through assigning all variables true or false, but 
we don't have a coding for \emph{variable $i$ appears in clause $j$}. 

This is done with giving meaning to the hops on the bridge: If the variable 
$i$ makes $j$ true if taken as $True$, then the $j$th such pair contains 
a hop from the left node to the right one over $n_j$, and from the right to 
the left, if assigning $False$ makes $j$ true.

\begin{theorem}
	This construction has a round-trip if and only if the original formula is satisfiable.
\end{theorem}
\begin{proof}
	If the formula is satisfiable, then we can tick off one clause after 
	another, by taking the hops from the bridge to $n_k$ whenever possible. 

	Now if the formula is \emph{not} satisfiable, then that means, that at 
	least one clause cannot be made true, but that translates directly to not 
	bein able to jump over to it with the current variable assignment in the graph.
\end{proof}
\paragraph{TSP reduces to SAT}
Lets reduce the TSP for the graph $G = (Nodes, Edges)$ for at most the cost
$M$ to a problem of satisfiability of boolean expressions.

We first notice, that we can add and compare numbers by building a fixed 
length binary calculator from the logical connectives, that is able to add 
all weights if necessary. This won't require to introduce more than 
polynomial many variables and connectives.

Let the variables $p_i^n$ denote, that the $i$th node of the path is $n$, 
then 
\[ PathExclusion = \bigwedge_{i=1}^{\abs{Nodes}}\bigwedge_{n\in Nodes} \bigwedge_{n'\in Nodes\atop n'\neq n} p_i^n \rightarrow \lnot p_i^{n'}\]
says that at any given position, only one node can be visited. Now we can 
just add up all weights multiplied with $1$ if they are in the round-trip or 
$0$ if they are not. This would look messy, because we have to do it bitwise, 
but the solution would look like
\[
	PathExclusion \wedge \left( \sum_{e=\in Edges} cost(e)\cdot 
	include\mhyphen edge(e) \right) \]
where 
\[ include\mhyphen edge(n_0, n_1)= \begin{cases}
		1, &\text{if }\bigvee_{k=1}^{\abs{Edges}} p_k^{n_0} \wedge p_{k+1}^{n_1}\\
		0, &\text{otherwise }
	\end{cases}\]

This formula would still be polynomially long in the input length and 
wouldn't contain any predicates. Therefore, it is polynomially reduced 
to $SAT$.
\DONE
\paragraph{Factorization reduces to TSP}
Factorization would be very easy to reduce to SAT: Given a $n$ digit binary 
number $z$, we could device $a_i$ and $b_i$ for $i=1\ldots (n-1)$ as $n-1$ digit 
binary numbers. We could then build a binary multiplier\footnote{Consult your 
favourite book on computer engineering} and check, if the result is the same 
as $z$. But we already found, that any SAT problem can be reduced to TSP, so 
if we use the construction with the zick-zack-gates again and on a large 
scale, we can convert $a_i$ and $b_i$ and the binary multiplier. Since 
applying two polynomial reductions in series still is a polynomial reduction, 
we can reduce Factorization to TSP. 
% Not sure, if I should do a smarter way, but then again, maybe there is no 
% elegant way...

\paragraph{CFG reduces to SAT}
Here as well, it is useful to use a special form, in order to manage the 
complexity that the problem in unrestricted form offers: Context-free 
grammars can (relatively easily with a mere $n^4$ blow up of the grammar) be
converted to the so called Greibach Normal Form, in which rules always have one
of the following forms:

\begin{align*}
	X &\rightarrow \alpha, A_1, A_2, \ldots, A_n \\
	S &\rightarrow \varepsilon
\end{align*}

where $A_i$ are non-terminals and $\alpha$ is a terminal. Furthermore $\varepsilon$ 
denotes the empty string and $S$ the start symbol.

This form has some consequences, for example that only one rule if any can 
produce empty strings, all others produce at least one terminal. Another nice 
property is that the string grows to the right, we don't \emph{need} to go 
back if we perfer not to.

In this case, we will just expand the left-most non-terminal one after 
another until the string is fully produced -- after at most $n$ steps, since 
we don't need to use the empty string rule, except when explicitly matching 
the empty string. Now let $R_t^r$ denote that we use the rule $r$ at the step $t$.
Since we expand one after another, we need to formalize exclusion as seen earlier:

\[ RuleExclusion = \bigwedge_{t=1}^{n}\bigwedge_{r\in Rules} \bigwedge_{r'\in Rules\atop r'\neq r} R_t^r \rightarrow \lnot R_t^{r'}\]

Furthermore we need to model the string after the step $t$, by defining 
$S^A_{x,t}$ to mean that the $x$th symbol of the string is $A$ at the time $t$. 
Again, we exclude the possibility, that the string has multiple symbols at 
the same time and space.

\[ SymbolExclusion = \bigwedge_{t=1}^{n}\bigwedge_{x=1}^{n}\bigwedge_{s\in Symbols} \bigwedge_{s'\in Symbols\atop s'\neq s} S_{x,t}^s \rightarrow \lnot R_{x,t}^{s'}\]

With these at our disposal, we can define the expansion rules: 
$Rule_j = X \rightarrow \alpha, A_1, \ldots, A_m$ becomes 
$\coded{Rule_j} = S^X_{i,t}\rightarrow S^\alpha_{i,t+1}\wedge \bigwedge_{k=1}^m S^{A_k}_{i+k, t+1}$

Then the matching of context-free grammars can be solved by solving

\[ RuleExclusion \wedge SymbolExclusion \wedge \bigwedge_{t=1}^{n}\bigvee_{j = 0}^{\abs{Rules}} \coded{Rule_j} \]

\subsection{Hardness and completeness}
We saw that in computability, there seems to be a natural border of 
computability, in which \WHILE, Turing machines and nearly any reasonably 
strong language reside. It was not too surprising then, that these different 
languages could express each other and themselves by means of interpretation and
compilation. Maybe more surprising is, that the complexity classes \PTIME and 
\NPTIME seem to be a similarly natural border.

\begin{defn}
	For a complexity class $C$, a problem $P$ is \emph{hard}, if 
	$\forall c\in C: c \reducesTo_{\PTIME} P$.

	The problem $P$ is \emph{$C$-complete}, if $P$ is $C$-hard and $P\in C$.
\end{defn}
\begin{example}
	\begin{itemize}
		\item \FOR is \PTIME-hard, but not complete, because not all \FOR programms run in \PTIME.
		\item \TM is \WHILE-complete.
	\end{itemize}
\end{example}
These examples are a bit cheated, since they use extremely large complexity 
classes. But in fact, we have seen two problems already, that are \NPTIME-complete.

\subsubsection{SAT is \NPTIME-complete}
\begin{theorem}
	\label{sat-np}
	The satisfiability of boolean formulas is \NPTIME-complete.
\end{theorem}
\begin{proof}
	For completeness, inclusion and universality are required.

	To prove $SAT\in \NPTIME$, we use the guess-and-check definition of 
	\NPTIME. The required certificate in this case is a mapping of the variables to 
	truth-values. This is at most linear in the length of the expression, 
	therefore fulfilling the required \PSPACE length of the certificate. Given the 
	certificate, we can then fully evaluate the expression, which again takes 
	linear time.

	The general idea how to create an $X$-complete problem is to simulate the 
	mode of computation. In the case of space completeness, you fail if you 
	move out of a premarked part of the tape, in the case of 
	\PTIME-completeness, you count down your remaining time and in the case of 
	\NPTIME-completeness, you build a table of possible configurations of the 
	turing machine and see if any of them succeeds\footnote{This proof combines 
		ideas from the proofs given by \cite{jones} and \cite{sipser2006introduction}}.

	% Jones has a more elegant approach, but that requires to introduce the 
	% language SBoole, which then simulates a GOTO program, which simulates a 
	% TM. However the solution is so much prettier, that I consider adapting it 
	% to the known formalisms.
  %
	First of all, it is not necessary to use transition function 
	$\delta: Q\times \Gamma \rightarrow \mathcal{P}(Q\times \Gamma\times \{L, N, R\})$
	, it is sufficient to be able to choose between two alternatives. If for 
	example $\delta(q, x) = \set{(q_1, y_1, d_1), \ldots, (q_n, y_n, d_n)}$, 
	then we can simply and polynomially reduce it to a list of binary 
	choices\footnote{The use of tuples instead of sets stems from the fact, 
	that one cannot speak of the \emph{first} or \emph{second} element of a 
	set, but for strict semantics, this is necessary.}:
	\begin{align}
		\delta(q, x) &= \Big((q_1, y_1, d_1), (q^{(1)}, x, N) \Big)\\
		\delta(q^{(1)}, x) &= \Big((q_2, y_2, d_2), (q^{(2)}, x, N) \Big)\\
		&\vdots \\
		\delta(q^{(n-1)}, x) &= \Big((q_{n-1}, y_{n-1}, d_{n-1}), (q_{n}, y_{n}, d_{n}) \Big)
	\end{align}
	So without loss of generality, we can assume, that the non-deterministic 
	Turing machine makes at most binary choices, which we could code as 
	booleans. Further, if we \emph{don't} want to make a choice, we could make 
	a choice, but end in $q_{reject}$ as the second option, so we can make 
	\emph{exactly} one binary choice per step.

	So let us now reduce the arbitrary problem $A\in\NPTIME$ to $SAT$. Since it 
	is polynomial runtime, there is some $k$ for which the runtime is bound by 
	$p(n) = n^k$.

	Even assuming, that we made a choice in every step, it would be enough to
	give $p(n)$ booleans $c_1, \dots, c_{p(n)}$ to fully specify the trace. This
	will be, what the solver for SAT would then modify to find the solution to
	$A$, the rest is deterministic. 

	The coding, if a trace ends in an accepting state, remains to be done -- 
	which includes coding how a Turing machine works. 

	The state changes over time, and has $\abs{Q}$ exclusive possibilities.
	Then $s^q_{t}$ means, that the machine is in state $q$ at the time $t$. 
	Coding, that the possibilities exclude each other can be done by adding 
	\begin{align}
		StateExclude &= \bigwedge_{q\in Q \atop t=1\ldots p(n)}{
		\bigwedge_{q'\in Q\atop q' \neq q}{s^q_{t} \rightarrow \lnot 
		s^{q'}_{t} }}\\
		&= \bigwedge_{q\in Q \atop t=1\ldots p(n)} 
		\bigwedge_{q'\in Q\atop q' \neq q} \lnot s^q_{t} \vee \lnot 
		s^{q'}_{t}
	\end{align}
	This gives $\abs{Q}^2\,p(n)$ additional input characters -- nothing that would 
	break polynomial input to $SAT$.

	The tape only needs $p(n)$ cells, but for each of the $p(n)$ time steps, 
	therefore we code the tape as the table $T^c_{x, t}$ with $c\in\Gamma$, 
	$x = 1\ldots p(n)$ and $t=1\ldots p(n)$, meaning \emph{the tape cell $x$ 
	contains the character $c$ at the time $t$}. The constraint is of course, 
	that at any given time, the tape at a given cell can only contain one 
	character, but this can be expressed by
	\begin{align}
		TapeExclude &= \bigwedge_{g\in \Gamma}\bigwedge_{x=1\ldots p(n) \atop t=1\ldots p(n)}
		\bigwedge_{g'\in \Gamma\atop g' \neq g}{T^g_{x,t} \rightarrow \lnot 
		T^{g'}_{x,t} }\\
		&= \bigwedge_{g\in \Gamma}\bigwedge_{x=1\ldots p(n) \atop t=1\ldots p(n)} 
		\bigwedge_{g'\in \Gamma\atop g' \neq g} \lnot T^g_{x,t} \vee \lnot 
		T^{g'}_{x,t}
	\end{align}.
	Despite looking huge at first glance, this is still polynomially long in the input.

	We also need to keep track of where the read/write head of the Turing 
	machine is. Perhaps unsurprisingly, we introduce a table $H_{x,t}$, meaning 
	that at the time $t=1\ldots p(n)$ the head is at the position 
	$x=1\ldots p(n)$. Exclusion applies, so we add
	\begin{align}
		HeadExclude &= \bigwedge_{x=1\ldots p(n) \atop t=1\ldots p(n)}
		{H_{x,t} \rightarrow \lnot H_{x,t} }\\
		&= \bigwedge_{x=1\ldots p(n) \atop t=1\ldots p(n)} \lnot H_{x,t} \vee \lnot 
		H_{x,t}
	\end{align}.

	Finally we need to code how the transitions take place. We need to say that
	\begin{itemize}
		\item Deterministically changing state means, that if we were in state $g$ 
			to time $t$ and saw the cell $T_x$ with the character $c$, then in $t+1$,
			we are in the state $g'$ implied by $\delta$.
			\begin{align}
				StateTransition^{q'}(s^q_t, T^c_{x,t}) 
									&= s^q_{t}\wedge T^c_{x,t} \rightarrow s^{q'}_{t+1}\\
									&= \lnot s^q_{t} \vee \lnot T^c_{x,t}\vee s^{q'}_{t+1}
			\end{align} 
		\item Deterministically changing the current cell does the same thing, 
			only with cells instead of states.
			\begin{align}
				CellTransition^{c'}(s^q_t, T^c_{x,t}) 
									&= s^q_{t}\wedge T^c_{x,t} \rightarrow T^{c'}_{x,t+1}\\
									&= \lnot s^q_{t} \vee \lnot T^c_{x,t}\vee T^{c'}_{x,t+1}
			\end{align} 

		\item Deterministically moving on the tape only changes $H_{t+1}$
			\begin{align}
				MoveTransition^d(s^q_t, T^c_{x,t}) 
				&= s^q_{t}\wedge T^c_{x,t} \wedge H_{x,t} \rightarrow H_{x+d,t+1}\\
									&= \lnot s^q_{t} \vee \lnot T^c_{x,t}\vee H_{x,t}\vee H_{x+d,t+1}
			\end{align},
			where $d\in \set{-1,0,1}$
		\item If our current choice bit says $True$, then take the first option $X_t$, 
			else the second option $Y_t$. This could for example be expressed by 
			$(c_t \wedge X_t) \vee (\lnot c_t \wedge Y_t)$.

		\item Plugging this together, we get the coding of the transition 
			function.
			\begin{multline}
				FirstTransition_{x,t} 
				= H_{x,t}\wedge T^c_{x,t}\wedge s^q_{t} \rightarrow
				\\ MoveTransition^{d}(s^q_t, T^c_{x,t}) \wedge 
				\\ CellTransition^{c'}(s^q_t, T^c_{x,t}) \wedge
				\\ StateTransition^{q'}(s^q_t, T^c_{x,t}) \\
			\end{multline}
			if $\delta(c,q) = \left((c', q', d), (c'', q'', d')\right)$ and analogously for 
			the second choice
			\begin{equation}
				Transition = \bigwedge_{t=1}^{p(n)}\bigwedge_{x=1}^{p(n)} 
							(c_t \wedge FirstTransition_{x,t}) \vee 
							(\lnot  c_t \wedge SecondTransition_{x, t})
			\end{equation}

			Even this huge transition table is still polynomial in the length of the input.
	\end{itemize}
	
	Finally, the formula should only be accepted of the end state is $q_{accept}$, which is simply $EndState = s^{q_{accept}}_{p(x)}$.

	Now $Transition\wedge HeadExclude \wedge TapeExclude \wedge StateExclude \wedge EndState$ 
	is the representation of $A$ in $SAT$. Note that no functions (predicates) would have 
	been necessary\footnote{Slightly changing this proof shows then, that predicate 
	logic is actually Turing complete.}.

	With this so-called \emph{gadget} -- something that simulates the 
	computational behaviour of another problem -- we have reduced the problem $A$ 
	to $SAT$. Basically we reduced the problem of calculating $p(n)$ steps on a 
	non-deterministic Turing machine, which is by definition \NPTIME-complete, 
	to the $SAT$ problem.
\end{proof}
This implies, that SAT can express any other \NPTIME problem with only a 
polynomial slowdown. This also means, that SAT could model any \PTIME 
problem, such as checking context free grammar membership.

On the other hand, we saw that SAT can be reduced to the Traveling Salesman 
Problem, which shows its completeness as well.

There are indeed many relevant problems that are \NPTIME-complete\footnote{So 
many in fact, that the author struggled to find any interesting \PTIME-complete
problems}, for example maximizing linear functions over linear constraints in
the domain of integers or optimal scheduling of tasks over multiple processors
just to name two.

\subsubsection{\NPTIME and optimization}
\label{np-opti}
While one should keep in mind, that \NPTIME only
describes decision problems, many \NPTIME-complete
problems actually hide an optimization problem. For
example, if we can determine if the traveling
salesman can do the round-trip with cost of at most
$k$, then we can actually find the optimal path:

\begin{algorithmic}[1]
	\State find least $k_0$, so that the round-trip is possible with binary search over $k$
	\For{each edge $e$ in the graph}
		\State Remove $e$ from the graph
		\State Check if the round-trip cost increases
		\State If so, reinsert $e$
	\EndFor
\end{algorithmic}

After the algorithm finishes, the only edges in the graph are the ones in the round-trip.

Why does this work? First the binary search determines the exact cost of the optimal route and does so in only $\log k_0 \cdot f(x)$, where $f(x)$ is the time that TSP takes. 

The loop then uses that any edge, that is not in the round-trip will leave the cost untouched, even when removed. An edge, that can not be compensated however will increase the cost, when removed. If there are more than one possible round-trip with the same cost, then only one of them will survive the loop, because edges will be removed, if any of the routes is still possible. We would need $\abs{E}\cdot f(x)$ time for the loop.

All in all this algorithm will take $(\log k_0 + \abs{E})\cdot f(x)$ and therefore has only a linear slowdown compared to solving TSP.

\subsubsection{Help, my problem is \NPTIME-complete}
While being (probably) asymptotically very difficult to solve, 
\NPTIME-complete problems are by no means impossible. There are some 
strategies that can be applied to handle them.
\paragraph{\NPTIME-complete does not necessarily mean slow}
In many cases, the precise algorithm to solve the problem works reasonably 
fast in most cases, but explodes for some abnormal cases. If these abnormal 
cases don't occur in normal input data, the algorithm is still save.

For example, if we are solving SAT, but the inputs take only the form of horn 
clauses (for example $\bigwedge x_i \rightarrow y$), then the problem is 
solvable in \PTIME. 

It could also be, that the algorithm runs in $\mathcal{O}((1+\varepsilon)^n)$ 
for some small $\varepsilon$. Then $n$ would have to be very big for it to be problematic.
\paragraph{Parametrization}
The problem might be slow in general, but there are different parameters to 
the problem, that, when fixed, make the algorithm polynomial. Only increasing 
these parameters then give the full problem. 

For example, checking if a given program in the ML language\footnote{Java or
	C++ would be no better as anyone who ever used template code knows. Actually,
	C++ templates are even Turing-complete \cite{veldhuizen2003c++}}
does not violate any typing (i.e.\ a cast would be necessary) is
\NPTIME-complete\footnote{See \cite{downey1999parameterized}}, but if we
parametrize by the number of type definitions in the system, we have merely a
polynomial runtime.
\paragraph{Approximation}
As seen in section~\ref{np-opti}, many \NPTIME-complete problems are actually
optimization problems in disguise. Instead of looking for \emph{the} optimal
solution, often it is enough to settle for a sub-optimal, but good enough
solution.  In this text, we didn't develop the necessary tools to analyse such
inaccurate algorithms, but such algorithms can come --provably-- very close to
an optimal solution, while taking only polynomial time.

\subsection{Other complexity classes}
The complexity classes introduced are of course only scratching the surface 
of the fascinating topic of complexity theory. There are many different modes 
of computation, that do not factor into \PTIME or \NPTIME, for example 
parallelism, which will be of ever greater importance, as the number of cores 
of computers increase, when the sequencial speed cannot. A bit further down 
the road, the quantum computer will get its share.

\paragraph{$\mathtt{NC}$}
stands for Nick's class\footnote{honoring Nick Pippenger} and
has been described as the class of well-parallelizable 
problems\footnote{See \cite{sipser2006introduction}}. It is known that $\mathtt{NC} \subset \PTIME$, but it is unknown, 
whether this inclusion is proper. Similarly to \NPTIME-complete problems, 
\PTIME-complete problems, such as CFG, are analyzed to prove this. 

\paragraph{$\mathtt{BQP}$}
is the class of bounded-error polynomial-time quantum computable decision 
problems. Bounded error compensates for the fact that quantum computation is, 
in order to achieve its full strength, random. Bounding the error means that 
it gives the wrong answer at most $0<\varepsilon<\frac{1}{2}$ of the time, where 
$\varepsilon$ is often arbitrarily chosen to be $\frac{1}{3}$. Given a 
procedure in $\mathtt{BQP}$, it is easy to see, that we can lower the 
probability of error arbitrarily low by running the procedure multiple times 
and taking the average answer.

It is possible to simulate a quantum computation in \PSPACE, and it is 
possible to simulate a deterministic computation on a quantum computer, so 
$\PTIME \subset \mathtt{BQP} \subset \PSPACE$, but again, all inclusions are 
suspected, but not proven, to be proper.

The connection to \NPTIME is unknown, but $\NPTIME\subset \mathtt{BQP}$ would 
imply $\NPTIME\neq \PTIME$.\end{filecontents*}

\begin{filecontents*}{completeness.tex}
\section{Turing-Completeness of a Language}
\label{sec:Turing Completeness}
In the dawn of computer science there were serveral ideas what computable 
means. Does it mean, that a machine can compute it, as Turing suggested? Or 
should we define some functions that should be computable and how they can be
combined to discuss the computability of a problem?

As it turned out, it does not matter -- the problems that can be solved in 
each of them are the same. This was shown by proving that the different 
mechanisms can simulate each other. By extension, a new formulism only needs 
to be able to simulate any of the existing formalisms to be at least as 
powerful as any of them. Thus came the expression \emph{Turing complete} to 
describe, that a certain formalism can build any Turing machine.

This chapter is build as exercises, because solving the problems gives a good 
impression, how one could go about proving other things to be turing complete.

\subsection{The Turing Machine}
The Turing Machine (\TM) is a formalism that focuses on a possible physical 
implementation of a computing machine, although far from what is used today. 
It features a potentially infinite amount of tape on which the machine 
operates and which it uses as storage. From this tape, the machine can read and
write the current cell and move its read-write-head one cell to the left or the
right. Finally, the machine has a finite number of ``states of mind",
comparable to a finite state automaton.

In order to formally analyse the \TM, we can code what such a machine would 
do in the following way:

\begin{defn}
	\label{def:tm}
	A Turing Machine $M$ is a tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$
	where 
	\begin{itemize}
		\item $Q$ are the states of mind the machines can be in.
		\item $\Gamma$ is the tape alphabet, that can be used during the computation.
		\item $\Sigma\subset \Gamma$ is the input alphabet, of which the initial tape is a word.
		\item $\delta:Q\times \Gamma \rightarrow Q\times \Gamma\times \{L, N, R\}$ 
			is the transition function, which codes, how the \TM reacts to a state 
			and the current symbol -- i.e.\ what will be the new state of mind, what 
			symbol will be written and in which direction the head will move.
		\item $q_0\in Q$ gives the initial state.
		\item $q_{accept}, q_{reject}\in Q$ signify that the machine has stopped --
			successfully or not.
	\end{itemize}
\end{defn}

To run a \TM means to give it a word $w\in\Sigma^*$, place the head at some 
cell on the tape and then execute the transitions indicated by the transition
function until we get into any of the states $q_{accept}$ or $q_{reject}$.

\begin{defn}
	A \emph{configuration} of a Turing machine 
	$M=(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$ 
	is then a tuple 
	$c = (tape, s) = (l, h, r, s) \in \Gamma^*\times \Gamma \times \Gamma^*\times Q$. 
	This allows us to define a step that a \TM makes.

	\begin{equation*}
		step(tape, s, (\tilde{h}, \tilde{s}, d)) = \begin{cases}
			(tape, s), &\text{ if } s \in \{q_{accept}, q_{reject}\} \\
			(l, \tilde{h}, r, \tilde{s}) , &\text{ if } d = N\\
			(\tilde{h}\: l, r_1, r_{2, \dots}, \tilde{s}) , &\text{ if } d = R\\
			(l_{2, \dots}, l_1, \tilde{h}\: r), \tilde{s}) , &\text{ if } d = L
		\end{cases}
	\end{equation*}
	
	or in other words: if the head moves \emph{right}, then the rewritten head is pushed to the left stack and the new head is popped off the right stack.

	\begin{figure}[htb]
		\includegraphics[width=0.95\textwidth]{turingtape}
		\caption{Tape of the Turing machine}
	\end{figure}

	We write $c_1 \vdash_{M} c_2$ to denote that $step(c_1, \delta(c_1)) = c_2$ and say that 
	one \emph{step of $M$} transforms $c_1$ to $c_2$.

	Now $c_1 \vdash_M^* c_2$ means that an arbitrary number of steps lead $c_1$ to $c_2$.

	\[
		\interpret[\TM]{M}(tape_1) = \begin{cases}
			tape_2, &\text{ if } (tape_1, q_0) \vdash_M^*(tape_2, q_{accept}) \\
			\bot, &\text{ if there is no such } tape_2
		\end{cases}
		\]
\end{defn}

\begin{example}[Adding two binary numbers]
	When we implement binary addition, we first need to think about how to 
	represent the problem. One of the easiest way to do that is to use {\tt 0} 
	and {\tt 1} to represent the digits, {\tt +} to separate the arguments, 
	{\tt =} ending the tape and assume that the numbers start with the least
	significant number on the left (which is the reverse of the usual notation,
	but easier to calculate with).
	
	\begin{algorithmic}[1]
		\State Start with $carry=0$ in mind.
		\If {tape shows 0}
				\State keep same $carry$ in mind
		\ElsIf {tape shows 1} 
			\If {$carry=0$}
				\State have $carry=1$ in mind
			\ElsIf {$carry=1$}
				\State have $carry=2$ in mind
			\EndIf
		\ElsIf {tape shows +}
			\State keep same $carry$ in mind
			\State have $finished = 1$ in mind
		\EndIf
		\State Move to the right until you hit {\tt +}.
		\If {tape shows 0}
				\State keep same $carry$ in mind
		\ElsIf {tape shows 1}
			\If {$carry=0$}
				\State have $carry=1$ in mind
			\ElsIf {$carry=1$}
				\State have $carry=2$ in mind
			\ElsIf {$carry=2$}
				\State have $carry=3$ in mind
			\EndIf
		\ElsIf {tape shows +}
			\State keep same $carry$ in mind
			\If {$finished=1$}
				\State have $finished = 2$ in mind
			\EndIf
		\EndIf
		\State Move to the right until you hit {\tt =}.
		\State Move to the right until you hit \#.
		\If {$carry=0$}
			\State write {\tt 0}
			\State have $carry=0$ in mind
		\ElsIf {$carry=1$}
			\State write {\tt 1}
			\State have $carry=0$ in mind
		\ElsIf {$carry=2$}
			\State write {\tt 0}
			\State have $carry=1$ in mind
		\ElsIf {$carry=3$}
			\State write {\tt 1}
			\State have $carry=1$ in mind
		\EndIf
		\If {$finished=2$}
			\State You're done
		\Else
			\State move to the far left
		\EndIf
	\end{algorithmic}
	The following shows the state transitions for the main loop of this 
	algorithm, the number of states would nearly double, if the $finished$ 
	states would be taken into account.

	\begin{center}
		\includegraphics[width=0.99\textwidth]{binary-adder}
	\end{center}
\end{example}

Seeing how complex turing machines get, it seems
surprising, that it can code any machine or language.

\subsection{\WHILE is Turing complete}
By definition~\ref{def:power}, we would need a compiler from \TM to \WHILE, 
but by~\ref{thm:power-interpreter}, an interpreter suffices. Implementing such an 
interpreter will be the following exercise.

\begin{Exercise}[title={Interpreter for \TM},label={exc:tm},difficulty=2]
	\Question Show that we can implement a dictionary datastructure in \WHILE\@.
		Implement {\tt insert} and {\tt lookup}.
	\Question Show how you can code the transition function in your map.
	\Question Implement the tape
		\subQuestion Can you keep track of your position in a list with two stacks?
		\subQuestion Implement the left and right movement 
		$\interpret{{\tt left}},\interpret{{\tt right}} : Tape \rightarrow Tape$. Note that the list is 
			only potentially infinite, so you might in actuality run into the current edge.
	\Question Plug the pieces together to implement an interpreter {\tt turing(TM)} for turing machines.
		\subQuestion How many nested {\tt while} loops do you need?
\end{Exercise}
\begin{Answer}
	\Question Since execution time is not an issue, we can implement this as a 
	list of pairs:

\begin{verbatim}
    lookup read (Table.Key) {
      for (K.Value) in Table {
        if [and](K = Key . [not](Result)) {
          Result := Value
        }
      }
    } Write Result

    insert read (Table.(Key.Value)) {
      Outtable := Nil
      for (K.V) in Table {
        if K = Key {
          Outtable := cons (Key.Value) Outtable
        }
        else {
          Outtable := cons (K.V) Outtable
        }
      }
    } write Outtable
\end{verbatim}

If you wanted to get rid of the copying of the whole list, you could also 
just prepend the new pair, since the lookup takes the first match.
	\Question The transition function 
	$\delta: TapeAlphabet \times State \rightarrow TapeAlphabet \times State\times \{L,N,R\}$
	can be coded by taking the alphabet and the states as symbols (or numbers) 
	and storing {\tt ((in-letter.in-state).(out-letter.out-state.direction))} 
	in the map {\tt M}. Now $\delta = \interpret{spec}(lookup.M)$.
	\Question
		\subQuestion We can do that by keeping one stack {\tt left} and one for 
		{\tt right}, the idea being, that the top of the {\tt left} stack is the 
		cell adjacent to the current to the left and the top of {\tt right} is 
		the same to the right. $Tape$ could now look like {\tt (left.current.right)}
		\subQuestion 
\begin{verbatim}
  left read (left.current.right) {
    right := cons current right
    if left {
      current := hd left
      left := tl left
    }
    else {
      current := :blank
    }
  } write (left.current.right)
\end{verbatim}
and analogously for {\tt right}.
	\Question
\begin{verbatim}
  TM-step read (state.(left.current.right).transition-map)) {
    (state.current.dir) := [lookup](transition-map.(state.current))

    if (dir = :left) {
      (left.current.right) := [left](left.current.right)
    }
    if (dir = :right) {
      (left.current.right) := [right](left.current.right)
    }
  } write (state.(left.current.right))

  TM-run read (start-state.tape.transition-map.end-states) {
    current-state := start-state
    while [not]([contains](end-states.current-state)) {
      (current-state.tape) := [TM-step](current-state.tape.transition-map)
    }
  } write (current-state.tape)
\end{verbatim}
	This needs just the main loop.
\end{Answer}

\subsubsection{\TM  is \WHILE-complete}
It could now be, that \WHILE is more powerful than \TM, so that one can 
actually compute more with a \WHILE program than one could with Turing 
Machines alone.

\begin{Exercise}[title={Interpreter for \WHILE in \TM},difficulty=4]
	In this exercise, we will build up a language that can be expressed in \TM 
	and will finally include \WHILE. This is complex, but you might solve 
	many low level implementation problems of programming languages in the progress.
	\Question Show an $n$-taped \TM to the one taped (where $n$ is of course fixed at
		compilation time). A $n$-taped turing machine has $n$ tapes that can be 
		independently moved and writen. \emph{Hint: Unify the tapes and mark where 
		you are.}
	\Question Show that for all \TM's {\tt A} and {\tt B} exists a turing 
			machine {\tt A;B} such that $\interpret[\TM]{A;B}(x) \peq
			\interpret[\TM]{B}(\interpret[\TM]{A}(x))$, i.e. that you can execute
			\TM's one after another.  
	\Question Show that you can implement a {\tt while} construct
		\subQuestion Given a \TM $A$ that prints {\tt T} or {\tt F} on a tape and 
			another \TM $B$, construct a \TM {\tt if A \{B\}} that runs $A$ 
			and then $B$ only if the second tape shows $T$.
		\subQuestion Modify this so that $B$ gets executed as long as $A$ returns {\tt T}.
	\Question Implement the {\tt cons} datastructure on the tape of a turing 
	machine. Note that you can add another tape to ``take notes" by merit of the first question.
		\subQuestion Implement {\tt cons}. \emph{Hint: Be literal about 
		expressions like {\tt cons (cons nil nil) (cons nil nil)}.} 
		\subQuestion Implement {\tt hd} and {\tt tl}.
	\Question Show that you can implement a map, that can be used to save the variables.
		\subQuestion Given a name $a$ on one tape, can you look through a list of 
			pairs and write $b$ on another tape if the coding of $(a.b)$ can be found in list.
		\subQuestion Implement changing the variables.
		\subQuestion Argue, why it is not possible to simulate \WHILE by using 
			one tape per variable.
	\Question Argue, how you could now interpret \WHILE.
\end{Exercise}
\begin{Answer}
	\Question As we have only a limited amount of tape used, we can always move 
		to the far left side of our tape. Now imagine a memory/tape layout like 
		this (in the example for $n=2$):
		\begin{center}
			\includegraphics[width=0.49\textwidth]{multitape}
		\end{center}
		where the $*_n$ means \emph{tape $n$ is currently at the following value}. 
		
		Now design the states and transitions such that
		\begin{algorithmic}[1]
			\ForAll{tape $t$}
				\State move to the far left.
				\State assume state $(s, t)$, where $s$ is the state of the multi-tape machine.
				\State move right until you find $*_t$.
				\State execute the step, that the multi-tape machine would make.
				\State move $*_t$ left or right, if necessary.
			\EndFor
		\end{algorithmic}
		While this leads to a lot more states, it makes it possible to execute 
		more than one tape simultanously.
	\Question {\tt A;B} inherits the end-states of {\tt B} and the 
		starting-state of {\tt A}. The internal states of {\tt A} and {\tt B} 
		need to be disjunct, otherwise the machine could \emph{jump over} from 
		{\tt A} to {\tt B} or vice versa. To ensure that, we call the states in 
		the new machine $(s, A)$ or $(s, B)$, depending on whether $s$ is from 
		{\tt A} or {\tt B}. Now $\delta((s,A), x) = \delta_A(s,x)$ and
		$\delta((s,B), x) = \delta_B(s,x)$. Finally, we connect the two machines:
		$\forall e\in Endstates_A: \delta((e, A), x) = (start_B, x, N)$
	\Question 
		\subQuestion By the first question, we can assume, that {\tt A}  uses exactly 
			one tape, and also that it is different from the one, that {\tt B} 
			uses. Use a similar construction as with the last question:
			\[\forall e\in Endstates_A: \delta((e,A), (\_, T)) = (start_B, (\_, T), (N, N))\]
			and
			\[\forall e\in Endstates_A: \delta((e,A), (\_, F)) = (end, (\_, F), (N, N))\]

			To round things up, connect the ends of {\tt B} to the $end$ state.
		\subQuestion
			Add the following constraint:
			\[\forall e \in Endstates_B: \delta((e,B), \_)= (start_A, \_, (N, N))\]
	\Question
		\subQuestion We introduce the turingletters $\turingletter{nil}, \turingletter{cons(},
			\turingletter{)}, \turingletter{,}$ to the alphabet. Now given two tapes, we first 
			write our return value on a third (empty) tape: first write
			$\turingletter{cons(}$ moving right, then we copy the first tape and add
			$\turingletter{,}$. Finally we copy the second tape and close with $\turingletter{)}$.
			Note here that {\tt cons} and its friends are part of the \WHILE language,
			and $\turingletter{cons(}$, \dots are letters we can put on a tape of a turing
			machine. 
			\subQuestion Here we get a tape on which 
			$\turingletter{cons(}\dots\turingletter{,}\dots\turingletter{)}$ is stored. The problem here is 
			that we need to consider the nesting of {\tt cons}. For this, we use an 
			auxillary tape $aux$ and write a simple stack. 
		\begin{algorithmic}[1]
			\State write $x$ and move to the right on $aux$ if the current input is $\turingletter{cons(}$.
			\State move left on $aux$ if the current input is $\turingletter{)}$.
			\State start copying input to output after encountering $,$.
			\State halt when the $aux$ tape reaches a blank after moving left.
		\end{algorithmic}
			The machine for {\tt hd} then is analogous.
	\subQuestion 
		\begin{algorithmic}[1]
			\ForAll pairs $p$ on the tape
			\EndFor
		\end{algorithmic}

\end{Answer}

These two exercises show, that $\WHILE\epower\TM$. This is important, since 
when showing something to be \WHILE-complete, we don't need to implement the 
\WHILE, but can use \TM instead, which is much simpler.

\subsection{The Halting Problem} \label{sec:halt}
We saw in the introduction, that there are problems, that can be solved in
\WHILE, that can not be solved in \FOR and also that serveral formalisms are
equally powerful to \WHILE, so that one can wonder, if this literally solves
all problems.

Unfortunately, a simple cardinality argument shows that this is not the case: 
There are only countably infinitely many \WHILE programs, as there are only 
so many finite strings, some of which are also \WHILE programs.

The set of functions $\N \rightarrow \N$ however is bigger, as every freshmen 
course in mathematics will show, therefore, there must be some functions that
can not be computed with \WHILE programs. This proof is unsatisfying, as it
does not give a problem that can't be solved. In fact, we would again describe
problems in a finite way, so the argument is mood.

There are however many problems that can explicitely stated but not solved by 
any algorithm. The perhaps most notoric is the halting problem:

\begin{theorem}[Halting Problem]
	There can be no program $\mathtt{halt?}\in \WHILE$ such that 
	\begin{align*}
		\interpret{\mathtt{halt?}}&:\WHILE\times \Input[\WHILE] \longrightarrow \{True, False\}\\
		\interpret{\mathtt{halt?}}&(p, i) \peq\begin{cases}
			False, &\text{ if }\interpret{p}(i)=\bot\\
			True, &\text{ else}
		\end{cases}
	\end{align*}
	So $\mathtt{halt?}$ answers if a given program with a certain input will halt.
\end{theorem}
\begin{proof}
	The proof is a variation of the quintessential uncomputability proof: We 
	assume that we had $\mathtt{halt?}$ and construct a program, that leads to a
	contradiction. The program is a variation of {\tt inverse}:

	\begin{verbatim}
		loopInverse read P {
		  if [halt?](P.P) {
		    while True { }
		  }
		} write P
	\end{verbatim}

	So we should get
	\begin{equation*}
	 \interpret{loopInverse}(p) = \begin{cases}
			\bot, &\text{ if }\interpret{p}(p) \neq \bot\\
			p,& \text{ else} 
		\end{cases}
	\end{equation*}
	what then is $\interpret{loopInverse}(loopInverse)$? Either it loops or it 
	returns, so lets first assume that it loops:

	\begin{align*}
		\interpret{loopInverse}(loopInverse) &= \bot &\Rightarrow \\ 
		\interpret{halt?}(loopInverse) &= False &\Rightarrow \\ 
		\interpret{loopInverse}(loopInverse) &= loopInverse\neq \bot
	\end{align*}

	So on the other hand, what if it didn't loop?

	\begin{align*}
		\interpret{loopInverse}(loopInverse) &\neq\bot &\Rightarrow \\
		\interpret{halt?} &= True & \Rightarrow \\
		\interpret{loopInverse}(loopInverse) &= \bot
	\end{align*}

	Therefore no such \WHILE program can exist.
\end{proof}

Lets reflect on this proof: While it does use \WHILE, it would be easy to 
translate {\tt loopInverse} into other languages and give a halting 
problem for those. In fact, if we can compile {\tt loopInverse} into a 
language, then the new language can not solve its own halting problem, even 
if it was more powerful than \WHILE.

\begin{corollary}
	No language at least as powerful than \WHILE can solve its own halting problem.
\end{corollary}

\subsection{Rice's Theorem}
\label{Rice}
Now maybe the Halting Problem is very special and maybe we're not even that 
interested in the halting of the machine. Maybe we're interested in another 
property $P$, for example ``if the machine halts, its result is the fibonacci 
frequence" or ``the machine leaves this part of the memory untouched".

Such procedures would certainly be useful for specification, security, etc.\ but
Rice proved in 1953 that these procedures cannot exist either.

\begin{theorem}[Rice]
	If there is a property 
	\[ P: (\Input[\WHILE]\rightarrow \Output[\WHILE])\rightarrow \{True, False\}\] 
		such that there are procedures $x$ and $y\in \WHILE$ such that 
		$P(\interpret{x})=True$ and $P(\interpret{y}) = False$ then there can be 
		no procedure $\interpret{p}: \WHILE \rightarrow \{True, False\}$ that corresponds to $P$.

		So if we have a non-trivial property of functions, we cannot write a
		program, that can deduce if the property holds based on the source of a
		procedure alone.
\end{theorem}
\begin{proof}
	We can easily see that the halting problem is a special case of this, but 
	in fact, with a simple construction, all cases come down to it.

	First we note that a procedure $\interpret{z}(x)\peq \bot$ must 
	either have the property $P$ or not. Since $p$ halts, we can check that in 
	advance. Assume that $\interpret{p}(z)=False$, then we can build a program 
	that can solve the halting problem. For this we use that there is a procedure $\mathtt{known-p}$ that satisfies $P$ (by non-triviality). Then we can define

	\begin{verbatim}
maybe-p: read (Q.I.X) {
  [interpreter](Q,I)
  Y := [known-p](X)
} write Y
\end{verbatim}
so that $f = \interpret{spec}(\texttt{maybe-p}, Q, I)$ satisfies the property $P$ if $\interpret{Q}(I) \neq \bot$, otherwise $\interpret{f} \peq \interpret{z}$.

\begin{verbatim}
halt: read (Q,I) {
  known-p-or-z := [spec](maybe-p.Q.I)
  Y := [p](known-p-or-z)
} write Y
\end{verbatim}
	so \texttt{maybe-p} 

	The trick here is that 
	\[
		\interpret{\interpret{spec}(\mathtt{maybe\mhyphen p}, \mathtt{Q}, \mathtt{I})}(x)\peq \begin{cases}
			\interpret{z}, &\text{ if } \interpret{Q}(I) \peq \bot\\
			\interpret{known\mhyphen p}, &\text{ else }			
		\end{cases}
	\]
	
	and therefore 
	\[\interpret{\mathtt{halt}}(q,i)\peq True\Leftrightarrow \interpret{\interpret{spec}(\mathtt{maybe\mhyphen p}, \mathtt{q}, \mathtt{i})} \peq \interpret{\mathtt{known\mhyphen p}}\] $\Leftrightarrow \interpret{q}(i)$ halts and vice versa for the contrary case.
\end{proof}

\subsubsection{So how do we deduce properties about programs then?}
Rice tells us, that it is not possible to deduce for example, 
that the result of a computation is a {\tt String}. Yet the Java compiler 
does it all the time. How is this possible?

The trick is that Rice tells us that the problem can't be solved \emph{in full
generality}. So instead of accepting all programs, we accept only the ones for
which we \emph{can} prove the property. This throws away an infinitude of
perfectly reasonable programs, which would keep the property, only because we
can't prove it, but this way, we can be sure that for any program we accept,
the property \emph{does} hold.

\subsection{The Normal Form Theorem}
\begin{theorem}[Normal Form Theorem]
	Every \WHILE program can be transformed into a \WHILE program with exactly 
	one {\tt while} loop. That is, all the inner constructs are taken from \FOR.
\end{theorem}
\begin{proof}
	Lets call the language of \WHILE programs, that are in the normal form $\WHILE_1$.
	We have seen that we can transform $\WHILE \rightarrow \TM$ and 
	$\TM \rightarrow \WHILE_1$. If we chain these (informal) compilation processes to 
	get a compiler $\WHILE \rightarrow \WHILE_1$.
\end{proof}

\subsection{Church's Thesis}
As mentioned, when the notion of computability was first developed, there 
were competing formalisms, but as it turned out, they were all equally 
powerful. This lead Alonzo Church to conjecture, that what the human sees 
as intuitively computable, is adequately formalized by any of these 
competitors. This is known as Church's Thesis (or Church-Turing Thesis).

\begin{thesis}[Church's Thesis]
	The Turing Machine adequately models what we hold for intuitively computable.
\end{thesis}

We saw that \WHILE too is a competitor, since it is equally powerful to any 
of the other formalisms. We could then formulate it as follows:

\begin{thesis}
	There is no intuitive extension of \WHILE that is more powerful than \WHILE.
\end{thesis}

For example, we could add procedure calls, but that would not make any 
functions computable that were not computable before.

The thesis can not be formally proven, since it connects the informal concept 
of ``intuitively computable" with the formal Turing Machines, however the 
evidence that no-one has since build a computer, that could be exploited to
calculate more than a \TM gives a strong indication, that the Church-Turing
Thesis is true.

\subsubsection{\dots or is it?}
There has been some work, what would happen, if you added certain 
functionalities to Turing Machines (and by extension to \WHILE). 

Turing himself analysed so-called oracle machines, which are basically Turing 
Machines, but can answer specific questions to an oracle on a different tape, 
that would answer if a specific predicate is true for the value of the tape.
The halting problem for Turing Machines is not solvable on a normal \TM, but 
we could add an oracle for it. This would be more powerful than \TM, but it 
is not intuitively clear how one could build such an oracle. Also, we would 
find, that the oracle machine could not solve its own halting problem -- for 
very much the same reason that the original \TM can't solve its own.

Another line of thought is that, when we talk about these formalisms, we 
don't really care if humans find it intuitively computable, but rather that 
we could actually build a machine that computes it. This gives us the 
physical Church-Turing thesis: It is not possible to build a computer that 
can not be simulated on a \TM.

This is a thesis, that \emph{can} be put to the test. While \TM rely on 
classical mechanics, some thought has been put into quantum computing. The 
model that is currently used to build quantum computers (qubits) are however
not stronger than \TM. Faster yes, but not really stronger.

On a larger scale, it is possible to construct a computing device that orbits 
around a rotating black hole. An observer falling into the black hole could 
then observe the infinite computation time of the orbiting machine in
subjectively finite time\footnote{See \cite{etesi2002blackhole} for the whole
discussion on the feasibility and the mathematical proof}. It has however been
noted, that falling into a black hole might not be a good idea.

Finally, the notion of a computer running and halting after some time might 
be flawed. There is no procedure, that can compute $\pi$ to its full extend, 
but many approximation procedures, which can give a arbitrarily precise 
result. Is $\pi$ then intuitively computable?

\subsection{Properties of Turing complete languages}
There are some common elements in the languages that are Turing complete. As we
have seen, any Turing complete language is unable to solve it's own halting
problem -- and by extension any halting problem of a Turing complete language.

Often, it is not obvious, that a certain formalism is Turing complete.

\subsubsection{Conway's Game of Life}
In 1970, the British mathematician John H. Conway devised a ``game" on an 
infinite squared paper: we start with some squares marked as ``alive" and 
then we update the paper in the following way\footnote{The general machine 
	that updates cells only taking the cells neighbors into account is called a 
cellular automata}:

\begin{itemize}
	\item A dead square becomes alive, if it has exactly three 
		neighbors\footnote{diagonal cells are neighbors too},that 
		are alive. Imagine that the cells around it would reproduce and the 
		offspring move into this square.
	\item If the cell is alive, it stays alive if only if it has two or three 
		living neighbors.
\end{itemize}

These extremely simple rules still make up a turing complete language. How 
could one guess that it was?

The first hint is the discrete infinite data structure. We have an unlimited (but 
never infinite) number of squares that are alive. 

This is a necessary condition to be Turing complete. Imagine, that we only
allow a limited data structure, for example a Turing tape that has $n$ cells
and an alphabet of $k$ letters. Each cell has therefore only $k$ possible
configurations, and all the cells combined have only $k^n$ possible states.
Since our machine only has a limited number of states, it can be in, say $m$,
and the head has only $n$ posible positions to be in, after at most 
$n\, m\, k^n$ steps of the machine we must have reached a state that we have
seen before.  The transition function does only depend on these factors,
therefore the loop will start again and nothing new will come of it.

Another hint is that there is no obvious way to deduce certain properties 
without running the whole machine -- ``Is this cell alive after $n$ turns" 
can only be anwered after running $n$ turns.

The real test is of course to implement a turing machine in the game of life, 
but this is beyond the scope of this 
text\footnote{\url{http://rendell-attic.org/gol/tm.htm} has an 
implementation of a turing machine in the Game of Life}.

\paragraph{Why are most programming languages Turing Complete?} % (fold)
\label{sub:Why are most programming languages Turing Complete?}
Not being able to tell if a program will stop nor any other interesting 
properties seems like a bad start. Further, we use mostly algorithms that are
guaranteed to hold in finite time. In short, we seldom truly need a Turing 
complete language, but still every major programming language is Turing 
complete. 

The reason for this is that programmers don't want to think about the halting 
of their programs, because normally they obviously do. Proving that might not 
be trivial and might require the programmer to rewrite the program in such a 
way, that a computer can prove it. So while it would be possible to to 
implement most algorithms in a weaker language, it would be impractical. We
couldn't use any unbounded loop constructs or true recursion.

In some areas, this is acceptable: In formal logic and interactive 
proof-finding, Coq\footnote{\url{http://coq.inria.fr/}} is used, even-though it has 
no unbounded recursion and every piece of code terminates.
% subsection Why are most programming languages Turing Complete? (end)
\end{filecontents*}

\begin{filecontents*}{self.tex}
\section{Self Interpretation\timeestimation{15h}}
\label{sec:self}
Self interpretation is the ability of an formalism to support an
"universal mechanism", that is a program that can interpret a finite
description of any programs in itself and apply it to some input.

For computability, self interpretation can be seen as some kind of gold
standard. This stems from the fact, that the simpler model of
computation, \FOR, are not self interpreting, which changes as soon as self interpretation is added.

\subsection{Recursion Theorem}
\begin{theorem}[Recursion Theorem]
	For any procedure $p\in \WHILE$ there is a procedure $p'\in \WHILE$ so 
	that $\interpret{p'}(x) = \interpret{p}(p'.x)$. This can uniformly be 
	computed by $Y\in \WHILE$, i.e. $\interpret{\interpret{Y}(p)}(x) = \interpret{p}(\interpret{Y}(p).x)$

	Every procedure of $\WHILE$ might as well use its own source code.
\end{theorem}
\begin{proof}
	Instead of giving $Y$ and explaining how it works, here is how one could 
	figure out how to do it\footnote{The proof here is based on \cite{dalenrecursion}}:

	\begin{enumerate}
		\item We start with $\interpret{h}(x):\peq \interpret{spec}(x.x)$, 
			because that gives us 
			\begin{equation*}
				\begin{split}
					\interpret{\interpret{h}(f)}(x)
					&\peq \interpret{\interpret{spec}(f.f)}(x)\\
					&\peq \interpret{f}(f.x)
				\end{split}
			\end{equation*}
			a procedure, that passes a given function as the first argument to 
			itself. This is not the full solution though: It uses the original 
			procedure $f$, not the transformed $\interpret{h}(f)$. Unfortunately, 
			we can't just write 
			$\interpret{h'}(x):\peq \interpret{spec}(x.\interpret{h}(x))$, because 
			that would give the same problem. 
		\item Instead we need to repeat this process 
\begin{multline*}
\interpret{iterate\mhyphen combinator}(combinator.program.x):\peq \\
			\interpret{program}(\interpret{spec}(combinator.(combinator.program)).x).
\end{multline*}			
			What does this do? We run the program and pass as its first argument 
			the code of a program that is modified by the combinator once. This is 
			basically the step from above, only for $combinator$.

			\begin{equation*}
				\begin{split}
					\interpret{iterate\mhyphen combinator}(c.program.x)
					&\peq \interpret{program}(\interpret{spec}(c.c.program).x) \\
					&\text{and to get the own source}\\
					\interpret{\interpret{spec}(c.c.program)}(x)
					&\overset{!}{\peq} \interpret{iterate\mhyphen combinator}(c.program.x)
				\end{split}
			\end{equation*}
		\item From the equation above, we can see, that we need to wrap
			$iterate\mhyphen combinator$ onto itself, 
			$\interpret{Y}(program):\peq \interpret{spec}(iterate\mhyphen
			combinator.(iterate\mhyphen combinator.program))$. 

			This has the desired property:

			\begin{equation*}
				\begin{split}
					\interpret{\interpret{Y}(program)}(x) 
					&\peq \interpret{\interpret{spec}(iterate\mhyphen
				combinator.(iterate\mhyphen combinator.program))}(x)\\
				&\peq \interpret{iterate\mhyphen combinator}(iterate\mhyphen combinator.program.x) \\
				&\peq \interpret{p}(\interpret{spec}(iterate\mhyphen combinator.iterate\mhyphen combinator.program).x)\\
				&\peq \interpret{p}(\interpret{Y}(program).x)
				\end{split}
			\end{equation*}
	\end{enumerate}
\end{proof}

\begin{example}[Quines]
	A \emph{quine}\/ is a program, that outputs its own source. It is a fun 
	exercise for all students of computer science to find a quine in their 
	favourite language. The existence of quines is ensured by the recursion theorem:
	Simply take the program $\interpret{id}(x)\peq x$ and then 
	$\interpret{\interpret{Y}(id)}() \peq \interpret{id}(\interpret{Y}(id))$ 
	is a quine.

	This is unfortunately not how you program a quine. Few languages have a $Y$ 
	procedure, and even if they had, they would use an own internal 
	representation for the $program$ and not the source code. To program 
	a quine, you have to execute the steps of $Y$ by hand. Because \WHILE does 
	not handle strings, it might not be the best choice to implement the quine, 
	so the following is written in {\tt Python}, but the same principle could 
	easily be applied to create a quine for other languages as well.

	\begin{enumerate}
		\item We basically need to return $\interpret{id}(id)$ as a string, but 
			in most languages, it's actually the other way around -- we define a 
			function and can decide to code it (as a string). That is commonly 
			denoted $id(\coded{id})$.
		\item So let's define a function, that does the coding:
\begin{verbatim}
def quote(source):
  return '"'*3 + source + '"'*3
\end{verbatim}
		\item Next, define a procedure, that prints its argument once without 
			quotes, once with the quotes, so basically the literal string ${\tt id(\coded{id})}$.
\begin{verbatim}
def quined(source):
  print source + '(' + quoted(source) + ')'
\end{verbatim}
		\item Finally, we can pass the source of the program to itself:
\begin{verbatim}

def quote(source):
  return '"'*3+source+'"'*3
def quined(source):
  print source + '(' + quote(source) +')'

quined("""
def quote(source):
  return '"'*3+source+'"'*3
def quined(source):
  print source + '(' + quote(source) +')'

quined""")
\end{verbatim}
		This recipe can be ported to many languages, including {\tt C}, {\tt Java} or {\tt Haskell}.
	\end{enumerate}
\end{example}

\paragraph{Why is it called the \emph{recursion} theorem?}
Since we have our own source, we can implement recursion with our interpreter:
\begin{verbatim}
fibonacci read (source.X) {
  if ([or](X = 0, X = 1)) {
    Y := 1
  } else {
    Y := [interpreter](source.(X-1)) + [interpreter](source.(X-2))
  }
} write Y
\end{verbatim}

\subsection{How this translates into logic}
The notion of computability is closely related to that of decidability in 
logic. A statement is \emph{decidable}\/ if either itself or its negation can be 
proven. For many years, it was thought that given a set of axioms strong 
enough every statement in mathematics was decidable, but as we will 
see, that is not the case.

Without going too far into formal logic, I can only say that a successful proof
of a statement can be seen as a trace of a program that finds the statement
from the axioms. The other direction is true as well: A program can be
understood as a description of a constructive proof,\footnote{This equivalence
goes extremely deep, see Curry-Howard correspondence, see
\cite{girard1989proofs} for a thorough introduction to proofs as programs.}.
In short: Formal logic (over the natural numbers) is Turing complete!

Since a proof is nothing but a finite string of symbols, we can code it as a
natural number. But since the domain, on which we use formal logic is natural
numbers, this also means that we can produce predicates about other predicates,
for example {\tt the first argument is a proof of the second argument}.

This is where the recursion theorem comes in: According to it, and this is a 
bit informal, since first, we'd need to translate it into its logical 
equivalent, every predicate can assume, that its first argument is the coding 
of itself.

Then what happens, if we apply this to the predicate {\tt "no number codes a proof 
of the first argument"}? We'd have that {\tt "no number codes a proof of this
statement"}. Assume that it is false, then there \emph{is}\/ a proof for the 
statement, but since the statement is false, we'd have a contradiction in our 
formal system. And if the statement is true? Then there is a true statement 
expressable in the system, that can not be proven. This is known as \emph{Gödel's 
incompleteness theorem}.\end{filecontents*}

\begin{filecontents*}{transforms.tex}
\section{Language Transforms\timeestimation{25h}} % (fold)
\label{sec:transforms}
In this chapter, we'll discuss how we can use the notion of a data 
representation of a program to get a standard toolchain.
\subsection{Language Subsets} % (fold)
\label{sub:Language Subsets}
\begin{defn}
	Let {\tt A} and {\tt B} be two languages such that each valid {\tt B} 
	program is also a valid {\tt A} program. Further 
	$\forall b\in B\, \forall d\in \Input[B]: \interpret[A]{b}(d) = \interpret[B]{b}(d)$

	Then $B$ is a language subset of $A$ (and conversely $A$ is a superset of
	$B$), writen $B \subset A$.
\end{defn}
\paragraph{{\tt C++}  and {\tt C} } % (fold)
\label{par:Cpp and C}
{\tt C++} was designed to be a object-oriented superset to the popular {\tt C}
programming language, so that the new {\tt C++} code could use legacy {\tt C}
code without modification. This notion was important to raise the acceptance of
{\tt C++} with programmers and eased switching.
% paragraph Cpp and C (end)
% subsection Language Subsets (end)
\subsection{Interpreter} % (fold)
\label{sub:Interpreter}
Today programmers and machines seldom speak the same language. Programming in 
machine language is difficult, error-prone and unportable to name only a few 
drawbacks. However it seems reasonable to expect to be able to execute ones 
code nonetheless. Typically, we want our computer to interpret what we mean 
in our high-level programming language. An \emph{interpreter} is such a program.

\begin{defn}
	An \emph{interpreter} of $A$ is a program $interp$ such that
	\begin{align*}
			\interpret[P]{interp}&: A \times \Input[A] \longrightarrow \Output[A] \\
			\interpret[P]{interp}&(a, d) = \interpret[A]{a}(d)
	\end{align*}
\end{defn}

Since parsing is not part of this text, we will assume, that a convenient 
format is already given, like the one introduced in \ref{sub:code-for}.\footnote{If you are interested in the whole story, 
	\cite{aho2007compilers} offers a good introduction into the theory of
	building tools for a new language.}


Interpreters are typically the first step in implementing a language: they 
are relatively easy to write and therefore allow experimenting. The downside 
is that working on the AST and constantly translating typically takes longer 
than an equivalent $A$ program would take. This \emph{overhead} is often 
just a fixed factor, but that factor could be 100, making the interpreted program a 
hundred times slower than the native one.

% subsection Interpreter (end)
\subsection{Compiler} % (fold)
\label{sub:Compiler}
Given the problem of a language that can not be executed directly, there is 
also another approach that can be taken instead of interpretation: We could 
translate the program into a native one in the executable language. This 
process is called \emph{compiling} and the program that does this is a {\em
compiler}.

\begin{defn}
	A \emph{compiler} for the language $A$ into the language $B$ is a program
	$compile\in P$, such that
	\begin{align*}
		\interpret[P]{compile} &: A \longrightarrow B\\
		\interpret[B]{\interpret[P]{compile}(a)} &= \interpret[A]{a}
	\end{align*}

	Normally $P=B$, but if it is \emph{not}, then $compile$ is a so-called {\em
	cross-compiler}.
\end{defn}

What does it mean, if we can express an compiler for $A$ in the language 
$B$? It means, that we can solve any problem in $B$ that can be solved in $A$, 
by compiling the $A$ solution to $B$. This allows us to classify languages 
in the following way.

\begin{defn}
	\label{def:power}
	The language $A$ is \emph{at least as powerful} as $B$, if there is an 
	compiler $\Compiler{B}{A}\in A$. We write $A \lepower B$.

	Similarly, $A$ are \emph{equally powerful} or \emph{Turing equivalent} if $A$
	can compile $B$ and vice versa. We write $A \epower B$.
\end{defn}

\begin{theorem}
	\begin{enumerate}
		\item $\lepower$ is reflexive, that is $A\lepower A$.
		\item $\lepower$ is transitive, that is if $A\lepower B\lepower C$, then $A\lepower C$.
	\end{enumerate}
\end{theorem}
\begin{proof}
	\begin{enumerate}
		\item The compiler is the identity.
		\item \[\Compiler[C]{A}{B} = \interpret[A]{\Compiler{B}{C}}(\Compiler{A}{B})\]
			and then we can compose $\interpret[C]{\Compiler{B}{C}} \circ \interpret[C]{\Compiler[C]{A}{B}}$
	\end{enumerate}
\end{proof}

\subsubsection{How a modern compiler works}
A compiler typically has three stages, a frontend, a middle, and a backend.

The \emph{frontend} transforms the language into a handy format, that is not 
necessarily similar to the input language. Compiler collections may have many 
frontends, that transform all kind of languages into this intermediate format.

The \emph{middle} makes all kind of transformations on the immediate format, 
for example optimizations, type checking, \dots. This is where productive 
work can be done, so much work is typically invested here\footnote{See \cite{aho2007compilers}}.

In the \emph{backend}, the actual output is generated by transforming the 
immediate format to the output language. Separating this from the middle 
makes it easier to work for different output languages.

\paragraph{How the {\tt gcc} is ported} % (fold)
\label{par:gcc}
When a new machine architecture is build, there is the problem that there is 
not yet any compiler for it. The naïve solution would be to write a complete 
compiler in the new machine language, but that would be very cumbersome and 
inefficient to do that for every new processor build.

There are two parts to the problem: on one hand, there is not any compiler, 
that outputs the new machine lanugage and on the other hand, there is no 
compiler that runs on the new machines.

For the first problem, we see that of the three stages of a modern compiler,
only the backend really depends on the output language. Often the backend has 
a general variant that can be parametrized for many architectures.
\footnote{For the whole process of writing a {\tt gcc} backend, see \cite{nilsson2000porting}}

The second problem is nowadays solved by cross-compiling -- when the language 
the compiler is executed in and the output language differ. Another approach 
was to have a minimal (non-optimizing) compiler or an interpreter to do the 
first translation.

% paragraph How the gcc is ported (end)
% subsection Compiler (end)
\subsection{Specializer} % (fold)
\label{sub:Specializer}
While programmers generally know the notions of a compiler and possibly of an 
interpreter, the \emph{specializer} is less well known. \emph{Specialization} 
is the process of fixing a certain value in the source code, even though it 
was written in a way that would have allowed different values. 

\begin{defn}
	A \emph{specializer} $spec$ for the language $A$ is a program 
	\begin{align*}
		\interpret[P]{spec}&:A\times \Input[A]\rightarrow A \\
		\interpret[A]{\interpret[P]{spec}(a, x)}(y) &= \interpret[A]{a}(x.y)
	\end{align*}

	Informally speaking, the specializer moves an argument from the runtime to 
	the compile time.
\end{defn}

Typically, this is part of the optimizations that occur during compilation. For
example, if we encountered the call {\tt fib(n, true)} for the function

\begin{verbatim}
	int fib(int n, bool debug) {
	  if (debug) printf("Call with %d", n);

	 	if (n == 0 || n == 1) return 0;

	 	return fib(n-1) + fib(n-2);
	}
\end{verbatim}
then the specializer might remove the first test and just leave the {\tt 
printf}, which is more efficient and removes the ``loose end'' {\tt debug}  
from the runtime.

For a specializer to work, it has to prove, that a certain part of the 
program only depends on the given value and static data and then evaluate 
that. This sounds easier than it is: 
\begin{example}
	Given the expression {\tt a+b+1}, where {\tt a} is statically known to be $5$, 
	we know that it could be specialized to {\tt b+6}, but if we interpreted it 
	as {\tt (a+b)+1} \emph{or} {\tt a+(b+1)}, no subexpression would be
	independent of {\tt b}.
\end{example}
For a deeper look at the applications and implementations of specializers, 
see \cite{jones1993partial}.


\subsubsection{Futamura Projections} % (fold)
\label{ssub:Futamura Projections}
The notion of a specializer as a transformer of source code has lead to some 
interesting observations by Yoshihiko Futamura
\footnote{\cite{futamura1999partial}}, which are now known as the Futamura
Projections:

\begin{enumerate}
	\item \begin{align*}
			\interpret[P]{\interpret[P]{spec}(\Interpreter{A}, source)}(inp)
			&= \interpret[P]{\Interpreter{A}}(source.inp) \\
			&= \interpret[A]{source}(inp)
	\end{align*}
		So we can get an executable, if we specialize the interpreter with the 
		source of our program.
	\item \begin{equation*}
			\begin{split}
			compiler_{A\rightarrow P} &= \interpret[P]{spec}(spec, \Interpreter{A}) \\
				\interpret[P]{\interpret[P]{spec}(spec, \Interpreter{A})}(source)
				&= \interpret[P]{spec}(\Interpreter{A}.source)
		\end{split}
	\end{equation*}
		Therefore we can get a compiler, if we specialize the specializer with the interpreter.
	\item \begin{align*}
			\interpret[P]{\interpret[P]{spec}(spec.spec)}(\Interpreter{A})
			&= \interpret[P]{spec}(spec.\Interpreter{A})
	\end{align*}
		So we can get a program, that takes an interpreter for any language $A$ 
		and produces a compiler for $A$ from it.
\end{enumerate}

This approach would make it as easy to generate a compiler as it is to 
program an interpreter, so why are not all compilers generated this way?

As discussed, finding specializable parts of the interpreter is not as easy 
as the equations make it look, so it is not surprising, that a correct 
specializer will not catch every possible optimization. In fact, optimizing 
the intermediate format allows many other optimizations besides the
specialization and so a pragmatic compiler writer will prefer to do such 
things by hand, instead of enhancing the specializer.

% subsubsection Futamura Projections (end)
\paragraph{The PyPy project} % (fold)
\label{par:ThePyPyproject}
\begin{example}
	The {\tt PyPy} project is an attempt to implement the popular {\tt
	Python}\footnote{\url{http://python.org/}} itself in a subset of {\tt Python}
	(called {\tt RPython}). Since {\tt Python} is an interpreted language, it
	would seem that this approach would lead to very slow execution, but that is
	not the case: PyPy uses Just-In-Time (JIT) specialization and compilation
	techniques in part described in \cite{psycho}.

	While the approach described in \ref{sub:Specializer} is understood to be 
	executed before the actual program is run, it is also possible to run it 
	in parallel to the actual computation: Now the specializer can use 
	statistical information on the values. For example, while it might not be 
	obvious from the source that a certain value is constant and therefore a 
	static specializer might fail to set in, but a dynamic specializer can 
	determine this and produce a specialized function to call.

	For a highly dynamic language like {\tt Python}, it can lead to a hundredfold 
	speedup for very repetitive arithmetics\footnote{\cite{psycho}}.
\end{example}

% paragraph The PyPy project (end)

\subsubsection{Theoretical Results}
\label{ssub:spec theo}
Proposing that we can statically fix arguments in our program leads important results:
\begin{theorem}
	\label{thm:power-interpreter}
	If there is an interpreter $\Interpreter{B}\in A$ then $B\leq A$.
\end{theorem}
\begin{proof}
	By the second Futamura projection 
	\[\Compiler{B}{A} = \interpret[A]{spec}(spec, \Interpreter{B})\]
\end{proof}

Note however that the reversal is not necessarily true: For example, we know, that 
\FOR is has no $\Interpreter{\FOR}$, but $\FOR \leq \FOR$ still holds. We 
will see later that a self-interpreter allows us to identify the two notions.
% subsection Specializer (end)
\end{filecontents*}

\begin{filecontents*}{for.tex}
\section{The {\tt FOR} language}
\label{sec:FOR}
\begin{table}[htb]
	\begin{grammar}
		<expression> ::= 
							`nil' 
				\alt 	`cons' <expression> <expression>
				\alt 	`hd' <expression>
				\alt 	`tl' <expression>
				\alt		`:' <symbol-name>
				\alt		<expression> `=' <expression>
				\alt 	<variable>

		<statement-list> ::= <statement> ;\alt <statement> ; <statement-list>

		<block> ::= `{' <statement-list> `}'

		<statement> ::=
							<variable> `:=' <expression>
				\alt	`if' <expression> <block> <else-block>
				\alt	`for' <variable> `in' <expression> <block>
			
				<else-block> ::= <empty> \alt `else' <block>
				
				<program> ::= <name> `read' <variable> <block> `write' <variable>
	\end{grammar}
	\caption{The \FOR syntax \label{tab:FOR-syntax}}
\end{table}

\subsection{The Elements} % (fold)
\label{sub:TheElements}
The \FOR language contains only very basic commands, but they can be combined
to implement a huge number of algorithms. As the data structure, we choose 
the humble $ConsCell$, that contains only a reference as the head and 
another as the tail\footnote{An observant reader will notice that this
structure stems from the building of linked lists.}. Because the head and the tail point to \emph{something}, we also need some 
atomic data, that it can point to. We introduce $Nil$, which points at 
nothing and is the basis for the $ConsCell$ data. As a short cut notation, let 
\[[a_1, a_2, \dots, a_n] := ConsCell(a_1, ConsCell(a_2, \dots ConsCell(a_n, Nil)\dots )).\]
\begin{figure}[htb]
	\begin{center}
		\includegraphics[height=3cm]{conscell}
	\end{center}
	\caption{The $ConsCell$}
\end{figure}

To make the programs easier to decipher, we also use named symbols, which are
not strictly necessary: we could also use lists to code them.

The formal definitions of the semantics of \FOR can be seen in the tables 
\ref{tab:for-sem-exp} and \ref{tab:for-sem-stat}, but to gain familiarity 
with semantic functions, the following sections will explain the meaning of 
the definitions.

In the \FOR language, when we write the expression $\mathtt{cons}\: e_1\: e_2$, it
will give us such a $ConsCell$ with the evaluation of $e_1$ in the head and the
evaluation of $e_2$ in the tail. The expression $\mathtt{hd}\: e$ yields the head of
the evaluation of $e$ and $\mathtt{tl}\: e$ its tail. The expression 
$\mathtt{nil}$ just gives back $Nil$\footnote{
	Note the difference: $\mathtt{nil}$ is an expression in the language,
	literally the string {\tt nil}, but $Nil $ is the mathematical entity.
	Similarly you should not mix up $\mathtt{cons}\: a\: b$ and $ConsCell(x, y)$}.
We also want to refer to stored values, so an identifier (e.g. {\tt X}) can
also be an expression, the evaluation of which depends on the current variable
bindings.

There are very few types of statements in \FOR, just three to be precise: The 
first is the \emph{assignment} $\mathtt{X}\:\mathtt{:=}\: e$, which assigns the variable {\tt X}
the evaluation of $e$. Later, when {\tt X} is used in an expression, it 
will reproduce this value. The second is the classic {\tt if} statement, that 
only executes its first block, if the expression does \emph{not} return {\tt nil} 
and the else-block -- if any -- otherwise. Finally, there is the eponymous 
$\mathtt{for}\: I\: \mathtt{in}\: e\: block$ loop, that works as follows:

\begin{enumerate}
	\item On first entering the loop, the expression $e$ is evaluated and stored.
	\item If the evaluation is $Nil$, we are done.
	\item Otherwise the block is evaluated with the head of $e$ bound to the 
		variable name $I$.
	\item Then this procedure is run again with the tail of $e$.
\end{enumerate}

\begin{table}
	If $c = \{(name_i, value_i)\}$ is the variable binding at the time of the evaluation:
	\begin{align}
			\interpret{\mathtt{nil}}(c) &= Nil \\
			\interpret{\mathtt{:}a}(c) &= symbol_a\\
			\interpret{\mathtt{cons}\: A\: B}(c)=\interpret{\mathtt{(}A\mathtt{.}B\mathtt{)}} &=  ConsCell(\interpret{A}(c), \interpret{B}(c)) \\
			\interpret{\mathtt{hd}\: A}(c) &= \begin{cases}
				x, &\text{ if }\interpret{A}(c) = ConsCell(x, y)\\
				\bot, &\text{ otherwise}
			\end{cases}\\
			\interpret{\mathtt{tl}\: A}(c) &= \begin{cases}
				y, &\text{ if }\interpret{A}(c) = ConsCell(x, y)\\
				\bot, &\text{ otherwise}
			\end{cases}\\
			\interpret{A\:\mathtt{=}\: B}(c) &= \begin{cases}
				ConsCell(Nil, Nil), &\text{ if } \interpret{A}(c) = \interpret{B}(c)\\
				Nil,&\text{ otherwise}
			\end{cases}\\
			\interpret{name}(c) &= \begin{cases}
				x, & \text{ if } (name, x) \in c\\
				Nil, & \text{ otherwise }
			\end{cases}
	\end{align}
	\caption{Semantics of \FOR expressions}
	\label{tab:for-sem-exp}
\end{table}
\begin{table}
	If $c = \{(name_i, value_i)\}$ is the variable binding at the time of the evaluation:
	\begin{align*}
		\interpret{name\: := a}(c) &= (c\setminus \{(name, x)\}) \cup (name, \interpret{a}(c)) \\
		\interpret{\mathtt{if}\: a\: block_1\: \mathtt{else}\: block_2}(c) &= \begin{cases}
			\interpret{block_2}(c), &\text{ if }\interpret{a}(c)= Nil\\
			\interpret{block_1}(c), &\text{ otherwise}
		\end{cases}\\
		\interpret{\mathtt{if}\: a\: block}(c) &= \begin{cases}
			c, &\text{ if }\interpret{a}(c)= Nil\\
			\interpret{block}(c), &\text{ otherwise}
		\end{cases}\\
		\interpret{\mathtt{for}\: a\:\mathtt{in}\: v\: \{\: b\: \}}(c) &= \begin{cases}
			c, &\text{ if }\interpret{v}(c) = Nil\\
			(\interpret{\mathtt{for}\: a\: \mathtt{in}\: \interpret{\mathtt{tl}\: 
		v}(c)\:\{\: b\: \}}\circ\interpret{b}\circ\\ \qquad \interpret{a\: \mathtt{:=}\: 
		\mathtt{hd}\: v})(c), &\text{ otherwise}
		\end{cases}
	\end{align*}
	
	\caption{Semantics of \FOR Statements}
	\label{tab:for-sem-stat}
\end{table}
\subsection{Coding \FOR programs}
\label{sub:code-for}
Some of the more interesting programs in the \FOR language use other \FOR programs 
as their input, for example a program $composition$ that takes a program $p$ and another program $q$, such that $\interpret{\interpret{composition}(p, q)}(x) = \interpret{p}(\interpret{q}(x))$. In order to create such a program, we need some interpretation \lineofthought{This would be a good point to start talking of functors, but then again, nobody wants to hear that in a practical text} $\coded{.}: \FOR \rightarrow \Input[\FOR]$.

One possible way to go about this is interpreting blocks and expressions as lists and denote them:
\begin{table}
\begin{align*}
	\coded{\mathtt{nil}} &= symbol_{nilexp}\\
	\coded{\mathtt{:}a} &= [symbol_{symbol}, symbol_a] \\
	\coded{\mathtt{cons\: a\: b }} &= [symbol_{cons}, \coded{a}, \coded{b}]\\
	\coded{\mathtt{hd}\: a} &= [symbol_{hd}, \coded{a}]\\
	\coded{\mathtt{tl}\: a} &= [symbol_{tl}, \coded{a}]\\
	\coded{variable} &= [symbol_{var}, symbol_{variable}] \\
	\coded{a\: \mathtt{:=}\: e} &= [symbol_{assign}, symbol_a, \coded{e}]\\
	\coded{\mathtt{\{ } b_1 \mathtt{;} b_2 \mathtt{;} \dots \mathtt{;} b_n \mathtt{\} }} &= [\coded{b_1}, \coded{b_2}, \dots, \coded{b_n}]\\
	\coded{\mathtt{for}\: a\: \mathtt{in}\: e\: block} &= [symbol_{for}, symbol_a, \coded{e}, \coded{block}]\\
	\coded{\mathtt{if}\: e\: if\mhyphen block\: else\mhyphen block} &= [symbol_{if}, \coded{e}, \coded{if\mhyphen block}, \coded{else\mhyphen block}]
\end{align*}
\caption{Coding the \FOR language in its own data}
\end{table} 
\subsection{\FOR computability}
The probably most important property of the \FOR language is that programs in 
it always terminate. The reason for this is, that upon entering the for loop, 
the number of repetitions is fixed as the length of the evaluated expression. 
Since we can't build an infinite expression in the finite time before the 
loop, the program terminates.

When experimenting with the language, one quickly finds, that many important 
functions are \FOR computable:

\begin{itemize}
	\item Constant functions.
	\item Addition.
	\item Multiplication -- as repeated addition.
	\item Exponentiation -- as repeated multiplication.
	\item Unary/binary conversion.
	\item Testing if a given number is prime.
	\item ...
\end{itemize}

As we can see, it is relatively simple to generate huge numbers using the 
\FOR language and then generate lists with that length.

At first glance it seems that any computation can be defined this way, but 
sadly, that is not the case.

Intuitively the interpretation of a \FOR program should be computable. We can 
do it in an algorithmic way and so it is only reasonable to expect \FOR to be 
able to interpret itself. As we will see, that can not be the case:

\begin{theorem}
	There is no \FOR program $exec$ that takes $ConsCell(program, input)$ as its 
	argument and returns $\interpret{program}(input)$.
\end{theorem}
\begin{proof}
Assume, there was a procedure in \FOR $exec$ that takes $(program.input)$ as 
its argument. Now the following procedure would surely be a \FOR program too:

\begin{verbatim}
inverse read X {
  result := [exec](X.X)
  if result {
    Y := FALSE;
  } else {
    Y := TRUE;
  }
} write Y
\end{verbatim}

We have 
\[ \interpret{inverse}(program) = \begin{cases}
		\mathtt{TRUE}, &\text{ if }\interpret{program}(program) = \mathtt{FALSE} \\
		\mathtt{FALSE}, &\text{ otherwise }
	\end{cases} \]

It outputs {\tt TRUE} iff the given program outputs {\tt FALSE}. What then 
is \sloppy$\interpret{inverse}(inverse)$ ? Assume first that it is 
{\tt TRUE}, then by definition it is {\tt FALSE} -- and vice versa! So it 
neither returns {\tt TRUE} \emph{nor} {\tt FALSE}. The only way that would 
work would be if it didn't return anything at all, but as we have seen, all 
\FOR programs terminate in finite time, so that can not be the case. 
Therefore {\tt inverse} can not be a \FOR program and by extension {\tt exec} 
is not a \FOR program. 
\footnote{This is the quitessential uncomputability 
	proof: A coding of the function is given that can be evaluated, but running 
  the program on itself leads to complications.}
\end{proof}

This is unfortunate, not only because we have seen that there are functions 
that are not \FOR computable, but that in general, any language that supports 
the building blocks of {\tt inverse} either doesn't support 
self-interpretation or it contains programs that will not halt.

As we try to capture \emph{all} intuitively computable functions, it is not 
acceptable to leave self-interpretation out, so in the next chapter, we will 
explore a language that will contain non-halting programs.

\subsection{The \FOR in real programming languages}
It turns out, that while the {\tt for} keyword exists in most languages in 
one form or another, few acurately model the \FOR languages intention. 
Foremost most languages cheat around the property of \FOR loops always 
terminating: In C-like languages, the loop variable is not immutable and therefore
\begin{verbatim}
	for (int i = 0; i < 10; i++) {
	  // ...
	}
\end{verbatim}
might very well not terminate, if {\tt i} is decremented in the body. 
Iterator-based loops can be tricked by implementing an iterator that does not 
halt, i.e. produces a new value on any {\tt next}.

\subsection{The \FOR in mathematics and logic}
The \FOR computable functions match a category of functions known as 
\emph{primitive recursive}. A function is \emph{primitive recursive}, if it is either
\begin{enumerate}
	\item A successor function $S_i(x_1,\dots,x_n) = x_i+1$
	\item A projection function $P_i(x_1,\dots,x_n) = x_i$
	\item In the form of primitive recursion:
		\begin{equation*}
			f(n,x_1,\dots,x_n) = \begin{cases}
				g(x_1,\dots,x_n), &\text{ if }n=0\\
				h(f(n-1, x_1, \dots, x_n), x_1,\dots,x_n),&\text{ else}
			\end{cases}
		\end{equation*}
		Where $g$ and $h$ are primitive recursive.
\end{enumerate}
It is easy to see that \FOR can compute any primitive recursive function:
The successor function and the projections are trivial, for the primitive 
recursion, we have programs $\interpret{G}=g$ and $\interpret{H}=h$ by 
induction assumption. 

\begin{verbatim}
F read NX {
  N := hd NX
  Xs := tl NX
  Repetitions := [unary](N)
  Result := [G](Xs)
  Counter := 0
  for I in Repetitions {
    Result := [H](Result.Xs)
  }
} write Result
\end{verbatim}

\begin{Exercise}[title={\FOR computable functions are primitive recursive}]
	\Question Can you model an {\tt if} statement in primitive recursion?
	\Question How would you implement a {\tt for} loop with primitive recursion?
	\Question How could we model assignment in the primitive recursive functions?
	\Question \emph{Difficult:} Show that $ConsCell$ can be modelled in the 
		natural numbers, with primitive recursive functions handling $\mathtt{cons}$, 
		$\mathtt{hd}$ and $\mathtt{tl}$.
\end{Exercise}
\end{filecontents*}

\begin{filecontents*}{introduction.tex}
Computability and complexity are in some way the basics of what computer
science is about. Where algorithmics might answer what the currently best known
solution to a problem is, computability theory says if a solution can exist and
complexity theory gives the problem (not the concrete algorithm!) a general
assessment of its difficulty, i.e. no algorithm can solve the problem faster 
than its inert complexity.

For this, one needs an idea what a problem is, and when it is solvable. A 
problem can be understood as getting some kind of input data $x\in \Input[A]$ 
and needing to produce an output value $y\in \Output[A]$, in other words: 
computing a function $f:\Input[A] \rightarrow \Output[A]$\footnote{Equivalently, 
a problem can be characterized as deciding if $x\in^? B$.}.

A problem is then considered solvable, if there is in some way a solution to 
it, but what a solution looks like, divides the minds: 

\paragraph{Turing and his machines}
Turing's approach is a very mechanical one: A machine that has memory in the 
form of an arbitrarily large tape and is in a certain state. Depending on the 
tape's content at the current position and the current state, it can write to 
the tape, change its state and move one cell to the left or to the right.

\paragraph{Kleene composes functions}
Kleene held it intuitively computable that there are some simple functions 
such as the projections, the constant functions, and the successor are 
computable and that the composition of two computable functions is again 
computable. Finally every function can be coded and the codes can then be executed.

\paragraph{Markov rewrites strings}
Markov noted that executing an algorithm is basically nothing but rewriting a 
string (the memory) according to some predefined rules.

\paragraph{Programing languages}
While each of these approaches is interesting in their own right, they do not 
reflect the intuitions of a modern computer scientist, who already knows 
about programming languages and is closer to them then to building machines 
or even mathematical constructs.

Nearly all modern languages try to capture the full spectrum of solvable 
problems. For the purposes of this text, the \WHILE language will 
serve as a minimal coding for computability.

\subsection{What is a programming language?} % (fold)
\label{sub:What is a programming language}
We have an intuitive notion of what a programming language is, which probably
goes like "A language, in which programs can be written" or "An executable
language". But what makes a string of letters executable? 

The difference is just that we know how a programming language should be 
interpreted, i.e.\ a program can be mapped to a function and thus in the 
realm of mathematics.

\begin{defn}
	A partial function from $A$ to $B$ is a function 
	\[ f:A\rightarrow B_\bot = B\cup \{\bot\}\]
	where $\bot$ signifies that no value exists for that input.

	For example $\interpret{A}(x) = \bot$ means, that the program $A$ does 
	either give an error or does not terminate on the input $x$.
\end{defn}

\begin{defn}
	A \emph{semantic function} $\interpret[A]{.}$ for a programming language $A$ is a function
	\[ \interpret[A]{.}: A \rightarrow \left( \Input[A] \rightarrow 
	\Output[A]\cup \{\bot\}\right)\]
	where $\bot$ signifies either an error or that the function does not return.
	Then the function $\interpret[A]{.}$ takes a valid $A$ program and 
	gives a function that maps inputs for $A$ programs to outputs (if any).
\end{defn}
The semantic function defines what a program \emph{means}, while its syntax 
defines \emph{how it should look like}. It typically uses other functions to 
denote parts of the program. 
\begin{example}
	As a part of a programming language, we want to know the semantics of 
	$\mathtt{572}$. Note that $\mathtt{572}$ is a string, not the number. However 
	$\interpret[dec]{\mathtt{572}}=5\cdot 100+7\cdot 10+ 2$ \emph{is} the number, not the string. 
\end{example}

When describing a programming language, the terms \emph{expression} and {\em
statement} will be used often. An \emph{expression} is a representation of 
data used in the language. It returns a value and can depend on the state of 
the computation, e.g. to evaluate variables. Some expressions even change the 
state of the computation. A \emph{statement} does not return a value and just 
changes the state.
\begin{example}
	In the assignment in a {\tt C}-like language {\tt int four = 2+2;}, the 
	whole line is a statement since it introduces a new variable name, that 
	can be referenced. {\tt 2+2} is an expression that returns $4$. After this 
	line, {\tt four} is an expression as well and will return the current value 
	of the variable.
\end{example}

% subsection What is a programming language (end)
\end{filecontents*}

\begin{filecontents*}{while.tex}
\section{The {\tt WHILE} Language\timeestimation{15h}}
\label{sec:WHILE}
In the last chapter we saw an example of a function that is not computable 
with a \FOR program\footnote{The semantic function of \FOR}. However with a 
simple addition to the language, we gain all we need for a language.

The new statement is called $\mathtt{while}\: e\: \{ block \}$, and it does what one would expect:

\begin{itemize}
	\item It takes an expression $e$ and a block $block$.
	\item If the evaluation of the expression yields {\tt nil}, it does nothing.
	\item Otherwise, it executes the block and repeats this procedure.
\end{itemize}

\begin{equation}
	\interpret{\mathtt{while}\: e\: block}(c) = \begin{cases}
		c, &\text{ if }\interpret{e}=Nil\\
		(\interpret{\mathtt{while}\: e\: block} \circ \interpret{block})(c), &\text{otherwise}
	\end{cases}
\end{equation}

This new statement does not necessarily terminate, in fact {\tt WHILE 
(nil.nil) \{\}} would never halt. This means, that the semantic function 
does not give a total function back -- for some inputs the interpretation of 
the source does not halt.

Looking back at the proof of the uncomputable function in \FOR called
$inverse$, that took a program and returned the boolean inverse of that
programs output when run with itself as input. We asked what
$\interpret{inverse}(inverse)$ would be. Since it can't be $TRUE$ nor
$FALSE$, it must be $\bot$. This can also be seen in that
$\interpret{eval}(inverse.inverse)$ is just an infinite recursion. 

Of course it could be that while this proof does not work, something else might
prevent us from implementing the {\tt eval} procedure. As we will see in
~\ref{sec:self}, that is not the case.

Part of this work is an implementation of the \WHILE programming language, which can be found at \url{https://github.com/zombiecalypse/Bachelor-Thesis/wiki}.
\end{filecontents*}

\begin{filecontents*}{main.tex}
\documentclass[oneside]{book}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{ucs}
\usepackage{cite}
\usepackage{newclude}
\usepackage{stmaryrd}
\usepackage[colorlinks]{hyperref}
\usepackage[titletoc,page]{appendix}
\usepackage[stable]{footmisc}
\usepackage{xifthen}
\usepackage{graphicx}
\usepackage{varioref}
\usepackage{syntax}
\usepackage{exercise}
\usepackage{xspace}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

\newcommand*{\pfunc}{\xrightarrow{p}}
\newcommand*{\peq}{\simeq}
\newcommand*{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand*{\listOf}[1]{\left< #1 \right> }
\newcommand*{\coded}[1]{\ulcorner #1 \urcorner }
\newcommand*{\turingletter}[1]{\left< #1 \right> }
\newcommand*{\WHILE}{\ensuremath{\mathtt{WHILE}}\xspace}
\newcommand*{\FOR}{\ensuremath{\mathtt{FOR}}\xspace}
\newcommand*{\TM}{\ensuremath{\mathtt{TM}}\xspace}
\newcommand*{\NTM}{\ensuremath{\mathtt{NTM}}\xspace}
\newcommand*{\N}{\ensuremath{\mathbb{N}}\xspace}
\newcommand{\lepower}{\leq}
\newcommand{\gepower}{\geq}
\newcommand{\epower}{\equiv}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\TIME}[1][]{\ensuremath{\mathtt{TIME}\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\NTIME}[1][]{\ensuremath{\mathtt{NTIME}\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\SPACE}[1][]{\ensuremath{\mathtt{SPACE}\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\NSPACE}[1][]{\ensuremath{\mathtt{NSPACE}\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\LOGTIME}{\ensuremath{\mathtt{LOGTIME}}}
\newcommand{\LOGSPACE}{\ensuremath{\mathtt{LOGSPACE}}}
\newcommand{\PTIME}{\ensuremath{\mathtt{PTIME}}\xspace}
\newcommand{\NPTIME}{\ensuremath{\mathtt{NPTIME}}\xspace}
\newcommand{\PSPACE}{\ensuremath{\mathtt{PSPACE}}}
\newcommand{\EXPTIME}{\ensuremath{\mathtt{EXPTIME}}}
\newcommand{\EXPSPACE}{\ensuremath{\mathtt{EXPSPACE}}}
\mathchardef\mhyphen="2D
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\reducesTo}{\leq}

% Note Commands
\newcommand{\citationneeded}{{\em (citation needed) } }
\newcommand{\lineofthought}[1]{{\bf [#1] }}
\newcommand{\TODO}{\ensuremath{\left<\mathbf{TODO}\right> }}
\newcommand{\DONE}{}

% Disabled Note Commands
\newcommand{\timeestimation}[1]{}
%\newcommand{\citationneeded}{}
%\newcommand{\lineofthought}[1]{}
%\newcommand{\TODO}{}

\newcommand{\interpret}[2][]{\ensuremath{\left\llbracket #2 \right\rrbracket
	\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\Input}[1][]{\ensuremath{I
	\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\Output}[1][]{\ensuremath{O
	\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\Compiler}[3][]{\ensuremath{compile_{#2\rightarrow #3}
	\ifthenelse{\isempty{#1}}{}{^{#1}}}}
\newcommand{\Interpreter}[2][]{\ensuremath{interpret_{#2}
	\ifthenelse{\isempty{#1}}{}{^{#1}}}}
\newcommand{\measuretime}[2][]{\ensuremath{T_#2
	\ifthenelse{\isempty{#1}}{}{^{#1}}}}
\newcommand{\measurespace}[2][]{\ensuremath{S_#2
	\ifthenelse{\isempty{#1}}{}{^{#1}}}}
\newtheorem{prop}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{thesis}{Thesis}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem*{example}{Example}




\author{Aaron Karper}
\newcommand{\titletext}{A Programming Language Oriented Approach to Computability}
\title{\titletext}
\date{}
\begin{document}
\begin{titlepage}
  \let\footnotesize\small
  \let\footnoterule\relax
  \let \footnote \thanks
  
  \begin{center}%
	\vspace{10em}
  	{\huge{\textsc{\titletext}}\\}%
  	\vskip 5em%
	{\LARGE{Bachelorarbeit\\der Philosophisch-naturwissenschaftlichen
  	 Fakult\"at der Universit\"at Bern}\par}%
  	\vskip 12em%
  	{\Large{vorgelegt von}\par}%
  	\vskip 1.5em%
  	{\Large{Aaron Karper}\par}%
  	{\Large{2013}\par}%
  	\vskip 6em%
  	{\Large{Leiter der Arbeit:}\par}%
  	{\Large{Professor Dr. Thomas Strahm}\par}%
	{\Large{Institut f\"ur Informatik und angewandte Mathematik}\par}%
  \end{center}\par	
  \thanks
  \vfil\null
\end{titlepage}

\tableofcontents
\chapter{Introduction}
	\include{introduction/introduction/introduction}
	\include{introduction/for/for}
	\include{introduction/while/while}

\chapter{Computability}
	\include{computability/transforms/transforms}
	\include{computability/completeness/completeness}
	\include{computability/self/self}

\chapter{Complexity}
	\include{complexity/complexity/complexity}
	\include{complexity/langcomplexity/langcomplexity}

\bibliography{biblio}{}
\bibliographystyle{plain}

%\begin{appendices}
	%\include*{appendix}
%\end{appendices}
\end{document}
\end{filecontents*}

\documentclass[oneside]{book}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{ucs}
\usepackage{cite}
\usepackage{newclude}
\usepackage{stmaryrd}
\usepackage[colorlinks]{hyperref}
\usepackage[titletoc,page]{appendix}
\usepackage[stable]{footmisc}
\usepackage{xifthen}
\usepackage{graphicx}
\usepackage{varioref}
\usepackage{syntax}
\usepackage{exercise}
\usepackage{xspace}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

\newcommand*{\pfunc}{\xrightarrow{p}}
\newcommand*{\peq}{\simeq}
\newcommand*{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand*{\listOf}[1]{\left< #1 \right> }
\newcommand*{\coded}[1]{\ulcorner #1 \urcorner }
\newcommand*{\turingletter}[1]{\left< #1 \right> }
\newcommand*{\WHILE}{\ensuremath{\mathtt{WHILE}}\xspace}
\newcommand*{\FOR}{\ensuremath{\mathtt{FOR}}\xspace}
\newcommand*{\TM}{\ensuremath{\mathtt{TM}}\xspace}
\newcommand*{\NTM}{\ensuremath{\mathtt{NTM}}\xspace}
\newcommand*{\N}{\ensuremath{\mathbb{N}}\xspace}
\newcommand{\lepower}{\leq}
\newcommand{\gepower}{\geq}
\newcommand{\epower}{\equiv}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\TIME}[1][]{\ensuremath{\mathtt{TIME}\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\NTIME}[1][]{\ensuremath{\mathtt{NTIME}\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\SPACE}[1][]{\ensuremath{\mathtt{SPACE}\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\NSPACE}[1][]{\ensuremath{\mathtt{NSPACE}\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\LOGTIME}{\ensuremath{\mathtt{LOGTIME}}}
\newcommand{\LOGSPACE}{\ensuremath{\mathtt{LOGSPACE}}}
\newcommand{\PTIME}{\ensuremath{\mathtt{PTIME}}\xspace}
\newcommand{\NPTIME}{\ensuremath{\mathtt{NPTIME}}\xspace}
\newcommand{\PSPACE}{\ensuremath{\mathtt{PSPACE}}}
\newcommand{\EXPTIME}{\ensuremath{\mathtt{EXPTIME}}}
\newcommand{\EXPSPACE}{\ensuremath{\mathtt{EXPSPACE}}}
\mathchardef\mhyphen="2D
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\reducesTo}{\leq}

% Note Commands
\newcommand{\citationneeded}{{\em (citation needed) } }
\newcommand{\lineofthought}[1]{{\bf [#1] }}
\newcommand{\TODO}{\ensuremath{\left<\mathbf{TODO}\right> }}
\newcommand{\DONE}{}

% Disabled Note Commands
\newcommand{\timeestimation}[1]{}
%\newcommand{\citationneeded}{}
%\newcommand{\lineofthought}[1]{}
%\newcommand{\TODO}{}

\newcommand{\interpret}[2][]{\ensuremath{\left\llbracket #2 \right\rrbracket
	\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\Input}[1][]{\ensuremath{I
	\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\Output}[1][]{\ensuremath{O
	\ifthenelse{\isempty{#1}}{}{_{#1}}}}
\newcommand{\Compiler}[3][]{\ensuremath{compile_{#2\rightarrow #3}
	\ifthenelse{\isempty{#1}}{}{^{#1}}}}
\newcommand{\Interpreter}[2][]{\ensuremath{interpret_{#2}
	\ifthenelse{\isempty{#1}}{}{^{#1}}}}
\newcommand{\measuretime}[2][]{\ensuremath{T_#2
	\ifthenelse{\isempty{#1}}{}{^{#1}}}}
\newcommand{\measurespace}[2][]{\ensuremath{S_#2
	\ifthenelse{\isempty{#1}}{}{^{#1}}}}
\newtheorem{prop}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{thesis}{Thesis}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem*{example}{Example}




\author{Aaron Karper}
\newcommand{\titletext}{A Programming Language Oriented Approach to Computability}
\title{\titletext}
\date{}
\begin{document}
\begin{titlepage}
  \let\footnotesize\small
  \let\footnoterule\relax
  \let \footnote \thanks
  
  \begin{center}%
	\vspace{10em}
  	{\huge{\textsc{\titletext}}\\}%
  	\vskip 5em%
	{\LARGE{Bachelorarbeit\\der Philosophisch-naturwissenschaftlichen
  	 Fakult\"at der Universit\"at Bern}\par}%
  	\vskip 12em%
  	{\Large{vorgelegt von}\par}%
  	\vskip 1.5em%
  	{\Large{Aaron Karper}\par}%
  	{\Large{2013}\par}%
  	\vskip 6em%
  	{\Large{Leiter der Arbeit:}\par}%
  	{\Large{Professor Dr. Thomas Strahm}\par}%
	{\Large{Institut f\"ur Informatik und angewandte Mathematik}\par}%
  \end{center}\par	
  \thanks
  \vfil\null
\end{titlepage}

\tableofcontents
\chapter{Introduction}
	\include{introduction}
	\include{for}
	\include{while}

\chapter{Computability}
	\include{transforms}
	\include{completeness}
	\include{self}

\chapter{Complexity}
	\include{complexity}
	\include{langcomplexity}

\bibliography{biblio}{}
\bibliographystyle{plain}

%\begin{appendices}
	%\include*{appendix}
%\end{appendices}
\end{document}

all.bbl
\begin{thebibliography}{10}

\bibitem{aho2007compilers}
A.V. Aho, M.S. Lam, R.~Sethi, and J.D. Ullman.
\newblock {\em Compilers: principles, techniques, and tools}, volume 1009.
\newblock Pearson/Addison Wesley, 2007.

\bibitem{downey1999parameterized}
R.G. Downey and M.R. Fellows.
\newblock {\em Parameterized complexity}, volume~3.
\newblock springer New York, 1999.

\bibitem{etesi2002blackhole}
Gábor Etesi and István Németi.
\newblock Non-turing computations via malament–hogarth space-times.
\newblock {\em International Journal of Theoretical Physics}, 41:341--370,
  2002.
\newblock 10.1023/A:1014019225365.

\bibitem{futamura1999partial}
Y.~Futamura.
\newblock Partial evaluation of computation process--an approach to a
  compiler-compiler.
\newblock {\em Higher-Order and Symbolic Computation}, 12(4):381--391, 1999.

\bibitem{girard1989proofs}
J.Y. Girard, P.~Taylor, and Y.~Lafont.
\newblock {\em Proofs and types}, volume~7.
\newblock Cambridge University Press Cambridge, 1989.

\bibitem{grover1996fast}
L.K. Grover.
\newblock A fast quantum mechanical algorithm for database search.
\newblock In {\em Proceedings of the twenty-eighth annual ACM symposium on
  Theory of computing}, pages 212--219. ACM, 1996.

\bibitem{jones1993partial}
N.D. Jones, C.K. Gomard, and P.~Sestoft.
\newblock {\em Partial evaluation and automatic program generation}.
\newblock Peter Sestoft, 1993.

\bibitem{jones}
Neil~D. Jones.
\newblock {\em Computability and complexity: from a programming perspective}.
\newblock MIT Press, Cambridge, MA, USA, 1997.

\bibitem{nilsson2000porting}
H.P. Nilsson.
\newblock Porting gcc for dunces.
\newblock {\em Master Thesis}, 5:43--54, 2000.

\bibitem{psycho}
Armin Rigo.
\newblock Representation-based just-in-time specialization and the psyco
  prototype for python.
\newblock In {\em Proceedings of the 2004 ACM SIGPLAN symposium on Partial
  evaluation and semantics-based program manipulation}, PEPM '04, pages 15--26,
  New York, NY, USA, 2004. ACM.

\bibitem{russell1995artificial}
S.J. Russell and P.~Norvig.
\newblock {\em Artificial intelligence: a modern approach}, volume~3.
\newblock Prentice hall Englewood Cliffs, NJ, 2009.

\bibitem{sipser2006introduction}
M.~Sipser.
\newblock {\em Introduction to the Theory of Computation}, volume~27.
\newblock Thomson Course Technology Boston, MA, 2006.

\bibitem{dalenrecursion}
D.~van Dalen.
\newblock Algorithms and decision problems: A crash course in recursion theory.
\newblock {\em G. Gabbay and F. Guenthner (eds.), Handbook of Philosophical
  Logic}, 1:409--478, 1983.

\bibitem{veldhuizen2003c++}
T.L. Veldhuizen.
\newblock C++ templates are turing complete.
\newblock {\em Available at citeseer. ist. psu. edu/581150. html}, 2003.

\end{thebibliography}
