Computability

Computability Theory

content/computability/computability-theory/computability-theory.tex

% Part: computability% Chapter: computability-theory\documentclass[../../../include/open-logic-chapter]{subfiles}\begin{document}\olchapter{cmp}{thy}{Computability Theory}\begin{editorial}  Material in this chapter should be reviewed and expanded. In  particular, there are no exercises yet.\end{editorial}\olimport{introduction}\olimport{coding-computations}\olimport{normal-form}\olimport{s-m-n}\olimport{universal-part-function}\olimport{no-universal-function}\olimport{halting-problem}\olimport{russells-paradox}\olimport{computable-sets}\olimport{ce-sets}\olimport{equiv-ce-defs}\olimport{non-comp-set}\olimport{ce-closed-cup-cap}\olimport{complement-ce}\olimport{reducibility}\olimport{prop-reduce}\olimport{complete-ce-sets}\olimport{k-1}\olimport{total}\olimport{rice-theorem}\olimport{fixed-point-thm}\olimport{application-fixed-point}\olimport{def-functions-self-reference}\OLEndChapterHook\end{document}

content/computability/computability-theory/introduction.tex

% Part: computability% Chapter: computability-theory% Section: introduction\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{int}\olsection{Introduction}The branch of logic known as \emph{computability theory} deals withissues having to do with the computability, or relative computability,of functions and sets. It is evidence of Kleene's influencethat the subject used to be known as \emph{recursion theory}, andtoday, both names are commonly used.Let us call a function~$f\colon \Nat \pto \Nat$ \emph{partial  computable} if it can be computed in some model of computation. If$f$ is total we will simply say that $f$~is \emph{computable}. Arelation~$R$ with computable characteristic function~$\Char{R}$ isalso called computable. If $f$ and~$g$ are partial functions, we willwrite $f(x) \fdefined$ to mean that $f$ is defined at~$x$, i.e., $x$~isin the domain of~$f$; and $f(x) \fundefined$ to mean the opposite,i.e., that $f$ is not defined at~$x$. We will use $f(x) \simeq g(x)$to mean that either $f(x)$ and $g(x)$ are both undefined, or they areboth defined and equal.One can explore the theory of computability without having to refer toa specific model of computation. To do this, one shows that there is auniversal partial computable function~$\fn{Un}(k, x)$. This allows usto enumerate the partial computable functions. We will adopt thenotation~$\cfind{k}$ to denote the $k$-th unary partial computablefunction, defined by $\cfind{k}(x) \simeq \fn{Un}(k, x)$. (Kleene used$\{ k \}$ for this purpose, but this notation has not been used asmuch recently.)  Slightly more generally, we can uniformly enumeratethe partial computable functions of arbitrary arities, and we will use$\cfind{k}[n]$ to denote the $k$-th $n$-ary partial recursivefunction.If $f(\vec x, y)$ is a total or partial function, then $\umin{y}{f(\vec x, y)}$ is the function of~$\vec x$ that returns the least~$y$such that $f(\vec x, y) = 0$, assuming that all of $f(\vec x, 0)$,\dots, $f(\vec x, y-1)$ are defined; if there is no such $y$,$\umin{y}{f (\vec x, y)}$ is undefined. If $R(\vec x, y)$ is arelation, $\umin{y}{R(\vec x, y)}$ is defined to be the least~$y$ suchthat $R(\vec x, y)$ is true; in other words, the least~$y$ such that$1 \tsub \Char{R}(\vec x, y) = 0$.To show that a function is computable, there aretwo ways one can proceed:\begin{enumerate}\item Rigorously: describe a Turing machine or partial recursive  function explicitly, and show that it computes the function you have  in mind;\item Informally: describe an algorithm that computes it, and appeal to  Church's thesis.\end{enumerate}There is no fine line between the two; a detailed description ofan algorithm should provide enough information so that it isrelatively clear how one could, in principle, design the right Turingmachine or sequence of partial recursive definitions. Fully rigorousdefinitions are unlikely to be informative, and we will try to find ahappy medium between these two approaches; in short, we will try tofind intuitive yet rigorous proofs that the precise definitions couldbe obtained.\end{document}

content/computability/computability-theory/coding-computations.tex

% Part: computability% Chapter: computability-theory% Section: coding-computations\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{cod}\olsection{Coding Computations}In every model of computation, it is possible to do the following:\begin{enumerate}\item Describe the \emph{definitions} of computable functions in a  systematic way. For instance, you can think of Turing machine  specifications, recursive definitions, or programs in a programming  language as providing these definitions.\item Describe the complete record of the computation of a function  given by some definition for a given input. For instance, a Turing  machine computation can be described by the sequence of  configurations (state of the machine, contents of the tape) for each  step of computation.\item Test whether a putative record of a computation is in fact the  record of how a computable function with a given definition would be  computed for a given input (on which the function is  defined, i.e., the computation halts).\item Extract from such a description of the complete record of a  computation the value of the function for a given input. For  instance, the contents of the tape in the very last step of a  halting Turing machine computation is the value.\end{enumerate}Using coding, it is possible to assign to each description of acomputable function a numerical \emph{index} in such a way that theinstructions can be recovered from the index in a computable way.Similarly, the complete record of a computation can be coded by asingle number as well. The resulting arithmetical relation ``$s$~codesthe record of computation of the function with index~$e$ forinput~$x$'' and the function ``output of computation sequence withcode~$s$'' are then computable; in fact, they are primitive recursive.This fundamental fact is very powerful, and allows us to prove anumber of striking and important results about computability,independently of the model of computation chosen.\end{document}

content/computability/computability-theory/normal-form.tex

% Part: computability% Chapter: computability-theory% Section: normal-form\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{nfm}\olsection{The Normal Form Theorem}Suppose we can describe definitions of computable functions, and test ifsome putative description of the complete record of the computation ofthat function on some input is correct. Then it stands to reason thatindependently of the model of computation, we can determine the valueof any computable function~$f$ on any input~$x$ as follows:\begin{enumerate}  \item Search through all possible descriptions of records of  computation.  \item Test if a given record is the record of a computation of~$f(x)$.  \item Extract the value of~$f(x)$ from the correct record if we have  found it.\end{enumerate}That this is in fact true is the content of Kleene's normal formtheorem.\begin{thm}[Kleene's Normal Form Theorem]\ollabel{thm:normal-form}There is a primitive recursive relation~$T(e, x, s)$ and a primitiverecursive function~$U(s)$, with the following property: if $f$ is anypartial computable function, then for some~$e$,\[f(x) \simeq U(\umin{s}{T(e, x, s)})\]for every~$x$.\end{thm}\begin{proof}[Proof Sketch]For any model of computation one can rigorously define a descriptionof the computable function~$f$ and code such description using anatural number~$e$.  One can also rigorously define a notion of``computation sequence'' which records the process of computing thefunction with index~$e$ for input~$x$.  Such a computation sequence canlikewise be coded as a number~$s$.  This can be done in such a waythat\begin{enumerate}  \item the relation $T(e, x, s)$, which holds iff a number~$s$ codes the computation  sequence of the function with index~$e$ on input~$x$, and  \item the function $U(s)$ which maps a computation sequence coded  by~$s$ to the end result of that computation\end{enumerate}are both computable. In fact, the relation~$T$ and the function~$U$are primitive recursive.\end{proof}\begin{explain}In order to give a rigorous proof of the Normal Form Theorem, we wouldhave to fix a model of computation and carry out the coding ofdescriptions of computable functions and of computation sequences indetail, and verify that the relation~$T$ and function~$U$ areprimitive recursive.  For most applications, it suffices that $T$and~$U$ are computable and that $U$~is total.It is probably best to remember the proof of the normal form theoremin slogan form: $\umin{s}{T(e, x, s)}$ searches for a computationsequence of the function with index~$e$ on input~$x$, and $U$ returnsthe output of the computation sequence if one can be found.\end{explain}If the model of computation is the partial recursive functions (whichis what Kleene originally used), it shows that only a single use ofunbounded search, i.e., a single $\umin{y}{f(\vec x, y)}$ operator isnecessary for the definition of any function. In this sense it showsthat any partial recursive function has a normal form.$T$ and $U$ can be used to define the enumeration $\cfind{0}$,$\cfind{1}$, $\cfind{2}$, \dots.  From now on, we will assume that wehave fixed a suitable choice of $T$ and~$U$, and take the equation\[\cfind{e}(x) \simeq U(\umin{s}{T(e,x,s)})\]to be the \emph{definition} of $\cfind{e}$.Here is another useful fact:\begin{thm}Every partial computable function has infinitely many indices.\end{thm}Again, this is intuitively clear.  Given any (description of) acomputable function, one can come up with a different descriptionwhich computes the same function (input-output pair) but does so,e.g., by first doing something that has no effect on the computation(say, test if $0 = 0$, or count to $5$, etc.).  The index of thealtered description will always be different from the originalindex.  Both are indices of the same function, just computed slightlydifferently.\end{document}

content/computability/computability-theory/s-m-n.tex

% Part: computability% Chapter: computability-theory% Section: s-m-n\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{smn}\olsection{The $s$-$m$-$n$ Theorem}\begin{explain}The next theorem is known as the ``$s$-$m$-$n$ theorem,'' for a reasonthat will be clear in a moment. The hard part is understanding justwhat the theorem says; once you understand the statement, it will seemfairly obvious.\end{explain}\begin{thm}\ollabel{thm:s-m-n}  For each pair of natural numbers $n$ and~$m$, there is a primitive  recursive function~$s^m_n$ such that for every sequence  $e$, $a_0$, \dots, $a_{m-1}$, $y_0$ ,\dots, $y_{n-1}$, we have  \[  \cfind{s^m_n(e, a_0, \dots, a_{m-1})}[n](y_0, \dots, y_{n-1}) \simeq  \cfind{e}[m+n](a_0, \dots, a_{m-1}, y_0, \dots, y_{n-1}).\]\end{thm}\begin{explain}It is helpful to think of $s^m_n$ as acting on \emph{programs}. Thatis, $s^m_n$ takes a program~$e$ for an $(m+n)$-ary function, as wellas fixed inputs $a_0$, \dots, $a_{m-1}$; and it returns a program$s^m_n(x, a_0, \dots, a_{m-1})$ for the $n$-ary function of theremaining arguments. \iftag{TMs}{It you think of $x$ as the description of aTuring machine, then $s^m_n(e, a_0, \dots, a_{m-1})$ is the Turingmachine that, on input $y_0$, \dots,~$y_{n-1}$, prepends$a_0$, \dots,~$a_{m-1}$ to the input string, and runs~$e$. Each $s^m_n$is then just a primitive recursive function that finds a code for theappropriate Turing machine.}{}\end{explain}\end{document}

content/computability/computability-theory/universal-part-function.tex

% Part: computability% Chapter: computability-theory% Section: universal-part-function\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{uni}\olsection{The Universal Partial Computable Function}\begin{thm}\ollabel{thm:univ-comp}There is a universal partial computable function~$\fn{Un}(e,x)$. In otherwords, there is a function $\fn{Un}(e,x)$ such that:\begin{enumerate}\item $\fn{Un}(e,x)$ is partial computable.\item If $f(x)$ is any partial computable function, then there is anatural number $e$ such that $f(x) \simeq \fn{Un}(e,x)$ for every~$x$.\end{enumerate}\end{thm}\begin{proof}Let $\fn{Un}(e,x) \simeq U(\umin{s}{T(e,x,s)})$, where $U$ and $T$ areas in Kleene's normal form theorem (\olref[nfm]{thm:normal-form}).\end{proof}\begin{explain}This is just a precise way of saying that we have an effectiveenumeration of the partial computable functions; the idea is that ifwe write $f_e$ for the function defined by $f_e(x) = \fn{Un}(e,x)$,then the sequence $f_0$, $f_1$, $f_2$, \dots includes all the partialcomputable functions, with the property that $f_e(x)$ can be computed``uniformly'' in $e$ and~$x$. For simplicity, we are using a binaryfunction that is universal for unary functions, but by codingsequences of numbers we can easily generalize this to more arguments.For example, note that if $f(x,y,z)$ is a $3$-place partial recursivefunction, then the function $g(x) \simeq f((x)_0, (x)_1, (x)_2)$ is aunary recursive function.\end{explain}\end{document}

content/computability/computability-theory/no-universal-function.tex

% Part: computability% Chapter: computability-theory% Section: no-universal-function\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{nou}\olsection{No Universal Computable Function}Although there is a partial computable function that is total for thepartial computable functions, there is no total computablefunction that is universal for the total computable functions. \begin{thm}\ollabel{thm:no-univ}There is no universal computable function. In other words, anyfunction $\fn{Un}'(k, x)$ which is such that if $f(x)$ is a totalcomputable function, then there is a natural number~$k$ such that$f(x) = \fn{Un}'(k,x)$ for every~$x$, is not computable.\end{thm}\begin{proof}The proof is a simple diagonalization: if $\fn{Un}'(k,x)$ were totaland computable, then\[d(x) = \fn{Un}'(x, x) + 1\]would also be total and computable. However, by definition, $d(k)$ isnot equal to $\fn{Un}'(k,k)$. Hence, for every $k$, the values of$d(x)$ and~$\fn{Un}'(k, x)$ differ for at least one~$x$, namely $x = k$.\end{proof}\begin{explain}\olref[uni]{thm:univ-comp} above shows that we can get around thisdiagonalization argument, but only at the expense of allowing theuniversal function to be partial. That is, $\fn{Un}$ is universal forthe total computable functions, it just isn't total. Thediagonalization argument doesn't work in the partial case. \end{explain}\begin{prob}  To understand why the diagonalization argument in the proof of  \olref{thm:no-univ} does not work in the partial  case, consider the function $f(x) \simeq \fn{Un}(x,x)+1$. Is it  partial computable? If so, it has an index~$e$, i.e., $f(x) \simeq  \fn{Un}(e,x)$. What can you say about~$f(e)$?\end{prob}\end{document}

content/computability/computability-theory/halting-problem.tex

% Part: computability% Chapter: computability-theory% Section: halting-problem\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{hlt}\olsection{The Halting Problem}By construction, the universal partial computablefunction~$\fn{Un}(e,x)$ is defined if and only if the computation ofthe function coded by~$e$ produces a value for input~$x$. It isnatural to ask if we can decide whether this is the case. In fact, itis not. For the Turing machine model of computation, this means thatwhether a given Turing machine halts on a given input iscomputationally undecidable. The following theorem is therefore knownas the ``undecidability of the halting problem.'' We will provide twoproofs below. The first continues the thread of our previousdiscussion, while the second is more direct.\begin{thm}\ollabel{thm:halting-problem}Let\[h(e, x)  =\begin{cases}1 & \text{if\/ $\fn{Un}(e, x)$ is defined} \\0 & \text{otherwise.}\end{cases}\]Then $h$ is not computable.\end{thm}\begin{proof}Suppose $h$ is computable. We show that this would let us define auniversal computable function. Define\[\fn{Un'}(e,x) =\begin{cases}\fn{Un}(e,x) & \text{if $h(e,x) = 1$} \\0 & \text{otherwise.}\end{cases}\]But now $\fn{Un'}(e, x)$ is a total function, and is computable if~$h$is. For instance, we could define $g$ using primitive recursion, by\begin{align*}g(0, e, x) & \simeq 0 \\g(y+1, e, x) & \simeq \fn{Un}(e,x);\end{align*}then\[\fn{Un'}(e,x) \simeq g(h(e,x),e,x).\]Since $\fn{Un'}(e,x)$ agrees with $\fn{Un}(e,x)$ wherever the latteris defined, $\fn{Un'}$ is universal for those partial computablefunctions that happen to be total. But this contradicts\olref[nou]{thm:no-univ}.\end{proof}\begin{proof}Suppose $h(e,x)$ were computable. Define the function $g$ by\[g(x) =\begin{cases}  0                & \text{if $h(x,x) = 0$} \\  \fundefined & \text{otherwise.}\end{cases}\]The function $g$ is partial computable. For example, one can define itas $\umin{y}{h(x,x) = 0}$. So, for some~$e$, $g(x) \simeq \fn{Un}(e,x)$ for every~$x$. Is $g$ defined at $e$?  If it is, then, by thedefinition of~$g$, $h(e,e) = 0$ ($h$~can only take the value~$0$ if itis defined). By the definition of~$h$, this means that $\fn{Un}(e, e)$is undefined. By our assumption that $g(x) \simeq \fn{Un}(e, x)$for every~$x$, we have that $g(e)$ is undefined, a contradiction.On the other hand, if $g(e)$ is undefined, then $h(e,e) \neq 0$, andso $h(e,e) = 1$. It follows that $\fn{Un}(e, e)$ is defined. But since$g(x) \simeq \fn{Un}(e, x)$, then $g(e)$ would also be defined. Again,a contradiction.\end{proof}\begin{tagblock}{TMs}\begin{explain}We can describe this argument in terms of Turing machines.  Supposethere were a Turing machine~$H$ that takes as input a description of aTuring machine~$E$ and an input~$x$, and decides whether or not $E$halts on input~$x$. Then we could build another Turing machine~$G$which takes a single input~$x$, runs $H$ to decide if the machine$M_x$ with index~$x$ halts on input~$x$, and does the opposite. Inother words, if $H$ reports that $M_x$ halts on input~$x$, $G$ goesinto an infinite loop, and if $H$ reports that $M_x$ doesn't halt oninput~$x$, then $G$ just halts. Does $G$ halt on its own index asinput? The argument above shows that it does if and only if itdoesn't---a contradiction. So our supposition that there is a suchTuring machine~$H$ must be false.\end{explain}\end{tagblock}\end{document}

content/computability/computability-theory/russells-paradox.tex

% Part: computability% Chapter: computability-theory% Section: russells-paradox\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{rus}\olsection{Comparison with Russell's Paradox}It is instructive to compare and contrast the arguments inthis section with Russell's paradox:\begin{enumerate}\item Russell's paradox: let $S = \Setabs{x}{x \notin x}$. Then $S  \in S$ if and only if $X \notin S$, a contradiction.  \emph{Conclusion:} There is no such set~$S$. Assuming the existence of a  ``set of all sets'' is inconsistent with the other axioms of set  theory.\item A modification of Russell's paradox: let $F$ be the ``function''  from the set of all functions to $\{ 0, 1 \}$, defined by  \[  F(f) =  \begin{cases}    1 & \text{if $f$ is in the domain of $f$, and $f(f) = 0$} \\    0 & \text{otherwise}  \end{cases}  \]  A similar argument shows that $F(F) = 0$ if and only if $F(F) = 1$,  a contradiction.  \emph{Conclusion:} $F$ is not a function. The ``set of all  functions'' is too big to be the domain of a function.\item The diagonalization argument: let $f_0$, $f_1$, \dots be the  enumeration of the partial computable functions, and let $G \colon \Nat \to  \{ 0, 1 \}$ be defined by  \[  G(x) =  \begin{cases}    1 & \text{if $f_x(x)\downarrow = 0$} \\    0 & \text{otherwise}  \end{cases}  \]  If $G$ is computable, then it is the function $f_k$ for some  $k$. But then $G(k) = 1$ if and only if $G(k) = 0$, a contradiction.  \emph{Conclusion:} $G$ is not computable. Note that according to the  axioms of set theory, $G$ is still a function; there is no paradox  here, just a clarification.\end{enumerate}That talk of partial functions, computable functions,partial computable functions, and so on can be confusing. The set ofall partial functions from $\Nat$ to $\Nat$ is a big collection ofobjects. Some of them are total, some of them are computable, some areboth total and computable, and some are neither. Keep in mind thatwhen we say ``function,'' by default, we mean a total function. Thus wehave:\begin{enumerate}\item computable functions\item partial computable functions that are not total\item functions that are not computable\item partial functions that are neither total nor computable\end{enumerate}To sort this out, it might help to draw a big square representing allthe partial functions from $\Nat$ to $\Nat$, and then mark off twooverlapping regions, corresponding to the total functions and thecomputable partial functions, respectively. It is a good exercise tosee if you can describe an object in each of the resulting regions inthe diagram.\end{document}

content/computability/computability-theory/computable-sets.tex

% Part: computability% Chapter: computability-theory% Section: computable-sets\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{cps}\olsection{Computable Sets}We can extend the notion of computability from computable functions tocomputable sets:\begin{defn}  Let $S$ be a set of natural numbers. Then $S$ is \emph{computable}  iff its characteristic function~$\Char{S}$ is. In other words,  $S$~is computable iff the function\[\Char{S}(x) =\begin{cases}1 & \text{if $x \in S$} \\0 & \text{otherwise}\end{cases}\]is computable. Similarly, a relation $R(x_0, \dots, x_{k-1})$ iscomputable if and only if its characteristic function is.Computable sets and relations are also called \emph{decidable}.\end{defn}\begin{explain}Notice that we now have a number of notions of computability: forpartial functions, for functions, and for sets. Do not get themconfused!{} \iftag{TMs}{The Turing machine computing a partial function  returns the output of the function, for input values at which the  function is defined; the Turing machine computing a set returns  either $1$ or~$0$, after deciding whether or not the input value is in  the set or not.}{}\end{explain}\end{document}

content/computability/computability-theory/ce-sets.tex

% Part: computability% Chapter: computability-theory% Section: ce-sets\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{ces}\olsection{Computably Enumerable Sets}\begin{defn}A set is \emph{computably enumerable} if it is empty or the range of acomputable function.\end{defn}\begin{history}Computably enumerable sets are also called \emph{recursively  enumerable} instead. This is the original terminology, and todayboth are commonly used, as well as the abbreviations ``c.e.'' and``r.e.''\end{history}\begin{explain}You should think about what the definition means, and why theterminology is appropriate. The idea is that if $S$ is the range ofthe computable function~$f$, then\[S = \{ f(0), f(1), f(2), \dots \},\]and so $f$ can be seen as ``enumerating'' the elements of~$S$. Notethat according to the definition, $f$~need not be an increasingfunction, i.e., the enumeration need not be in increasing order. Infact, $f$ need not even be injective, i.e., repetitions in theenumeration $f(0)$, $f(1)$, $f(2)$, \dots{} of~$S$ are allowed. Forinstance, the constant function $f(x) = 0$ enumerates the set $\{ 0\}$.\end{explain}Any computable set is computably enumerable. To see this, suppose$S$~is computable. If $S$ is empty, then by definition it iscomputably enumerable. Otherwise, let $a$ be any element of$S$. Define $f$ by\[f(x) =\begin{cases}x & \text{if $\Char{S}(x) = 1$} \\a & \text{otherwise.}\end{cases}\]Then $f$ is a computable function, and $S$ is the range of~$f$.\end{document}

content/computability/computability-theory/equiv-ce-defs.tex

% Part: computability% Chapter: computability-theory% Section: equiv-ce-defs\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{eqc}\olsection[Definitions of C. E. Sets]{Equivalent Defininitions of  Computably Enumerable Sets}The following gives a number of important equivalent statements ofwhat it means to be computably enumerable.\begin{thm}\ollabel{thm:ce-equiv}Let $S$ be a set of natural numbers. Then the following areequivalent:\begin{enumerate}\item\ollabel{case:ce} $S$ is computably enumerable.\item\ollabel{case:ran-pc} $S$ is the range of a \emph{partial} computable function.\item\ollabel{case:ran-prim} $S$ is empty or the range of a primitive recursive function.\item\ollabel{case:ce-domain} $S$ is the \emph{domain} of a partial computable function.\end{enumerate}\end{thm}\begin{explain}The first three clauses say that we can equivalently take any non-emptycomputably enumerable set to be enumerated by either a computablefunction, a partial computable function, or a primitive recursivefunction. The fourth clause tells us that if $S$ is computablyenumerable, then for some index~$e$,\[S = \Setabs{x}{\cfind{e}(x) \fdefined}.\]In other words, $S$ is the set of inputs on for which the computationof $\cfind{e}$ halts. For that reason, computably enumerable sets aresometimes called \emph{semi-decidable}: if a number is in the set, youeventually get a ``yes,'' but if it isn't, you never get a ``no''!{}\end{explain}\begin{proof}Since every primitive recursive function is computable and everycomputable function is partial computable, \olref{case:ran-prim}implies \olref{case:ce} and \olref{case:ce}implies~\olref{case:ran-pc}. (Note that if $S$ is empty, $S$~is therange of the partial computable function that is nowhere defined.) Ifwe show that \olref{case:ran-pc} implies \olref{case:ran-prim}, wewill have shown the first three clauses equivalent.So, suppose $S$ is the range of the partial computable function$\cfind{e}$. If $S$ is empty, we are done. Otherwise, let $a$ be anyelement of~$S$. By Kleene's normal form theorem, we can write\[\cfind{e}(x) = U(\umin{s}{T(e, x, s)}).\]In particular, $\cfind{e}(x) \fdefined$ and $= y$ if and only if thereis an $s$ such that $T(e, x, s)$ and $U(s) = y$. Define $f(z)$ by\[f(z) = \begin{cases}  U((z)_1) & \text{if $T(e, (z)_0, (z)_1)$} \\  a        & \text{otherwise.}\end{cases}\]Then $f$ is primitive recursive, because $T$ and $U$are. \iftag{TMs}{Expressed in terms of Turing machines, if $z$ codes a  pair $\tuple{(z)_0, (z)_1}$ such that $(z)_1$ is a halting  computation of machine~$M_e$ on input $(z)_0$, then $f$ returns the  output of the computation; otherwise, it returns~$a$.}We need to show that $S$ is the range of~$f$, i.e., for any naturalnumber~$y$, $y \in S$ if and only if it is in the range of~$f$. In theforwards direction, suppose $y \in S$. Then $y$ is in the range of$\cfind{e}$, so for some $x$ and~$s$, $T(e,x,s)$ holds and $U(s) = y$.But then $y = f(\tuple{x,s})$. Conversely, suppose $y$ is in the rangeof~$f$. Then either $y = a$, or for some~$z$, $T(e,(z)_0,(z)_1)$ and$U((z)_1) = y$. Since, in the latter case, $\cfind{e}(x) \fdefined =y$, either way, $y$ is in~$S$.(The notation $\cfind{e}(x) \fdefined = y$ means ``$\cfind{e}(x)$ isdefined and equal to $y$.'' We could just as well use $\cfind{e}(x) =y$, but the extra arrow is sometimes helpful in reminding us that weare dealing with a partial function.)To finish up the proof of \olref{thm:ce-equiv}, it suffices to showthat \olref{case:ce} and~\olref{case:ce-domain} are equivalent. First,let us show that \olref{case:ce} implies~\olref{case:ce-domain}.Suppose $S$ is the range of a computable function~$f$, i.e.,\[S = \Setabs{y}{\text{for some $x$, } f(x) = y}.\]Let\[g(y) = \umin{x}{(f(x) = y)}.\]Then $g$ is a partial computable function, and $g(y)$ is defined ifand only if for some~$x$, $f(x) = y$. In other words, the domain of$g$~is the range of~$f$. \iftag{TMs}{Expressed in terms of Turingmachines: given a Turing machine~$F$ that enumerates the elementsof~$S$, let $G$ be the Turing machine that semi-decides $S$ bysearching through the outputs of~$F$ to see if a given element is inthe set, halts if it is and keeps searching forever if it isn't.}{}Finally, to show \olref{case:ce-domain} implies~\olref{case:ce},suppose that $S$~is the domain of the partial computablefunction~$\cfind{e}$, i.e.,\[S = \Setabs{x}{\cfind{e}(x) \fdefined}.\]If $S$ is empty, we are done; otherwise, let $a$ be any elementof~$S$. Define $f$ by\[f(z) = \begin{cases}(z)_0 & \text{if $T(e,(z)_0,(z)_1)$} \\a & \text{otherwise.}\end{cases}\]Then, as above, a number $x$ is in the range of~$f$ if and only if$\cfind{e}(x) \fdefined$, i.e., if and only if $x \in S$. \iftag{TMs}{Expressedin terms of Turing machines: given a machine $M_e$ that semi-decides$S$, enumerate the elements of $S$ by running through all possibleTuring machine computations, and returning the inputs that correspondto halting computations.}{}\end{proof}Clause~\olref{case:ce-domain} of \olref{thm:ce-equiv} provides us witha convenient way of enumerating the computably enumerable sets: foreach~$e$, let $W_e$ denote the domain of $\cfind{e}$, i.e.,\[W_e = \Setabs{x}{\cfind{e}(x) \fdefined}.\] Then if $A$ is any computably enumerable set, $A = W_e$, for some~$e$.The following provides yet another characterization of the computablyenumerable sets.\begin{thm}\ollabel{thm:exists-char}A set $S$ is computably enumerable if and only if there is acomputable relation $R(x,y)$ such that\[S = \Setabs{ x }{ \lexists[y][R(x,y)] }.\]\end{thm}\begin{proof}In the forward direction, suppose $S$ is computablyenumerable. Then for some $e$, $S = W_e$. For this value of~$e$we can write $S$ as\[S = \Setabs{ x }{ \lexists[y][T(e, x, y)] }.\]In the reverse direction, suppose $S = \Setabs{ x }{  \lexists[y][R(x, y)] }$. Define $f$~by\[f(x) \simeq \umin{y}{R(x, y)}.\]Then $f$ is partial computable, and $S$ is the domain of~$f$.\end{proof}\end{document}

content/computability/computability-theory/non-comp-set.tex

% Part: computability% Chapter: computability-theory% Section: non-comp-set\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{ncp}\olsection{There Are Non-Computable Sets}We saw above that every computable set is computably enumerable. Isthe converse true? The following shows that, in general, it is not.\begin{thm}\ollabel{thm:K-0}Let $K_0$ be the set $\Setabs{\tuple{e, x}}{\cfind{e}(x) \fdefined}$.Then $K_0$ is computably enumerable but not computable.\end{thm}\begin{proof}To see that $K_0$ is computably enumerable, note that it is thedomain of the function~$f$ defined by\[f(z) = \umin{y}{(\len{z} = 2 \land T((z)_0, (z)_1, y))}.\]For, if $\cfind{e}(x)$ is defined, $f(\tuple{e, x})$ finds a haltingcomputation sequence; if $\cfind{e}(x)$ is undefined, so is$f(\tuple{e, x})$; and if $z$ doesn't even code a pair, then $f(z)$ isalso undefined.The fact that $K_0$ is not computable is just the undecidability ofthe halting problem, \olref[hlt]{thm:halting-problem}.\end{proof}The set $K_0$ is the set of pairs $\tuple{e,x}$ such that$\cfind{e}(x) \fdefined$, i.e., $\tuple{e,x} \in K_0$ iff $\cfind{e}$is defined (halts) on input~$x$, so it is also called the ``haltingset.'' The set $K = \Setabs{e}{\cfind{e}(e) \fdefined}$ is the``self-halting set.'' It is often used as a canonical undecidable set.\begin{thm}\ollabel{thm:K}The self-halting set $K = \Setabs{e}{\cfind{e}(e) \fdefined}$ is!!{c.e.} but not decidable.\end{thm}\begin{proof}  Suppose $K$ is decidable, i.e., its characteristic function  $\Char{K}$ is computable. Let   \[d(e) = \begin{cases}  1 & \text{if\/ $\Char{K}(e) = 0$}\\  \fundefined & \text{otherwise.}  \end{cases}  \]   Let $k$ be the index of~$d$, i.e., $d \simeq \cfind{k}$. Then $d(k)  \simeq \cfind{k}(k)$. This contradicts the fact that $d(k)  \fdefined$ iff $\cfind{k}(k) \fundefined$, which follows from the  definition of~$d$.  $K$ is the domain of $f(x) = \umin{y}{T(x,x,y)}$ and so is !!{c.e.}\end{proof}\end{document}

content/computability/computability-theory/ce-closed-cup-cap.tex

% Part: computability% Chapter: computability-theory% Section: ce-closed-cup-cap\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{clo}\olsection[Union and Intersection of C.E. Sets]{Computably Enumerable  Sets are Closed under Union and Intersection}The following theorem gives some closure properties on the set ofcomputably enumerable sets.\begin{thm}Suppose $A$ and $B$ are computably enumerable. Then so are $A \cap B$and $A \cup B$.\end{thm}\begin{proof}\olref[eqc]{thm:ce-equiv} allows us to use various characterizationsof the computably enumerable sets. By way of illustration, we willprovide a few different proofs.For the first proof, suppose $A$ is enumerated by a computablefunction~$f$, and $B$ is enumerated by a computable function~$g$. Let\begin{align*}h(x) & = \umin{y}{(f(y) = x \lor g(y) = x)} \text{ and}\\j(x) & = \umin{y}{(f((y)_0) = x \land g((y)_1) = x)}.\end{align*}Then $A \cup B$ is the domain of $h$, and $A \cap B$ is the domainof~$j$.\begin{explain}Here is what is going on, in computational terms: givenprocedures that enumerate $A$ and $B$, we can semi-decide if anelement $x$ is in $A \cup B$ by looking for $x$ in either enumeration;and we can semi-decide if an element $x$ is in $A \cap B$ for lookingfor $x$ in both enumerations at the same time.\end{explain}For the second proof, suppose again that $A$ is enumerated by~$f$ and$B$ is enumerated by~$g$. Let\[k(x) = \begin{cases}f(x/2) & \text{if $x$ is even} \\g((x-1)/2) & \text{if $x$ is odd.}\end{cases}\]Then $k$ enumerates $A \cup B$; the idea is that $k$ just alternatesbetween the enumerations offered by $f$ and~$g$. Enumerating $A \capB$ is tricker. If $A \cap B$ is empty, it is trivially computablyenumerable. Otherwise, let $c$ be any element of $A \cap B$, anddefine $l$ by\[l(x) = \begin{cases}f((x)_0) & \text{if $f((x)_0) = g((x)_1)$} \\c & \text{otherwise.}\end{cases}\]In computational terms, $l$ runs through pairs of elements in theenumerations of $f$ and $g$, and outputs every match it finds;otherwise, it just stalls by outputting $c$.For the last proof, suppose $A$ is the \emph{domain} of the partialfunction $m(x)$ and $B$ is the domain of the partial function$n(x)$. Then $A \cap B$ is the domain of the partial function $m(x) +n(x)$.\begin{explain}In computational terms, if $A$ is the set of values for which$m$ halts and $B$ is the set of values for which $n$ halts, $A \cap B$is the set of values for which both procedures halt.\end{explain}Expressing $A \cup B$ as a set of halting values is more difficult,because one has to simulate $m$ and $n$ in parallel. Let $d$ be anindex for $m$ and let $e$ be an index for $n$; in other words, $m =\cfind{d}$ and $n = \cfind{e}$. Then $A \cup B$ is the domain of thefunction\[p(x) = \umin{y}{(T(d,x,y) \lor T(e,x,y))}.\]\begin{explain}In computational terms, on input $x$, $p$ searches for either ahalting computation for $m$ or a halting computation for $n$, andhalts if it finds either one.\end{explain}\end{proof}\end{document}

content/computability/computability-theory/complement-ce.tex

% Part: computability% Chapter: computability-theory% Section: complement-ce\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{cmp}\olsection{Computably Enumerable Sets not Closed under Complement}Suppose $A$ is computably enumerable. Is the complement of~$A$,$\Complement{A} = \Nat \setminus A$, always computably enumerableas well? The following theorem and corollary show that the answer is``no.''\begin{thm}\ollabel{thm:ce-comp}Let $A$ be any set of natural numbers. Then $A$ is computable if andonly if both $A$ and $\Complement{A}$ are computably enumerable.\end{thm}\begin{proof}The forwards direction is easy: if $A$ is computable, then$\Complement{A}$ is computable as well ($\Char{A} = 1 \tsub\Char{\Complement{A}}$), and so both are computably enumerable.In the other direction, suppose $A$ and~$\Complement{A}$ are bothcomputably enumerable. Let $A$ be the domain of~$\cfind{d}$, and let$\Complement{A}$ be the domain of~$\cfind{e}$. Define $h$ by\[h(x) = \umin{s}{(T(d,x,s) \lor T(e,x,s))}.\]In other words, on input~$x$, $h$~searches for either a haltingcomputation of~$\cfind{d}$ or a halting computation of~$\cfind{e}$.Now, if $x \in A$, it will succeed in the first case, and if $x \in\Complement{A}$, it will succeed in the second case. So, $h$~is atotal computable function. But now we have that for every~$x$, $x \inA$ if and only if $T(e, x, h(x))$, i.e., if $\cfind{e}$ is the onethat is defined. Since $T(e, x, h(x))$ is a computable relation,$A$~is computable.\end{proof}\begin{explain}It is easier to understand what is going on in informal computationalterms: to decide $A$, on input $x$ search for halting computations of$\cfind{e}$ and $\cfind{f}$. One of them is bound to halt; if it is $\cfind{e}$,then $x$ is in~$A$, and otherwise, $x$ is in~$\Complement{A}$.\end{explain}\begin{cor}\ollabel{cor:comp-k}$\Complement{K_0}$ is not computably enumerable.\end{cor}\begin{proof}We know that $K_0$ is computably enumerable, but not computable. If$\Complement{K_0}$ were computably enumerable, then $K_0$ would becomputable by \olref{thm:ce-comp}, contradicting \olref[ncp]{thm:K-0}.\end{proof}\end{document}

content/computability/computability-theory/reducibility.tex

% Part: computability% Chapter: computability-theory% Section: reducibility\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{red}\olsection{Reducibility}\begin{explain}We now know that there is at least one set, $K_0$, that is computablyenumerable but not computable. It should be clear that there areothers. The method of reducibility provides a powerful method ofshowing that other sets have these properties, without constantlyhaving to return to first principles.Generally speaking, a ``reduction'' of a set $A$ to a set~$B$ is amethod of transforming answers to whether or not !!{element}s are in~$B$into answers as to whether or not !!{element}s are in~$A$. We will focuson a notion called ``many-one reducibility,'' but there are many othernotions of reducibility available, with varying properties. Notions ofreducibility are also central to the study of computationalcomplexity, where efficiency issues have to be considered as well. Forexample, a set is said to be ``NP-complete'' if it is in NP and everyNP problem can be reduced to it, using a notion of reduction that issimilar to the one described below, only with the added requirementthat the reduction can be computed in polynomial time.We have already used the notion of reduction notion implicitly. Definethe set~$K$ by\[K = \Setabs{x}{\cfind{x}(x) \fdefined},\]i.e., $K = \Setabs{x}{x \in W_x}$. Our proof that the halting problemin unsolvable (\olref[hlt]{thm:halting-problem}) shows most directlythat $K$ is not computable. Recall that $K_0$ is the set\[K_0 = \Setabs{\tuple{e, x}}{\cfind{e}(x) \fdefined },\]i.e., $K_0 = \Setabs{\tuple{x,e}}{x \in W_e}$. It is easy to extendany proof of the uncomputability of~$K$ to the uncomputabilityof~$K_0$: if $K_0$ were computable, we could decide whether or not!!a{element}~$x$ is in $K$ simply by asking whether or not the pair$\tuple{x, x}$ is in $K_0$. The function~$f$ which maps $x$ to$\tuple{x, x}$ is an example of a \emph{reduction} of $K$ to $K_0$.\end{explain}\begin{defn}Let $A$ and $B$ be sets of natural numbers. A computablefunction~$f\colon \Nat \to \Nat$ is a \emph{many-one reduction} of $A$to~$B$ iff, for every natural number~$x$,\[x \in A \quad \text{if and only if} \quad f(x) \in B.\]If such a reduction $f$ exists, we say that $A$ is \emph{many-onereducible} to~$B$, written $A \leq_m B$. If $A$ is many-one reducibleto $B$ and vice-versa, then $A$ and $B$ are said to be \emph{many-oneequivalent}, written $A \equiv_m B$.\end{defn}If the function $f$ in the definition above happens to be injective,$A$~is said to be \emph{one-one reducible} to~$B$. Most of thereductions described below meet this stronger requirement, but we willnot use this fact.\begin{digress}It is true, but by no means obvious, that one-one reducibility reallyis a stronger requirement than many-one reducibility. In other words,there are infinite sets $A$ and~$B$ such that $A$ is many-onereducible to~$B$ but not one-one reducible to~$B$.\end{digress}\end{document}

content/computability/computability-theory/prop-reduce.tex

% Part: computability% Chapter: computability-theory% Section: prop-reduce\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{ppr}\olsection{Properties of Reducibility}We write $A \leq_m B$ if $A$ reduces to~$B$, and this notationsuggests that if $A \leq_m B$, then $A$ is ``no harder than''~$B$ andthat $B$ is ``as hard or harder than''~$A$, and that $\le_m$, like theusual $\le$ on numbers, orders sets (or decision problems) by theircomplexity. The following two propositions support this intuition. Thefirst one say taht $\le_m$ is transitive.\begin{prop}\ollabel{prop:trans-red}If $A \leq_m B$ and $B \leq_m C$, then $A \leq_m C$.\end{prop}\begin{proof}Composing a reduction of $A$ to~$B$ with a reduction of $B$ to$C$ yields a reduction of $A$ to~$C$.\end{proof}\begin{prob}Prove \olref{prop:trans-red} by showing that if $f$ and~$g$ aremany-one reductions of $A$ to~$B$ and $B$ to~$C$, respectively, then$\comp{f}{g}$ is a many-one reduction of $A$ to~$C$.\end{prob}\begin{prop}\ollabel{prop:reduce}Let $A$ and $B$ be any sets, and suppose $A \leq_m B$.\begin{enumerate}\item If $B$ is computably enumerable, so is~$A$.\item If $B$ is computable, so is~$A$.\end{enumerate}\end{prop}\begin{proof}Let $f$ be a many-one reduction from $A$ to~$B$. For the firstclaim, just check that if $B$ is the domain of a partial function~$g$,then $A$ is the domain of~$\comp{f}{g}$:\begin{align*}x \in A & \text{ iff } f(x) \in B \\& \text{ iff }  g(f(x)) \fdefined.\end{align*}For the second claim, remember that if $B$~is computable then $B$and~$\Complement{B}$ are computably enumerable(\olref[cmp]{thm:ce-comp}). It is not hard to check that $f$~is also amany-one reduction of $\Complement{A}$ to $\Complement{B}$, so, by thefirst part of this proof, $A$ and~$\Complement{A}$ are !!{computablyenumerable}. So $A$ is computable as well by \olref[cmp]{thm:ce-comp}.(Alternatively, you can check that $\Char{A} = \comp{f}{\Char{B}}$; soif $\Char{B}$ is computable, then so is~$\Char{A}$.)\end{proof}\begin{prob}Suppose $f$ is a many-one reduction of $A$ to~$B$. Show that $f$ isalso a many-one reduction of $\Complement{A}$ to $\Complement{B}$.\end{prob}\begin{prob}Show that if $f\colon A \to B$ is a many-one reduction, then $\Char{A}= \comp{f}{\Char{B}}$.\end{prob}\begin{digress}A more general notion of reducibility called \emph{Turingreducibility} is useful in other contexts, especially for provingundecidability results. Note that by \olref[cmp]{cor:comp-k}, thecomplement of~$K_0$ is not reducible to~$K_0$, since it is notcomputably enumerable. But, intuitively, if you knew the answers toquestions about $K_0$, you would know the answer to questions aboutits complement as well. A set $A$ is said to be Turing reducibleto~$B$ if one can determine answers to questions in~$A$ using acomputable procedure that can ask questions about~$B$. This is moreliberal than many-one reducibility, in which (1)~you are only allowedto ask one question about $B$, and (2)~a ``yes'' answer has totranslate to a ``yes'' answer to the question about $A$, and similarlyfor ``no.'' It is still the case that if $A$~is Turing reducibleto~$B$ and $B$~is computable then $A$~is computable as well (though,as we have seen, the analogous statement does not hold for computableenumerability).You should think about the various notions of reducibility we havediscussed, and understand the distinctions between them. We will,however, only deal with many-one reducibility in this chapter.Incidentally, both types of reducibility discussed in the lastparagraph have analogues in computational complexity, with the addedrequirement that the Turing machines run in polynomial time: thecomplexity version of many-one reducibility is known as \emph{Karpreducibility}, while the complexity version of Turing reducibility isknown as \emph{Cook reducibility}.\end{digress}\end{document}

content/computability/computability-theory/complete-ce-sets.tex

% Part: computability% Chapter: computability-theory% Section: complete-ce-sets\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{cce}\olsection{Complete Computably Enumerable Sets}\begin{defn}A set $A$ is a \emph{complete !!{computably enumerable} set}(under many-one reducibility) if\begin{enumerate}\item $A$ is computably enumerable, and\item for any other computably enumerable set $B$, $B \leq_m A$.\end{enumerate}\end{defn}In other words, complete computably enumerable sets are the``hardest'' computably enumerable sets possible. They allow one toanswer questions about \emph{any} computably enumerable set.\begin{thm}$K$, $K_0$, and $K_1$ are all complete computably enumerable sets.\end{thm}\begin{proof}To see that $K_0$ is complete, let $B$ be any computablyenumerable set. Then for some index $e$,\[B = W_e = \Setabs{x}{\cfind{e}(x) \fdefined}.\]Let $f$ be the function $f(x) = \tuple{e, x}$. Then for every naturalnumber $x$, $x \in B$ if and only if $f(x) \in K_0$. In other words, $f$reduces $B$ to~$K_0$.To see that $K_1$ is complete, note that in the proof of\olref[k1]{prop:k1} we reduced $K_0$ to it. So, by\olref[ppr]{prop:trans-red}, any computably enumerable set can bereduced to~$K_1$ as well.$K$ can be reduced to $K_0$ in much the same way.\end{proof}\begin{prob}Give a reduction of $K$ to $K_0$.\end{prob}\begin{digress}So, it turns out that all the examples of computably enumerable setsthat we have considered so far are either computable, or complete.This should seem strange!{} Are there any examples of computablyenumerable sets that are neither computable nor complete? The answeris yes, but it wasn't until the middle of the 1950s that this wasestablished by Friedberg and Muchnik, independently.\end{digress}\end{document}

content/computability/computability-theory/k-1.tex

% Part: computability% Chapter: computability-theory% Section: k-1\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{k1}\olsection{An Example of Reducibility}Let us consider an application of \olref[ppr]{prop:reduce}.\begin{prop}\ollabel{prop:k1}Let\[K_1 = \Setabs{e}{\cfind{e}(0) \fdefined}.\]Then $K_1$ is computably enumerable but not computable.\end{prop}\begin{proof}Since $K_1 = \Setabs{e}{\lexists[s][T(e,0,s)]}$, $K_1$ is computablyenumerable by \olref[eqc]{thm:exists-char}.To show that $K_1$ is not computable, let us show that $K_0$ isreducible to it.\begin{explain}This is a little bit tricky, since using $K_1$ we canonly ask questions about computations that start with a particularinput, $0$. Suppose you have a smart friend who can answer questionsof this type (friends like this are known as ``oracles''). Thensuppose someone comes up to you and asks you whether or not $\tuple{e,  x}$ is in $K_0$, that is, whether or not machine $e$ halts on input$x$. One thing you can do is build another machine, $e_x$, that, for\emph{any} input, ignores that input and instead runs~$e$ on input$x$. Then clearly the question as to whether machine $e$ halts oninput $x$ is equivalent to the question as to whether machine $e_x$halts on input $0$ (or any other input). So, then you ask your friendwhether this new machine, $e_x$, halts on input $0$; your friend'sanswer to the modified question provides the answer to the originalone. This provides the desired reduction of $K_0$ to~$K_1$.\end{explain}Using the universal partial computable function, let $f$be the 3-ary function defined by\[f(x,y,z) \simeq \cfind{x}(y).\]Note that $f$ ignores its third input entirely. Pick an index $e$ suchthat $f = \cfind{e}[3]$; so we have\[\cfind{e}[3](x,y,z) \simeq \cfind{x}(y).\]By the $s$-$m$-$n$ theorem, there is a function $s(e,x,y)$ such that, forevery $z$,\begin{align*}\cfind{s(e,x,y)}(z) & \simeq \cfind{e}[3](x,y,z) \\& \simeq \cfind{x}(y).\end{align*}\begin{explain}In terms of the informal argument above, $s(e,x,y)$ is an index forthe machine that, for any input $z$, ignores that input and computes$\cfind{x}(y)$.\end{explain}In particular, we have\[\cfind{s(e,x,y)}(0) \fdefined \quad \text{if and only if} \quad\cfind{x}(y) \fdefined.\]In other words, $\tuple{x, y} \in K_0$ if and only if $s(e,x,y) \inK_1$. So the function $g$ defined by\[g(w) = s(e,(w)_0,(w)_1)\]is a reduction of $K_0$ to~$K_1$.\end{proof}\end{document}

content/computability/computability-theory/total.tex

% Part: computability% Chapter: computability-theory% Section: total\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{tot}\olsection{Totality is Undecidable}Let us consider one more example of using the $s$-$m$-$n$ theorem to showthat something is noncomputable. Let $\fn{Tot}$ be the set of indicesof total computable functions, i.e.\[\fn{Tot} = \Setabs{x}{\text{for every $y$, $\cfind{x}(y)\fdefined$}}.\]\begin{prop}\ollabel{prop:total}$\fn{Tot}$ is not computable.\end{prop}\begin{proof}To see that $\fn{Tot}$ is not computable, it suffices to show that $K$is reducible to it. Let $h(x,y)$ be defined by\[h(x,y) \simeq\begin{cases}0 & \text{if $x \in K$} \\\fundefined & \text{otherwise}\end{cases}\]Note that $h(x,y)$ does not depend on $y$ at all. It shouldnot be hard to see that $h$~is partial computable: on input $x, y$, thewe compute~$h$ by first simulating the function~$\cfind{x}$ on input~$x$; ifthis computation halts, $h(x,y)$ outputs $0$ and halts. So$h(x,y)$ is just $\Zero(\umin{s}{T(x,x,s)})$, where $\Zero$ is the constant zerofunction.Using the $s$-$m$-$n$ theorem, there is a primitive recursivefunction~$k(x)$ such that for every $x$ and~$y$,\[\cfind{k(x)}(y) =\begin{cases}0 & \text{if $x \in K$} \\\fundefined & \text{otherwise}\end{cases}\]So $\cfind{k(x)}$ is total if $x \in K$, and undefined otherwise. Thus,$k$ is a reduction of $K$ to~$\fn{Tot}$.\end{proof}\begin{digress}It turns out that $\fn{Tot}$ is not even computably enumerable---itscomplexity lies further up on the ``arithmetical hierarchy.''  But wewill not worry about this strengthening here.\end{digress}\end{document}

content/computability/computability-theory/rice-theorem.tex

% Part: computability% Chapter: computability-theory% Section: rice-theorem\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{rce}\olsection{Rice's Theorem}If you think about it, you will see that the specifics of $\fn{Tot}$do not play into the proof of \olref[tot]{prop:total}. We designed$h(x,y)$ to act like the constant function $j(y) = 0$ exactly when $x$is in $K$; but we could just as well have made it act like any otherpartial computable function under those circumstances. Thisobservation lets us state a more general theorem, which says, roughly,that no nontrivial property of computable functions is decidable.Keep in mind that $\cfind{0}$, $\cfind{1}$, $\cfind{2}$,~\dots is ourstandard enumeration of the partial computable functions.\begin{thm}[Rice's Theorem]  Let $C$ be any set of partial computable functions, and let $A =  \Setabs{n}{\cfind{n} \in C}$. If $A$ is computable, then either $C$  is empty or $C$ is the set of all the partial computable  functions.\end{thm}An {\em index set} is a set $A$ with the property that if $n$ and $m$are indices which ``compute'' the same function, then either both $n$and $m$ are in $A$, or neither is. It is not hard to see that theset~$A$ in the theorem has this property. Conversely, if $A$~is anindex set and $C$~is the set of functions computed by these indices,then $A = \Setabs{n}{\cfind{n} \in C}$.\begin{explain}With this terminology, Rice's theorem is equivalent to saying that nonontrivial index set is decidable. To understand what the theoremsays, it is helpful to emphasize the distinction between\emph{programs} (say, in your favorite programming language) and thefunctions they compute. There are certainly questions about programs(indices), which are syntactic objects, that are computable: does thisprogram have more than 150 symbols? Does it have more than 22 lines?Does it have a ``while'' statement? Does the string ``hello world''ever appear as the argument to a ``print'' statement? Rice's theoremsays that no nontrivial question about the program's \emph{behavior}is computable. This includes questions like these: does the programhalt on input $0$? Does it ever halt? Does it ever output an evennumber?\end{explain}\begin{proof}[Proof of Rice's theorem]Suppose $C$ is neither empty nor the set of all the partialcomputable functions, and let $A$ be the set of indices of functionsin~$C$. We will show that if $A$ were computable, we could solve thehalting problem; so $A$~is not computable.Without loss of generality, we can assume that the function $f$ whichis nowhere defined is not in $C$ (otherwise, switch $C$ and itscomplement in the argument below). Let $g$ be any function in~$C$. Theidea is that if we could decide~$A$, we could tell the differencebetween indices computing~$f$, and indices computing~$g$; and then wecould use that capability to solve the halting problem.Here's how. Using the universal partial computable functions, we candefine a function\[h(x,y) \simeq\begin{cases}\text{undefined} & \text{if $\cfind{x}(x) \fundefined$} \\g(y) & \text{otherwise.}\end{cases}\]To compute $h$, first we try to compute $\cfind{x}(x)$; if thatcomputation halts, we go on to compute~$g(y)$; and if {\em that}computation halts, we return the output. More formally, we can write\[h(x,y) \simeq \Proj{2}{0}(g(y),\fn{Un}(x,x)).\]where $\Proj{2}{0}(z_0, z_1) = z_0$ is the $2$-place projectionfunction returning the $0$-th argument, which is computable.Then $h$ is a composition of partial computable functions, and the rightside is defined and equal to~$g(y)$ just when $\fn{Un}(x,x)$ and$g(y)$ are both defined.Notice that for a fixed~$x$, if $\cfind{x}(x)$ is undefined, then$h(x,y)$ is undefined for every~$y$; and if $\cfind{x}(x)$ is defined,then $h(x,y) \simeq g(y)$. So, for any fixed value of~$x$, either$h(x,y)$ acts just like $f$ or it acts just like $g$, and decidingwhether or not $\cfind{x}(x)$ is defined amounts to deciding which ofthese two cases holds. But this amounts to deciding whether or not$h_x(y) \simeq h(x,y)$ is in~$C$ or not, and if $A$ were computable,we could do just that.More formally, since $h$~is partial computable, it is equal to thefunction $\cfind{e}$ for some index~$e$. By the $s$-$m$-$n$ theoremthere is a primitive recursive function~$s$ such that for each~$x$,$\cfind{s(e,x)}(y) = h_x(y)$. Now we have that for each $x$, if$\cfind{x}(x) \fdefined$, then $\cfind{s(e,x)}$ is the same functionas~$g$, and so $s(e,x)$ is in $A$. On the other hand, if $\cfind{x}(x)\uparrow$, then $\cfind{s(e,x)}$ is the same function as~$f$, and so$s(e,x)$ is not in~$A$. In other words, we have that for every~$x$, $x\in K$ if and only if $s(e,x) \in A$. If $A$ were computable,$K$~would be also, which is a contradiction. So $A$ is not computable.\end{proof}Rice's theorem is very powerful. The following immediate corollaryshows some sample applications.\begin{cor}The following sets are undecidable.\begin{enumerate}\item $\Setabs{x}{\text{$17$ is in the range of $\cfind{x}$}}$\item $\Setabs{x}{\text{$\cfind{x}$ is constant}}$\item $\Setabs{x}{\text{$\cfind{x}$ is total}}$\item $\Setabs{x}{\text{whenever $y < y'$, $\cfind{x}(y) \fdefined$, and    if $\cfind{x}(y') \fdefined$, then $\cfind{x}(y) < \cfind{x}(y')$}}$\end{enumerate}\end{cor}\begin{proof}  These are all nontrivial index sets.\end{proof}\end{document}

content/computability/computability-theory/fixed-point-thm.tex

% Part: computability% Chapter: computability-theory% Section: fixed-point-thm\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{fix}\olsection{The Fixed-Point Theorem}Let's consider the halting problem again. As temporarynotation, let us write $\gn{\cfind{x}(y)}$ for $\tuple{x, y}$; think ofthis as representing a ``name'' for the value $\cfind{x}(y)$. With thisnotation, we can reword one of our proofs that the halting problem isundecidable.Question: is there a computable function $h$, with thefollowing property? For every $x$ and $y$,\[h(\gn{\cfind{x}(y)}) =\begin{cases}1 & \text{if $\cfind{x}(y) \fdefined$} \\0 & \text{otherwise.}\end{cases}\]Answer: No; otherwise, the partial function\[g(x) \simeq\begin{cases}0 & \text{if $h(\gn{\cfind{x}(x)}) = 0$} \\\text{undefined} & \text{otherwise}\end{cases}\]would be computable, and so have some index~$e$. But then we have\[\cfind{e}(e) \simeq\begin{cases}0 & \text{if $h(\gn{\cfind{e}(e)}) = 0$} \\\text{undefined} & \text{otherwise,}\end{cases}\]in which case $\cfind{e}(e)$ is defined if and only if it isn't, acontradiction.Now, take a look at the equation with $\cfind{e}$. There is an instance ofself-reference there, in a sense: we have arranged for the value of$\cfind{e}(e)$ to depend on $\gn{\cfind{e}(e)}$, in a certain way. Thefixed-point theorem says that we {\em can} do this, in general---notjust for the sake of proving contradictions.\olref{lem:fixed-equiv} gives two equivalent ways of stating thefixed-point theorem. Logically speaking, the fact that the statementsare equivalent follows from the fact that they are both true; but whatwe really mean is that each one follows straightforwardly from theother, so that they can be taken as alternative statements of the sametheorem.\begin{lem}\ollabel{lem:fixed-equiv}The following statements are equivalent:\begin{enumerate}\item For every partial computable function $g(x,y)$, there is an  index~$e$ such that for every~$y$,\[\cfind{e}(y) \simeq g(e,y).\]\item For every computable function~$f(x)$, there is an index~$e$ such  that for every~$y$,\[\cfind{e}(y) \simeq \cfind{f(e)}(y).\]\end{enumerate}\end{lem}\begin{proof}$(1) \Rightarrow (2)$: Given $f$, define $g$ by $g(x,y) \simeq\fn{Un}(f(x),y)$. Use (1) to get an index~$e$ such that for every~$y$,\begin{align*}\cfind{e}(y) & = \fn{Un}(f(e),y) \\& = \cfind{f(e)}(y).\end{align*}$(2) \Rightarrow (1)$: Given $g$, use the $s$-$m$-$n$ theorem to get $f$ suchthat for every $x$ and~$y$, $\cfind{f(x)}(y) \simeq g(x,y)$. Use (2) toget an index~$e$ such that\begin{align*}\cfind{e}(y) & = \cfind{f(e)}(y) \\& = g(e,y).\end{align*}This concludes the proof.\end{proof}\begin{explain}Before showing that statement (1) is true (and hence (2) as well),consider how bizarre it is. Think of $e$ as being a computer program;statement (1) says that given any partial computable $g(x,y)$, you canfind a computer program $e$ that computes $g_e(y) \simeq g(e,y)$. Inother words, you can find a computer program that computes a functionthat references the program itself.\end{explain}\begin{thm}The two statements in \olref{lem:fixed-equiv} aretrue. Specifically, for every partial computable function $g(x,y)$,there is an index~$e$ such that for every~$y$,\[\cfind{e}(y) \simeq g(e,y).\]\end{thm}\begin{proof}The ingredients are already implicit in the discussion of the haltingproblem above. Let $\fn{diag}(x)$ be a computable function which for each$x$ returns an index for the function $f_x(y) \simeq \cfind{x}(x,y)$,i.e.\[\cfind{\fn{diag}(x)}(y) \simeq \cfind{x}(x,y).\]Think of $\fn{diag}$ as a function that transforms a program for a 2-aryfunction into a program for a 1-ary function, obtained by fixing theoriginal program as its first argument. The function $\fn{diag}$ can bedefined formally as follows: first define $s$ by\[s(x,y) \simeq \fn{Un}^2(x,x,y),\]where $\fn{Un}^2$ is a 3-ary function that is universal for partial computable2-ary functions. Then, by the $s$-$m$-$n$ theorem, we can find a primitiverecursive function $\fn{diag}$ satisfying\[\cfind{\fn{diag}(x)}(y) \simeq s(x,y).\]Now, define the function $l$ by\[l(x,y) \simeq g(\fn{diag}(x),y).\]and let $\gn{l}$ be an index for $l$. Finally, let $e = \fn{diag}(\gn{l})$.Then for every $y$, we have\begin{align*}\cfind{e}(y) & \simeq \cfind{\fn{diag}(\gn{l})}(y) \\& \simeq \cfind{\gn{l}}(\gn{l}, y) \\& \simeq l(\gn{l}, y) \\& \simeq g(\fn{diag}(\gn{l}),y) \\& \simeq g(e, y),\end{align*}as required.\end{proof}\begin{explain}What's going on? Suppose you are given the task of writing a computerprogram that prints itself out. Suppose further, however, that you areworking with a programming language with a rich and bizarre library ofstring functions. In particular, suppose your programming language hasa function $\fn{diag}$ which works as follows: given an inputstring~$s$, $\fn{diag}$ locates each instance of the symbol `x'occurring in~$s$, and replaces it by a quoted version of the originalstring. For example, given the string\begin{quote}\begin{verbatim}hello x world\end{verbatim}\end{quote}as input, the function returns\begin{quote}\begin{verbatim}hello 'hello x world' world\end{verbatim}\end{quote}as output. In that case, it is easy to write the desired program; youcan check that\begin{quote}\begin{verbatim}print(diag('print(diag(x))'))\end{verbatim}\end{quote}does the trick. For more common programming languages like C++ andJava, the same idea (with a more involved implementation) still works.We are only a couple of steps away from the proof of the fixed-pointtheorem. Suppose a variant of the print function $\fn{print}(x,y)$accepts a string $x$ and another numeric argument $y$, and prints thestring $x$ repeatedly, $y$ times. Then the ``program''\begin{quote}\begin{verbatim}getinput(y);print(diag('getinput(y); print(diag(x), y)'), y)\end{verbatim}\end{quote}prints itself out $y$ times, on input $y$. Replacing the$\fn{getinput}$---$\fn{print}$---$\fn{diag}$ skeleton by anarbitrary function $g(x,y)$ yields\begin{quote}\begin{verbatim}g(diag('g(diag(x), y)'), y)\end{verbatim}\end{quote}which is a program that, on input $y$, runs $g$ on the program itselfand $y$. Thinking of ``quoting'' with ``using an index for,'' we havethe proof above.For now, it is o.k.\ if you want to think of the proof as formaltrickery, or black magic. But you should be able to reconstruct thedetails of the argument given above. When we prove the incompletenesstheorems (and the related ``fixed-point theorem'') we will discussother ways of understanding why it works.\end{explain}\begin{tagblock}{lambda}\begin{digress}The same idea can be used to get a ``fixed point'' combinator. Supposeyou have a lambda term $g$, and you want another term $k$ with theproperty that $k$ is $\beta$-equivalent to $gk$. Define terms\[\fn{diag}(x) = xx\]and\[l(x) = g(\fn{diag}(x))\]using our notational conventions; in other words, $l$ is the term$\lambd[x][g(xx)]$. Let $k$ be the term $ll$. Then we have\begin{align*}k & = (\lambd[x][g(xx)])(\lambd[x][g(xx)]) \\& \red  g((\lambd[x][g(xx)])(\lambd[x][g(xx)])) \\& = gk.\end{align*}If one takes\[Y = \lambd[g][((\lambd[x][g(xx)])(\lambd[x][g(xx)]))]\]then $Yg$ and $g(Yg)$ reduce to a common term; so $Yg \equiv_\betag(Yg)$. This is known as ``Curry's combinator.'' If instead one takes\[Y = (\lambd[xg][g(xxg)])(\lambd[xg][g(xxg)])\]then in fact $Yg$ reduces to $g(Yg)$, which is a stronger statement.This latter version of $Y$ is known as ``Turing's combinator.''\end{digress}\end{tagblock}\end{document}

content/computability/computability-theory/application-fixed-point.tex

% Part: computability% Chapter: computability-theory% Section: applications-fixed-point\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{apf}\olsection{Applying the Fixed-Point Theorem}The fixed-point theorem essentially lets us define partial computablefunctions in terms of their indices. For example, we can find anindex $e$ such that for every $y$,\[\cfind{e}(y) = e + y.\]As another example, one can use the proof of the fixed-point theoremto design a program in Java or C++ that prints itself out.Remember that if for each $e$, we let $W_e$ be the domain of $\cfind{e}$,then the sequence $W_0$, $W_1$, $W_2$,~\dots enumerates the computablyenumerable sets. Some of these sets are computable. One can ask ifthere is an algorithm which takes as input a value $x$, and, if $W_x$happens to be computable, returns an index for its characteristicfunction. The answer is ``no,'' there is no such algorithm:\begin{thm}There is no partial computable function $f$ with the followingproperty: whenever $W_e$ is computable, then $f(e)$ is defined and$\cfind{f(e)}$ is its characteristic function.\end{thm}\begin{proof}Let $f$ be any computable function; we will construct an $e$such that $W_e$ is computable, but $\cfind{f(e)}$ is not itscharacteristic function. Using the fixed point theorem, we can find anindex $e$ such that\[\cfind{e}(y) \simeq\begin{cases}0 & \text{if $y=0$ and $\cfind{f(e)}(0) \fdefined = 0$} \\\text{undefined} & \text{otherwise.}\end{cases}\]That is, $e$ is obtained by applying the fixed-point theorem to thefunction defined by\[g(x,y) \simeq\begin{cases}0 & \text{if $y=0$ and $\cfind{f(x)}(0) \fdefined = 0$} \\\text{undefined} & \text{otherwise.}\end{cases}\]Informally, we can see that $g$ is partial computable, as follows: oninput $x$ and $y$, the algorithm first checks to see if $y$ is equalto~$0$. If it is, the algorithm computes $f(x)$, and then uses theuniversal machine to compute $\cfind{f(x)}(0)$. If this last computationhalts and returns~$0$, the algorithm returns~$0$; otherwise, thealgorithm doesn't halt.But now notice that if $\cfind{f(e)}(0)$ is defined and equal to $0$,then $\cfind{e}(y)$ is defined exactly when $y$ is equal to $0$, so $W_e =\{ 0 \}$. If $\cfind{f(e)}(0)$ is not defined, or is defined but notequal to $0$, then $W_e = \emptyset$. Either way, $\cfind{f(e)}$ is notthe characteristic function of~$W_e$, since it gives the wrong answeron input $0$.\end{proof}\end{document}

content/computability/computability-theory/def-functions-self-reference.tex

% Part: computability% Chapter: computability-theory% Section: def-functions-self-reference\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{thy}{slf}\olsection{Defining Functions using Self-Reference}It is generally useful to be able to define functions in terms ofthemselves. For example, given computable functions $k$, $l$, and~$m$,the fixed-point lemma tells us that there is a partial computablefunction~$f$ satisfying the following equation for every~$y$:\[f(y) \simeq\begin{cases}k(y) & \text{if $l(y) = 0$} \\f(m(y)) & \text{otherwise.}\end{cases}\]Again, more specifically, $f$~is obtained by letting\[g(x,y) \simeq\begin{cases}k(y) & \text{if $l(y) = 0$} \\\cfind{x}(m(y)) & \text{otherwise}\end{cases}\]and then using the fixed-point lemma to find an index~$e$ such that$\cfind{e}(y) = g(e,y)$.For a concrete example, the ``greatest common divisor'' function$\fn{gcd}(u,v)$ can be defined by\[\fn{gcd}(u,v) \simeq\begin{cases}v & \text{if $u = 0$} \\\fn{gcd}(\fn{mod}(v, u), u) & \text{otherwise}\end{cases}\]where $\fn{mod}(v, u)$ denotes the remainder of dividing $v$by~$u$. An appeal to the fixed-point lemma shows that $\fn{gcd}$ ispartial computable. (In fact, this can be put in the format above,letting $y$ code the pair $\tuple{u, v}$.) A subsequent inductionon~$u$ then shows that, in fact, $\fn{gcd}$ is total.Of course, one can cook up self-referential definitions that are muchfancier than the examples just discussed. Most programming languagessupport definitions of functions in terms of themselves, one way oranother. Note that this is a little bit less dramatic than being ableto define a function in terms of an \emph{index} for an algorithmcomputing the functions, which is what, in full generality, thefixed-point theorem lets you do.\end{document}