Computability

Recursive Functions

content/computability/recursive-functions/recursive-functions.tex

% Part: computability% Chapter: recursive-functions\documentclass[../../../include/open-logic-chapter]{subfiles}\begin{document}\olchapter{cmp}{rec}{Recursive Functions}\begin{editorial}  These are Jeremy Avigad's notes on recursive functions, revised and  expanded by Richard Zach. This chapter does contain some exercises,  and can be included independently to provide the basis for a  discussion of arithmetization of syntax.\end{editorial}\olimport{introduction}\olimport{primitive-recursion}\olimport{composition}\olimport{pr-functions}\olimport{notation-pr-functions}\olimport{pr-functions-computable}\olimport{examples}\olimport{pr-relations}\olimport{bounded-minimization}\olimport{primes}\olimport{sequences}\olimport{trees}\olimport{other-recursions}\olimport{non-pr-functions}\olimport{partial-functions}\olimport{normal-form}\olimport{halting-problem}\olimport{general-recursive-functions}\OLEndChapterHook\end{document}

content/computability/recursive-functions/introduction.tex

% Part: computability% Chapter: recursive-functions% Section: introduction\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{int}\olsection{Introduction}In order to develop a mathematical theory of computability, one has to,first of all, develop a \emph{model} of computability.  We now think ofcomputability as the kind of thing that computers do, and computerswork with symbols.  But at the beginning of the development oftheories of computability, the paradigmatic example of computation was\emph{numerical} computation.  Mathematicians were always interestedin number-theoretic functions, i.e., functions $f\colon \Nat^n \to\Nat$ that can be computed. So it is not surprising that at thebeginning of the theory of computability, it was such functions thatwere studied.  The most familiar examples of computable numericalfunctions, such as addition, multiplication, exponentiation (ofnatural numbers) share an interesting feature: they can be defined\emph{recursively}.  It is thus quite natural to attempt a generaldefinition of \emph{computable function} on the basis of recursivedefinitions.  Among the many possible ways to define number-theoreticfunctions recursively, one particularly simple pattern of definitionhere becomes central: so-called \emph{primitive recursion}.In addition to computable functions, we might be interested incomputable sets and relations. A set is computable if we can computethe answer to whether or not a given number is !!a{element} of theset, and a relation is computable iff we can compute whether or not atuple $\tuple{n_1, \dots, n_k}$ is !!a{element} of the relation.  Byconsidering the \emph{characteristic function} of a set or relation,discussion of computable sets and relations can be subsumed under thatof computable functions.  Thus we can define primitive recursiverelations as well, e.g., the relation ``$n$ evenly divides $m$'' is aprimitive recursive relation.Primitive recursive functions---those that can be defined using justprimitive recursion---are not, however, the only computablenumber-theoretic functions. Many generalizations of primitiverecursion have been considered, but the most powerful andwidely-accepted additional way of computing functions is by unboundedsearch.  This leads to the definition of \emph{partial recursive  functions}, and a related definition to \emph{general recursive  functions}.  General recursive functions are computable and total,and the definition characterizes exactly the partial recursivefunctions that happen to be total.  Recursive functions can simulateevery other model of computation (Turing machines, lambda calculus,etc.) and so represent one of the many accepted models of computation.\end{document}

content/computability/recursive-functions/primitive-recursion.tex

% Part: computability% Chapter: recursive-functions% Section: primitive-recursion\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{pre}\olsection{Primitive Recursion}A characteristic of the natural numbers is that every natural numbercan be reached from~$0$ by applying the successor operation~$+1$finitely many times---any natural number is either~$0$ or thesuccessor of \dots{} the successor of~$0$. One way to specify afunction~$h\colon\Nat \to \Nat$ that makes use of this fact is this:(a)~specify what the value of $h$ is for argument~$0$, and (b)~alsospecify how to, given the value of $h(x)$, compute the value of$h(x+1)$. For (a) tells us directly what $h(0)$ is, so $h$~is definedfor~$0$. Now, using the instruction given by (b) for $x=0$, we cancompute $h(1) = h(0+1)$ from~$h(0)$. Using the same instructions for$x=1$, we compute $h(2) = h(1+1)$ from~$h(1)$, and so on. For everynatural number~$x$, we'll eventually reach the step where we define$h(x)$ from $h(x+1)$, and so $h(x)$ is defined for all $x \in \Nat$.For instance, suppose we specify $h\colon \Nat \to \Nat$ by the followingtwo equations:\begin{align*}h(0) & =  1\\h(x+1) & =  2 \cdot h(x)\end{align*}If we already know how to multiply, then these equations give us theinformation required for (a) and~(b) above. By successively applyingthe second equation, we get that\begin{align*}  h(1) & = 2\cdot h(0) = 2,\\  h(2) & = 2\cdot h(1) = 2\cdot 2,\\  h(3) & = 2 \cdot h(2) = 2\cdot 2 \cdot 2,\\  & \vdots\end{align*}We see that the function~$h$ we have specified is $h(x) = 2^x$.The characteristic feature of the natural numbers guarantees thatthere is only one function~$h$ that meets these two criteria.  A pairof equations like these is called a \emph{definition by primitiverecursion} of the function~$h$. It is so-called because we define~$h$``recursively,'' i.e., the definition, specifically the secondequation, involves $h$ itself on the right-hand-side. It is``primitive'' because in defining $h(x+1)$ we only use thevalue~$h(x)$, i.e., the immediately preceding value. This is thesimplest way of defining a function on~$\Nat$ recursively.We can define even more fundamental functions like addition andmultiplication by primitive recursion. In these cases, however, thefunctions in question are $2$-place. We fix one of the argumentplaces, and use the other for the recursion. E.g, to define$\Add(x, y)$ we can fix~$x$ and define the value first for $y=0$and then for $y+1$ in terms of~$y$. Since $x$ is fixed, it will appearon the left and on the right side of the defining equations.\begin{align*}\Add(x,0) & =  x\\\Add(x,y+1) & =  \Add(x,y)+1\end{align*}These equations specify the value of $\Add$ for all $x$\emph{and}~$y$. To find $\Add(2,3)$, for instance, we apply thedefining equations for $x = 2$, using the first to find$\Add(2,0) = 2$, then using the second to successively find$\Add(2,1) = 2 + 1 = 3$, $\Add(2, 2) = 3 + 1 = 4$, $\Add(2,3) = 4 + 1 = 5$.In the definition of $\Add$ we used $+$ on the right-hand-side ofthe second equation, but only to add~$1$. In other words, we used thesuccessor function $\Succ(z) = z+1$ and applied it to the previous value$\Add(x,y)$ to define $\Add(x,y+1)$. So we can think of therecursive definition as given in terms of a single function which weapply to the previous value. However, it doesn't hurt---and sometimesis necessary---to allow the function to depend not just on the previousvalue but also on $x$ and~$y$. Consider:\begin{align*}  \Mult(x,0) & =  0 \\  \Mult(x,y+1) & =  \Add(\Mult(x,y),x)\end{align*}This is a primitive recursive definition of a function $\Mult$ byapplying the function $\Add$ to both the preceding value$\Mult(x,y)$ and the first argument~$x$. It also defines thefunction~$\Mult(x,y)$ for all arguments $x$ and~$y$. For instance,$\Mult(2,3)$ is determined by successively computing $\Mult(2,0)$,$\Mult(2,1)$, $\Mult(2,2)$, and~$\Mult(2,3)$:\begin{align*}  \Mult(2,0) & = 0\\  \Mult(2,1) & = \Mult(2,0+1) =  \Add(\Mult(2,0), 2) = \Add(0, 2) = 2\\  \Mult(2,2) & = \Mult(2,1+1) =  \Add(\Mult(2,1), 2) = \Add(2, 2) = 4\\  \Mult(2,3) & = \Mult(2,2+1) =  \Add(\Mult(2,2), 2) = \Add(4, 2) = 6\end{align*}The general pattern then is this: to give a primitive recursivedefinition of a function~$h(x_0, \dots, x_{k-1}, y)$, we provide twoequations. The first defines the value of $h(x_0, \dots, x_{k-1}, 0)$without reference to~$h$. The second defines the value of $h(x_0,\dots, x_{k-1}, y+1)$ in terms of $h(x_0, \dots, x_{k-1}, y)$, theother arguments $x_0$, \dots,~$x_{k-1}$, and~$y$. Only the immediatelypreceding value of~$h$ may be used in that second equation.  If wethink of the operations given by the right-hand-sides of these twoequations as themselves being functions $f$ and~$g$, then the generalpattern to define a new function~$h$ by primitive recursion is this:\begin{align*}  h(x_0, \dots, x_{k-1}, 0) & = f(x_0, \dots, x_{k-1})\\  h(x_0, \dots, x_{k-1}, y+1) & =  g(x_0, \dots, x_{k-1}, y, h(x_0, \dots, x_{k-1}, y))\end{align*}  In the case of $\Add$, we have $k=1$ and $f(x_0) = x_0$ (theidentity function), and $g(x_0, y, z) = z + 1$ (the $3$-place functionthat returns the successor of its third argument):\begin{align*}  \Add(x_0, 0) & = f(x_0) = x_0\\  \Add(x_0, y+1) & = g(x_0, y, \Add(x_0, y)) =  \Succ(\Add(x_0, y))\end{align*}In the case of $\Mult$, we have $f(x_0) = 0$ (the constantfunction always returning~$0$) and $g(x_0, y, z) = \Add(z,x_0)$(the $3$-place function that returns the sum of its last and firstargument):\begin{align*}  \Mult(x_0,0) & =  f(x_0) = 0 \\  \Mult(x_0,y+1) & =  g(x_0, y, \Mult(x_0,y)) =  \Add(\Mult(x_0,y), x_0)\end{align*}\end{document}

content/computability/recursive-functions/composition.tex

% Part: computability% Chapter: recursive-functions% Section: composition\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{com}\olsection{Composition}If $f$ and $g$ are two one-place functions of natural numbers, we cancompose them: $h(x) = f(g(x))$. The new function~$h(x)$ is thendefined by \emph{composition} from the functions $f$ and~$g$. We'dlike to generalize this to functions of more than one argument.Here's one way of doing this: suppose $f$ is a $k$-place function,and $g_0$, \dots, $g_{k-1}$ are $k$ functions which are all$n$-place. Then we can define a new $n$-place function $h$ as follows:\[h(x_0, \dots, x_{n-1}) =f(g_0(x_0, \dots, x_{n-1}), \dots, g_{k-1}(x_0, \dots, x_{n-1}))\]If $f$ and all $g_i$ are computable, so is $h$: To compute $h(x_0,\dots, x_{n-1})$, first compute the values $y_i = g_i(x_0, \dots,x_{n-1})$ for each $i = 0$, \dots,~$k-1$. Then feed these values into$f$ to compute $h(x_0, \dots, x_{k-1}) = f(y_0, \dots, y_{k-1})$.This may seem like an overly restrictive characterization of whathappens when we compute a new function using some existing ones. Forone thing, sometimes we do not use all the arguments of a function, aswhen we defined $g(x, y, z) = \Succ(z)$ for use in the primitiverecursive definition of~$\Add$. Suppose we are allowed use of thefollowing functions:\[\Proj{n}{i}(x_0, \dots, x_{n-1}) = x_i\]The functions~$\Proj{k}{i}$ are called \emph{projection} functions:$\Proj{n}{i}$ is an $n$-place function. Then $g$ can be defined by\[g(x, y, z) = \Succ(\Proj{3}{2}(x, y, z)).\]Here the role of $f$ is played by the $1$-place function $\Succ$, so$k=1$. And we have one $3$-place function $\Proj{3}{2}$ which playsthe role of $g_0$. The result is a $3$-place function that returns thesuccessor of the third argument.The projection functions also allow us to define new functions byreordering or identifying arguments. For instance, the function $h(x)= \Add(x, x)$ can be defined by\[h(x_0) = \Add(\Proj{1}{0}(x_0),\Proj{1}{0}(x_0)).\]Here $k=2$, $n=1$, the role of $f(y_0,y_1)$ is played by $\Add$, andthe roles of $g_0(x_0)$ and $g_1(x_0)$ are both playedby~$\Proj{1}{0}(x_0)$, the one-place projection function (aka theidentity function).If $f(y_0, y_1)$ is a function we already have, we can define thefunction $h(x_0, x_1) = f(x_1, x_0)$ by\[h(x_0, x_1) = f(\Proj{2}{1}(x_0, x_1),\Proj{2}{0}(x_0, x_1)).\]Here $k=2$, $n = 2$, and the roles of $g_0$ and $g_1$ are played by$\Proj{2}{1}$ and~$\Proj{2}{0}$, respectively.You may also worry that $g_0$, \dots,~$g_{k-1}$ are all requiredto have the same arity~$n$. (Remember that the \emph{arity} of afunction is the number of arguments; an $n$-place function hasarity~$n$.) But adding the projection functions provides the desiredflexibility. For example, suppose $f$ and~$g$ are $3$-place functionsand $h$~is the $2$-place function defined by\[h(x,y) = f(x,g(x,x,y),y).\]The definition of~$h$ can be rewritten with the projectionfunctions, as\[h(x,y) = f(\Proj{2}{0}(x,y), g(\Proj{2}{0}(x,y), \Proj{2}{0}(x,y),\Proj{2}{1}(x,y)), \Proj{2}{1}(x,y)).\]Then $h$ is the composition of $f$ with $\Proj{2}{0}$, $l$, and$\Proj{2}{1}$, where\[l(x,y) = g(\Proj{2}{0}(x,y),\Proj{2}{0}(x,y),\Proj{2}{1}(x,y)),\]i.e., $l$ is the composition of $g$ with $\Proj{2}{0}$, $\Proj{2}{0}$,and~$\Proj{2}{1}$.\end{document}

content/computability/recursive-functions/pr-functions.tex

% Part: computability% Chapter: recursive-functions% Section: pr-functions\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{prf}\olsection{Primitive Recursion Functions}Let us record again how we can define new functions from existing onesusing primitive recursion and composition.\begin{defn}  \ollabel{defn:primitive-recursion} Suppose $f$ is a $k$-place  function ($k\ge 1$) and $g$ is a $(k+2)$-place function. The  function defined by \emph{primitive recursion from $f$ and $g$} is  the $(k+1)$-place function~$h$ defined by the equations  \begin{align*}    h(x_0,\dots,x_{k-1},0) & =  f(x_0,\dots,x_{k-1}) \\    h(x_0,\dots,x_{k-1},y+1) & = g(x_0,\dots,x_{k-1}, y, h(x_0,\dots,x_{k-1}, y))  \end{align*}\end{defn}\begin{defn}  \ollabel{defn:composition} Suppose $f$ is a $k$-place function, and  $g_0$, \dots, $g_{k-1}$ are $k$ functions which are all  $n$-place. The function defined by \emph{composition from $f$ and    $g_0$, \dots,~$g_{k-1}$} is the $n$-place function~$h$ defined by  \[  h(x_0, \dots, x_{n-1}) =  f(g_0(x_0, \dots, x_{n-1}), \dots, g_{k-1}(x_0, \dots, x_{n-1})).  \]\end{defn}In addition to $\Succ$ and the projection functions\[\Proj{n}{i}(x_0,\dots,x_{n-1}) = x_i,\]for each natural number $n$ and $i < n$, we will include among theprimitive recursive functions the function~$\Zero(x) = 0$.\begin{defn}  The set of primitive recursive functions is the set of functions   from $\Nat^n$ to $\Nat$, defined inductively by the  following clauses:  \begin{enumerate}  \item $\Zero$ is primitive recursive.  \item $\Succ$ is primitive recursive.  \item Each projection function $\Proj{n}{i}$ is primitive recursive.  \item If $f$ is a $k$-place primitive recursive function and $g_0$,    \dots,~$g_{k-1}$ are $n$-place primitive recursive functions, then    the composition of $f$ with $g_0$, \dots,~$g_{k-1}$ is primitive    recursive.  \item If $f$ is a $k$-place primitive recursive function and $g$ is    a $k+2$-place primitive recursive function, then the function    defined by primitive recursion from $f$ and $g$ is primitive    recursive.\end{enumerate}\end{defn}\begin{explain}Put more concisely, the set of primitive recursive functions is thesmallest set containing $\Zero$, $\Succ$, and the projectionfunctions~$\Proj{n}{j}$, and which is closed under composition andprimitive recursion.Another way of describing the set of primitive recursive functions isby defining it in terms of ``stages.'' Let $S_0$ denote the set ofstarting functions: $\Zero$, $\Succ$, and the projections. These arethe primitive recursive functions of stage~$0$. Once a stage $S_i$ hasbeen defined, let $S_{i+1}$ be the set of all functions you get byapplying a single instance of composition or primitive recursion tofunctions already in~$S_i$. Then\[S = \bigcup_{i \in \Nat} S_i\]is the set of all primitive recursive functions\end{explain}Let us verify that $\Add$ is a primitive recursive function.\begin{prop}  The addition function $\Add(x,y) = x+y$ is primitive recursive.\end{prop}\begin{proof}We already have a primitive recursive definition of $\Add$ in terms oftwo functions $f$ and~$g$ which matches the format of\olref{defn:primitive-recursion}:\begin{align*}  \Add(x_0, 0) & = f(x_0) = x_0\\  \Add(x_0, y+1) & = g(x_0, y, \Add(x_0, y)) =  \Succ(\Add(x_0, y))\end{align*}So $\Add$ is primitive recursive provided $f$ and $g$ are aswell. $f(x_0) = x_0 = \Proj{1}{0}(x_0)$, and the projection functionscount as primitive recursive, so $f$ is primitive recursive. Thefunction $g$ is the three-place function $g(x_0, y, z)$ defined by\[g(x_0, y, z) = \Succ(z).\]This does not yet tell us that $g$ is primitive recursive, since $g$and $\Succ$ are not quite the same function: $\Succ$ is one-place, and$g$ has to be three-place. But we can define $g$ ``officially'' bycomposition as\[g(x_0, y, z) = \Succ(\Proj{3}{2}(x_0, y, z))\]Since $\Succ$ and $\Proj{3}{2}$ count as primitive recursivefunctions, $g$ does as well, since it can be defined by compositionfrom primitive recursive functions.\end{proof}\begin{prop}  \ollabel{prop:mult-pr}  The multiplication function $\Mult(x,y) = x \cdot y$ is primitive recursive.\end{prop}\begin{proof}  Exercise.\end{proof}\begin{prob}  Prove \olref[cmp][rec][prf]{prop:mult-pr} by showing that the  primitive recursive definition of $\Mult$ can be put into the  form required by \olref[cmp][rec][prf]{defn:primitive-recursion} and  showing that the corresponding functions $f$ and~$g$ are primitive  recursive.\end{prob}\begin{ex}Here's our very first example of a primitive recursive definition:\begin{align*}h(0) & =  1 \\h(y+1) & =  2 \cdot h(y).\end{align*}This function cannot fit into the form required by\olref{defn:primitive-recursion}, since $k=0$. The definition alsoinvolves the constants $1$ and $2$. To get around the first problem,let's introduce a dummy argument and define the function~$h'$:\begin{align*}h'(x_0, 0) & =  f(x_0) = 1 \\h'(x_0, y+1) & =  g(x_0, y, h'(x_0, y)) = 2 \cdot h'(x_0, y).\end{align*}The function $f(x_0) = 1$ can be defined from $\Succ$ and $\Zero$ bycomposition: $f(x_0) = \Succ(\Zero(x_0))$. The function $g$ can bedefined by composition from $g'(z) = 2 \cdot z$ and projections:\begin{align*}g(x_0, y, z) & = g'(\Proj{3}{2}(x_0, y, z))\intertext{and $g'$ in turn can be defined by composition as}g'(z) & = \Mult(g''(z), \Proj{1}{0}(z))\intertext{and}g''(z) & = \Succ(f(z)),\end{align*}where $f$ is as above: $f(z) = \Succ(\Zero(z))$. Now that wehave~$h'$, we can use composition again to let $h(y) =h'(\Proj{1}{0}(y),\Proj{1}{0}(y))$. This shows that $h$ can be definedfrom the basic functions using a sequence of compositions andprimitive recursions, so $h$~is primitive recursive.\end{ex}\end{document}

content/computability/recursive-functions/notation-pr-functions.tex

% Part: computability% Chapter: recursive-functions% Section: notations-pr-functions\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{not}\olsection{Primitive Recursion Notations}One advantage to having the precise inductive description of the primitiverecursive functions is that we can be systematic in describing them.For example, we can assign a ``notation'' to each such function, asfollows. Use symbols $\Zero$, $\Succ$, and $\Proj{n}{i}$ for zero,successor, and the projections. Now suppose $h$ is defined bycomposition from a $k$-place function~$f$ and $n$-place functions $g_0$,\dots,~$g_{k-1}$, and we have assigned notations $F$, $G_0$,\dots,~$G_{k-1}$ to the latter functions. Then, using a new symbol$\fn{Comp}_{k,n}$, we can denote the function $h$ by$\fn{Comp}_{k,n}[F,G_0,\dots,G_{k-1}]$. For functions defined by primitive recursion, we can use analogousnotations. Suppose the $(k+1)$-ary function~$h$ is defined byprimitive recursion from the $k$-ary function~$f$ and the $(k+2)$-aryfunction~$g$, and the notations assigned to $f$ and~$g$ are $F$and~$G$, respectively. Then the notation assigned to~$h$ is$\fn{Rec}_k[F,G]$. Recall that the addition function is defined by primitive recursion as\begin{align*}  \Add(x_0, 0) & = \Proj{1}{0}(x_0) = x_0\\  \Add(x_0, y+1) & = \Succ(\Proj{3}{2}(x_0, y, \Add(x_0, y))) = \Add(x_0, y) +1\end{align*}Here the role of~$f$ is played by $\Proj{1}{0}$, and the role of~$g$is played by $\Succ(\Proj{3}{2}(x_0, y, z))$, which is assigned thenotation $\fn{Comp}_{1,3}[\Succ,\Proj{3}{2}]$ as it is the result ofdefining a function by composition from the $1$-ary function~$\Succ$and the $3$-ary function~$\Proj{3}{2}$. With this setup, we can denotethe addition function by\[\fn{Rec}_1[\Proj{1}{0},\fn{Comp}_{1,3}[\Succ,\Proj{3}{2}]].\]Having these notations sometimes proves useful, e.g., when enumeratingprimitive recursive functions.\begin{prob}  Give the complete primitive recursive notation for~$\Mult$.\end{prob}\end{document}

content/computability/recursive-functions/pr-functions-computable.tex

% Part: computability% Chapter: recursive-functions% Section: pr-functions-computable\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{cmp}\olsection{Primitive Recursive Functions are Computable}Suppose a function $h$ is defined by primitive recursion\begin{eqnarray*}h(\vec x, 0)     & = & f(\vec x) \\h(\vec x, y + 1) & = & g(\vec x, y, h(\vec x, y))\end{eqnarray*}and suppose the functions $f$ and $g$ are computable.  (We use $\vec x$ to abbreviate $x_0$, \dots, $x_{k-1}$.) Then $h(\vecx, 0)$ can obviously be computed, since it is just $f(\vec x)$ which weassume is computable.  $h(\vec x, 1)$ can then also be computed, since$1 = 0 + 1$ and so $h(\vec x, 1)$ is just\begin{align*} h(\vec x, 1) & = g(\vec x, 0, h(\vec x, 0)) =  g(\vec x, 0, f(\vec x)).\intertext{We can go on in this way and  compute}h(\vec x, 2) & = g(\vec x, 1, h(\vec x, 1)) = g(\vec x, 1, g(\vec x, 0, f(\vec x)))\\h(\vec x, 3) & = g(\vec x, 2, h(\vec x, 2)) = g(\vec x, 2, g(\vec x, 1, g(\vec x, 0, f(\vec x))))\\h(\vec x, 4) & = g(\vec x, 3, h(\vec x, 3)) = g(\vec x, 3, g(\vec x, 2, g(\vec x, 1, g(\vec x, 0, f(\vec x)))))\\& \vdots\end{align*}Thus, to compute $h(\vec x, y)$ in general, successively compute$h(\vec x, 0)$, $h(\vec x, 1)$, \dots, until we reach $h(\vec x, y)$.Thus, a primitive recursive definition yields a new computablefunction if the functions $f$ and $g$ are computable.  Composition offunctions also results in a computable function if the functions $f$and $g_i$ are computable.Since the basic functions $\Zero$, $\Succ$, and $\Proj{n}{i}$ arecomputable, and composition and primitive recursion yield computablefunctions from computable functions, this means that every primitiverecursive function is computable.\end{document}

content/computability/recursive-functions/examples.tex

% Part: computability% Chapter: recursive-functions% Section: examples\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{exa}\olsection{Examples of Primitive Recursive Functions}We already have some examples of primitive recursive functions: theaddition and multiplication functions~$\Add$ and $\Mult$.  Theidentity function $\fn{id}(x) = x$ is primitive recursive, since it isjust~$\Proj{1}{0}$. The constant functions $\fn{const}_n(x) = n$ areprimitive recursive since they can be defined from $\Zero$ and $\Succ$by successive composition. This is useful when we want to useconstants in primitive recursive definitions, e.g., if we want todefine the function $f(x) = 2 \cdot x$ can obtain it by compositionfrom $\fn{const}_n(x)$ and multiplication as $f(x) =\Mult(\fn{const}_2(x), \Proj{1}{0}(x))$. We'll make use of this trickfrom now on.\begin{prop}  The exponentiation function $\fn{exp}(x, y) = x^y$ is primitive recursive.\end{prop}\begin{proof}  We can define $\fn{exp}$ primitive recursively as  \begin{align*}    \fn{exp}(x, 0) & = 1\\    \fn{exp}(x, y+1) & = \Mult(x, \fn{exp}(x,y)).    \intertext{Strictly speaking, this is not a recursive definition      from primitive recursive functions. Officially, though, we      have:}    \fn{exp}(x, 0) & = f(x)\\    \fn{exp}(x, y+1) & = g(x, y, \fn{exp}(x,y)).    \intertext{where}    f(x) & = \Succ(\Zero(x)) = 1\\    g(x, y, z) & = \Mult(\Proj{3}{0}(x, y, z), \Proj{3}{2}(x, y, z)) = x \cdot z  \end{align*}  and so $f$ and $g$ are defined from primitive recursive functions by  composition.\end{proof}\begin{prop}  The predecessor function $\fn{pred}(y)$ defined by  \[  \fn{pred}(y) = \begin{cases}    0 & \text{if $y=0$}\\    y-1 & \text{otherwise}  \end{cases}  \]  is primitive recursive.\end{prop}\begin{proof} Note that  \begin{align*}   \fn{pred}(0) & = 0 \text{ and}\\   \fn{pred}(y+1) & = y. \end{align*} This is almost a primitive recursive definition.  It does not, strictly speaking, fit into the pattern of definition by primitive recursion, since that pattern requires at least one extra argument~$x$. It is also odd in that it does not actually use $\fn{pred}(y)$ in the definition of $\fn{pred}(y+1)$. But we can first define $\fn{pred}'(x, y)$ by \begin{align*}   \fn{pred}'(x, 0) & = \Zero(x) = 0,\\   \fn{pred}'(x, y+1) & = \Proj{3}{1}(x, y, \fn{pred'}(x, y)) = y. \end{align*}and then define $\fn{pred}$ from it by composition, e.g., as$\fn{pred}(x) = \fn{pred}'(\Zero(x), \Proj{1}{0}(x))$.\end{proof}\begin{prop}  The factorial function $\fn{fac}(x) = \fact{x} = 1 \cdot 2 \cdot 3  \cdot \dots \cdot x$ is primitive recursive.\end{prop}\begin{proof}  The obvious primitive recursive definition is  \begin{align*}    \fn{fac}(0) &= 1\\    \fn{fac}(y+1) & = \fn{fac}(y) \cdot (y+1).    \intertext{Officially, we have to first define a two-place function $h$}    h(x, 0) & = \fn{const}_1(x)\\    h(x, y+1) & = g(x, y, h(x, y))    \intertext{where $g(x, y, z) = \Mult(\Proj{3}{2}(x, y, z),      \Succ(\Proj{3}{1}(x, y, z)))$ and then let}    \fn{fac}(y) & = h(\Proj{1}{0}(y), \Proj{1}{0}(y)) = h(y,y).  \end{align*}  From now on we'll be a bit more laissez-faire and not give the official  definitions by composition and primitive recursion.\end{proof}\begin{prop}  Truncated subtraction, $x \tsub y$, defined by  \[  x \tsub y = \begin{cases}    0 & \text{if $x < y$}\\    x-y & \text{otherwise}  \end{cases}  \]  is primitive recursive.\end{prop}\begin{proof}  We have:  \begin{align*}    x \tsub 0 & = x\\    x \tsub (y+1) & = \fn{pred}(x \tsub y)   \end{align*}\end{proof}\begin{prop} The distance between $x$ and $y$, $\left|x-y\right|$, is primitive recursive.\end{prop}\begin{proof}  We have $\left| x-y \right| = (x \tsub y) + (y \tsub x)$, so  the distance can be defined by composition from $+$ and $\tsub$,  which are primitive recursive.\end{proof}\begin{prop}  The maximum of $x$ and $y$, $\fn{max}(x,y)$, is primitive recursive.\end{prop}\begin{proof}  We can define $\fn{max}(x,y)$ by composition from $+$ and $\tsub$ by  \[  \fn{max}(x,y) \defis x + (y \tsub x).  \]  If $x$ is the maximum, i.e., $x \ge y$, then $y \tsub x = 0$, so $x  + (y \tsub x) = x + 0 = x$. If $y$ is the maximum, then $y \tsub x =  y - x$, and so $x + (y \tsub x) = x + (y - x) = y$.\end{proof}\begin{prop}  \ollabel{prop:min-pr}  The minimum of $x$ and $y$, $\fn{min}(x,y)$, is primitive recursive.\end{prop}\begin{proof}  Exercise.\end{proof}\begin{prob}  Prove \olref[cmp][rec][exa]{prop:min-pr}.\end{prob}\begin{prob}Show that \[f(x, y) =2^{(2^{\iddots^{2^{x}}})}\raisebox{1ex}{\bigg\rbrace}\raisebox{1ex}{\text {$y$ $2$'s}}\] is primitive recursive.\end{prob}\begin{prob}Show that integer division $d(x, y) = \lfloor x/y \rfloor$ (i.e.,division, where you disregard everything after the decimal point) isprimitive recursive. When $y = 0$, we stipulate $d(x, y) = 0$. Give anexplicit definition of~$d$ using primitive recursion andcomposition.\end{prob}\begin{prop}The set of primitive recursive functions is closed under thefollowing two operations:\begin{enumerate}\item Finite sums: if $f(\vec x, z)$ is primitive recursive, then sois the function\[g(\vec x, y) \defis \sum_{z = 0}^y f(\vec x, z).\]\item Finite products: if $f(\vec x, z)$ is primitive recursive, thenso is the function\[h(\vec x, y) \defis \prod_{z = 0}^y f(\vec x, z).\]\end{enumerate}\end{prop}\begin{proof}For example, finite sums are defined recursively by the equations\begin{align*}  g(\vec x, 0) & = f(\vec x, 0)\\  g(\vec x, y+1) & = g(\vec x, y) + f(\vec x, y+1).\end{align*}\end{proof}\end{document}

content/computability/recursive-functions/pr-relations.tex

% Part: computability% Chapter: recursive-functions% Section: pr-relations\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{prr}\olsection{Primitive Recursive Relations}\begin{defn}A relation $R(\vec x)$ is said to be primitive recursive if its characteristicfunction,\[\Char{R}(\vec x) = \left\{  \begin{array}{ll}  1 & \mbox{if $R(\vec x)$} \\  0 & \mbox{otherwise}  \end{array}\right.\]is primitive recursive.\end{defn}In other words, when one speaks of a primitive recursive relation$R(\vec x)$, one is referring to a relation of the form $\Char{R}(\vecx) = 1$, where $\Char{R}$ is a primitive recursive function which, onany input, returns either 1 or 0. For example, the relation$\fn{IsZero}(x)$, which holds if and only if $x = 0$, corresponds to thefunction $\Char{\fn{IsZero}}$, defined using primitive recursion by\begin{align*}\Char{\fn{IsZero}}(0) & = 1,\\\Char{\fn{IsZero}}(x+1) & = 0.\end{align*}It should be clear that one can compose relations with other primitiverecursive functions. So the following are also primitive recursive:\begin{enumerate}\item The equality relation, $x = y$, defined by $\fn{IsZero}(\left|x -  y\right|)$\item The less-than relation, $x \leq y$, defined by $\fn{IsZero}(x  \tsub y)$\end{enumerate}\begin{prop}  The set of primitive recursive relations is closed under Boolean  operations, that is,   if $P(\vec x)$ and $Q(\vec x)$ are primitive recursive, so are  \begin{enumerate}  \item $\lnot P(\vec x)$  \item $P(\vec x) \land Q(\vec x)$  \item $P(\vec x) \lor Q(\vec x)$  \item $P(\vec x) \lif Q(\vec x)$  \end{enumerate}\end{prop}\begin{proof}  Suppose $P(\vec x)$ and $Q(\vec x)$ are primitive recursive, i.e.,  their characteristic functions $\Char{P}$ and $\Char{Q}$ are.  We  have to show that the characteristic functions of $\lnot P(\vec x)$,  etc., are also primitive recursive.  \[  \Char{\lnot P}(\vec x) = \begin{cases}    0 & \text{if $\Char{P}(\vec x) = 1$}\\    1 & \text{otherwise}  \end{cases}  \]  We can define $\Char{\lnot P}(\vec x)$ as $1 \tsub \Char{P}(\vec x)$.  \[  \Char{P \land Q}(\vec x) = \begin{cases}    1 & \text{if $\Char{P}(\vec x) = \Char{Q}(\vec x) = 1$}\\    0 & \text{otherwise}  \end{cases}  \]  We can define $\Char{P \land Q}(\vec x)$ as $\Char{P}(\vec x) \cdot  \Char{Q}(\vec x)$ or as $\fn{min}(\Char{P}(\vec x), \Char{Q}(\vec  x))$. Similarly,   \begin{align*}    \Char{P \lor Q}(\vec x) & = \fn{max}(\Char{P}(\vec x), \Char{Q}(\vec x)) \text{ and}\\    \Char{P \lif Q}(\vec x) & = \fn{max}(1 \tsub  \Char{P}(\vec x), \Char{Q}(\vec x)).  \end{align*}\end{proof}\begin{prop}  The set of primitive recursive relations is closed under bounded  quantification, i.e., if $R(\vec x, z)$ is a primitive recursive  relation, then so are the relations  \begin{align*}    & \bforall{z < y}{R(\vec x, z)} \text{ and}\\    & \bexists{z < y}{R(\vec x, z)}.  \end{align*}  $\bforall{z < y}{R(\vec x, z)}$ holds of $\vec x$ and $y$ if and  only if $R(\vec x, z)$ holds for every~$z$ less than~$y$, and  similarly for $\bexists{z < y}{R(\vec x, z)}$.\end{prop}\begin{proof}  By convention, we take $\bforall{z < 0}{R(\vec x, z)}$ to be true  (for the trivial reason that there are no $z$ less than~$0$) and  $\bexists{z < 0}{R(\vec x, z)}$ to be false. A bounded  universal quantifier functions just like a finite product or  iterated minimum, i.e., if $P(\vec x, y) \defiff \bforall{z <  y}{R(\vec x, z)}$ then $\Char{P}(\vec x, y)$ can be defined by  \begin{align*}    \Char{P}(\vec x, 0) & = 1\\    \Char{P}(\vec x, y+1) & =    \fn{min}(\Char{P}(\vec x, y), \Char{R}(\vec x, y)).  \end{align*}  Bounded existential quantification can similarly be defined using  $\fn{max}$. Alternatively, it can be defined from bounded universal  quantification, using the equivalence $\bexists{z < y}{R(\vec x, z)}  \liff \lnot \bforall{z < y}{\lnot R(\vec x, z)}$. Note that, for  example, a bounded quantifier of the form $\bexists{x \leq y}{\dots  x\dots}$ is equivalent to $\bexists{x < y+1}{\dots x \dots}$.\end{proof}\begin{prob}  Show that the three place relation $x \equiv y \mod n$ (congruence  modulo~$n$) is primitive recursive.\end{prob}Another useful primitive recursive function is the conditionalfunction, $\fn{cond}(x,y,z)$, defined by\begin{align*}  \fn{cond}(x,y,z) & = \begin{cases}  y & \text{if $x = 0$} \\  z & \text{otherwise}.\end{cases}\intertext{This is defined recursively by}\fn{cond}(0,y,z) & = y,\\\fn{cond}(x+1,y,z) & = z.\end{align*}One can use this to justify definitions of primitive recursive functionsby cases from primitive recursive relations:\begin{prop}If $g_0(\vec x)$, \dots,~$g_m(\vec x)$ are primitive recursive functions, and $R_0(\vecx)$, \dots, $R_{m-1}(\vec x)$ are primitive recursive relations, thenthe function $f$ defined by\[f(\vec x) = \begin{cases}    g_0(\vec x) & \text{if $R_0(\vec{x})$} \\    g_1(\vec x) & \text{if $R_1(\vec{x})$ and not $R_0(\vec{x})$} \\    \vdots & \\    g_{m-1}(\vec x) & \text{if $R_{m-1}(\vec{x})$ and none of the      previous hold}    \\    g_m(\vec x) & \mbox{otherwise}\end{cases}\]is also primitive recursive.\end{prop}\begin{proof}  When $m = 1$, this is just the function defined by  \[  f(\vec x) = \fn{cond}(\Char{\lnot R_0}(\vec x),g_0(\vec x),g_1(\vec  x)).  \]  For $m$ greater than $1$, one can just compose definitions of this  form.\end{proof}\end{document}

content/computability/recursive-functions/bounded-minimization.tex

% Part: computability% Chapter: recursive-functions% Section: bounded-minimization\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{bmi}\olsection{Bounded Minimization}\begin{explain}It is often useful to define a function as the least number satisfyingsome property or relation~$P$. If $P$ is decidable, we can computethis function simply by trying out all the possible numbers, $0$, $1$,$2$, \dots, until we find the least one satisfying~$P$.  This kind ofunbounded search takes us out of the realm of primitive recursivefunctions. However, if we're only interested in the least number\emph{less than some independently given bound}, we stay primitiverecursive. In other words, and a bit more generally, suppose we have aprimitive recursive relation~$R(x,z)$. Consider the function that maps$x$ and~$y$ to the least $z < y$ such that $R(x, z)$. It, too, can becomputed, by testing whether $R(x, 0)$, $R(x, 1)$, \dots, $R(x, y-1)$.But why is it primitive recursive?\end{explain}\begin{prop}If $R(\vec x, z)$ is primitive recursive, so is the function$m_R(\vec{x}, y)$ which returns the least~$z$ less than~$y$ such that$R(\vec x, z)$ holds, if there is one, and $y$ otherwise.  We willwrite the function~$m_R$ as\[\bmin{z < y}{R(\vec{x}, z)},\]\end{prop}\begin{proof}Note than there can be no~$z < 0$ such that $R(\vec{x}, z)$ sincethere is no $z < 0$ at all.  So $m_R(\vec x, 0) = 0$.In case the bound is of the form $y + 1$ we have three cases:\begin{enumerate}\item There is a $z < y$ such that $R(\vec{x}, z)$, in which case$m_R(\vec{x}, y+1) = m_R(\vec{x}, y)$.\item There is no such~$z<y$ but $R(\vec{x}, y)$ holds, then$m_R(\vec{x}, y+1) = y$.\item There is no $z < y+1$ such that $R(\vec{x}, z)$, then$m_R(\vec{z}, y+1) = y+1$.\end{enumerate}So we can define $m_R(\vec x, 0)$ by primitive recursion as follows:\begin{align*}m_R(\vec{x}, 0) & = 0\\m_R(\vec{x}, y+1) & =\begin{cases}m_R(\vec{x}, y) & \text{if $m_R(\vec x, y) \neq y$}\\y & \text{if $m_R(\vec x, y) = y$ and $R(\vec{x}, y)$}\\y+1 & \text{otherwise.}\end{cases}\end{align*}Note that there is a $z<y$ such that $R(\vec x, z)$ iff $m_R(\vec x,y) \neq y$.\end{proof}\begin{prob}Suppose $R(\vec x, z)$ is primitive recursive. Define the function$m'_R(\vec{x}, y)$ which returns the least~$z$ less than~$y$ such that$R(\vec{x}, z)$ holds, if there is one, and $0$ otherwise, byprimitive recursion from~$\Char{R}$.\end{prob}\end{document}

content/computability/recursive-functions/primes.tex

% Part: computability% Chapter: recursive-functions% Section: primes\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{pri}\olsection{Primes}Bounded quantification and bounded minimization provide us with a gooddeal of machinery to show that natural functions and relations areprimitive recursive. For example, consider the relation ``$x$divides $y$'', written $x \mid y$.  The relation $x \mid y$ holds ifdivision of $y$ by~$x$ is possible without remainder, i.e., if $y$ isan integer multiple of~$x$.  (If it doesn't hold, i.e., the remainderwhen dividing $x$ by $y$ is $> 0$, we write $x \nmid y$.) In otherwords, $x \mid y$ iff for some~$z$, $x \cdot z = y$.  Obviously, anysuch $z$, if it exists, must be $\leq y$. So, we have that $x \mid y$iff for some $z \le y$, $x \cdot z = y$.  We can define the relation$x \mid y$ by bounded existential quantification from $=$ andmultiplication by\[x \mid y \defiff \bexists{z \leq y}{(x \cdot z) = y}.\]We've thus shown that $x \mid y$ is primitive recursive.A natural number~$x$ is \emph{prime} if it is neither $0$ nor $1$ andis only divisible by $1$ and itself. In other words, prime numbers aresuch that, whenever $y \mid x$, either $y = 1$ or~$y=x$.  To test if$x$~is prime, we only have to check if $y \mid x$ for all $y \le x$,since if $y > x$, then automatically~$y \nmid x$.  So, the relation$\fn{Prime}(x)$, which holds iff $x$ is prime, can be defined by\[\fn{Prime}(x) \defiff x \geq 2 \land \bforall{y \leq x}{(y \mid x \lif y  = 1 \lor y = x)}\]and is thus primitive recursive.The primes are $2$, $3$, $5$, $7$, $11$, etc. Consider the function$p(x)$ which returns the $x$th prime in that sequence, i.e., $p(0) =2$, $p(1) = 3$, $p(2) = 5$, etc. (For convenience we will often write$p(x)$ as $p_x$ ($p_0=2$, $p_1=3$, etc.)If we had a function$\fn{nextPrime(x)}$, which returns the first prime number largerthan~$x$, $p$~can be easily defined using primitive recursion:\begin{align*}  p(0) & = 2\\  p(x+1) & = \fn{nextPrime}(p(x))\end{align*}Since $\fn{nextPrime}(x)$ is the least $y$ such that $y > x$ and$y$~is prime, it can be easily computed by unbounded search. But itcan also be defined by bounded minimization, thanks to a result due toEuclid: there is always a prime number between $x$ and $\fact{x}+1$.\[  \fn{nextPrime(x)} =  \bmin{y \leq \fact{x}+1}{(y > x \land \fn{Prime}(y))}.\]This shows, that $\fn{nextPrime}(x)$ and hence $p(x)$ are (not justcomputable but) primitive recursive.(If you're curious, here's a quick proof of Euclid's theorem. Suppose$p_n$ is the largest prime $\le x$ and consider the product $p =p_0\cdot p_1 \cdot \dots \cdot p_n$ of all primes~$\le x$. Either$p+1$ is prime or there is a prime between $x$ and~$p+1$.  Why?Suppose $p+1$ is not prime. Then some prime number $q \mid p+1$ where$q < p+1$. None of the primes $\le x$ divide $p+1$. (By definitionof~$p$, each of the primes $p_i \le x$ divides~$p$, i.e., withremainder~$0$. So, each of the primes $p_i \le x$ divides $p+1$ withremainder~$1$, and so $p_i \nmid p+1$.)  Hence, $q$ is a prime $>x$ and $< p+1$.  And $p \le \fact{x}$, so there is a prime $> x$ and $\le\fact{x}+1$.)\begin{prob}Define integer division $d(x, y)$ using bounded minimization.\end{prob}\end{document}

content/computability/recursive-functions/sequences.tex

% Part: computability% Chapter: recursive-functions% Section: sequences\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{seq}\olsection{Sequences}The set of primitive recursive functions is remarkably robust. But wewill be able to do even more once we have developed a adequate meansof handling \emph{sequences}. We will identify finite sequences ofnatural numbers with natural numbers in the following way: thesequence $\langle a_0, a_1, a_2, \dots, a_k \rangle$ corresponds tothe number\[p_0^{a_0+1} \cdot p_1^{a_1+1} \cdot p_2^{a_2+1} \cdot \dots \cdotp_k^{a_k+1}.\]We add one to the exponents to guarantee that, for example, thesequences $\langle 2, 7, 3\rangle$ and $\langle 2, 7, 3, 0, 0 \rangle$have distinct numeric codes. We can take both $0$ and~$1$ to code theempty sequence; for concreteness, let $\emptyseq$ denote~$0$.The reason that this coding of sequences works is the so-calledFundamental Theorem of Arithmetic: every natural number $n \ge 2$ canbe written in one and only one way in the form\[n = p_0^{a_0} \cdot p_1^{a_1} \cdot \dots \cdot p_k^{a_k}\]with $a_k \ge 1$. This guarantees that the mapping $\tuple{}(a_0,\dots, a_k) = \tuple{a_0, \dots, a_k}$ is injective: differentsequences are mapped to different numbers; to each number only at mostone sequence corresponds.We'll now show that the operations of determining the length of asequence, determining its $i$th element, appending an element to asequence, and concatenating two sequences, are all primitiverecursive.\begin{prop}  The function $\len{s}$, which returns the length of the sequence  $s$, is primitive recursive.\end{prop}\begin{proof}  Let $R(i, s)$ be the relation defined by  \[  R(i, s) \text{ iff }  p_i \mid s \land p_{i+1} \nmid s.  \]  $R$ is clearly primitive recursive. Whenever $s$ is the code of a  non-empty sequence, i.e.,  \[  s = p_0^{a_0+1} \cdot \dots \cdot p_{k}^{a_{k}+1},  \]  $R(i,s)$ holds if $p_i$ is the largest prime such that  $p_i \mid s$, i.e., $i = k$. The length of $s$ thus is $i+1$ iff  $p_i$ is the largest prime that divides~$s$, so we can let  \[  \len{s} =  \begin{cases}    0 & \text{if $s = 0$ or $s = 1$} \\    1 + \bmin{i < s}{R(i, s)} & \text{otherwise}  \end{cases}  \]  We can use bounded minimization here, since there is only one $i$ that  satisfies $R(i,s)$ when $s$~is a code of a sequence, and if $i$  exists it is less than~$s$ itself.\end{proof}\begin{prop}  The function $\fn{append}(s,a)$, which returns the result of appending $a$ to  the sequence $s$, is primitive recursive.\end{prop}\begin{proof}  $\fn{append}$ can be defined by:  \[  \fn{append}(s,a) =  \begin{cases}    2^{a+1} & \text{if $s = 0$ or $s = 1$} \\    s \cdot p_{\len{s}}^{a+1} & \text{otherwise.}  \end{cases}  \]\end{proof}\begin{prop}  The function $\fn{element}(s,i)$, which returns the $i$th element of $s$  (where the initial element is called the $0$th), or $0$ if $i$ is  greater than or equal to the length of $s$, is primitive recursive.\end{prop}\begin{proof}Note that $a$ is the $i$th element of~$s$ iff $p_i^{a+1}$ isthe largest power of~$p_i$ that divides~$s$, i.e., $p_i^{a+1} \mid s$but $p_i^{a+2} \nmid s$. So:  \[  \fn{element}(s,i) =  \begin{cases}    0 & \mbox{if $i \geq \len{s}$} \\    \bmin{a < s}{(p_i^{a+2} \nmid s)} & \text{otherwise.}  \end{cases}  \]\end{proof}Instead of using the official names for the functions defined above,we introduce a more compact notation. We will use $(s)_i$ instead of$\fn{element}(s,i)$, and $\tuple{s_0, \dots, s_k}$ to abbreviate\[\fn{append}(\fn{append}(\dots \fn{append}(\emptyseq,s_0)\dots),s_k).\]Note that if $s$ has length~$k$, the elements of $s$ are$(s)_0$, \dots,~$(s)_{k-1}$.\begin{prop}The function $\fn{concat}(s,t)$, which concatenates twosequences, is primitive recursive.\end{prop}\begin{proof}  We want a function $\fn{concat}$ with the property that  \[    \fn{concat}(\tuple{a_0, \dots, a_k}, \tuple{b_0, \dots, b_l}) =    \tuple{a_0, \dots, a_k, b_0, \dots, b_l}.  \]  We'll use a ``helper'' function  $\fn{hconcat}(s,t,n)$ which concatenates the first $n$ symbols of $t$  to~$s$. This function can be defined by primitive recursion as  follows:  \begin{align*}    \fn{hconcat}(s,t,0) & = s\\    \fn{hconcat}(s,t,n+1) & = \fn{append}(\fn{hconcat}(s,t,n),(t)_n)    \intertext{Then we can define $\fn{concat}$ by}    \fn{concat}(s,t) & = \fn{hconcat}(s,t,\len{t}).  \end{align*}\end{proof}We will write $s \concat t$ instead of $\fn{concat}(s,t)$.It will be useful for us to be able to bound the numeric code of asequence in terms of its length and its largest element. Suppose $s$is a sequence of length~$k$, each element of which is less than or equalto some number~$x$. Then $s$ has at most $k$ prime factors, each atmost~$p_{k-1}$, and each raised to at most $x+1$ in the primefactorization of~$s$. In other words, if we define\[\fn{sequenceBound}(x,k) = p_{k-1}^{k \cdot (x+1)},\]then the numeric code of the sequence~$s$ described above is atmost~$\fn{sequenceBound}(x,k)$.Having such a bound on sequences gives us a way of defining newfunctions using bounded search. For example, we can define$\fn{concat}$ using bounded search. All we need to do is write down aprimitive recursive \emph{specification} of the object (number of theconcatenated sequence) we are looking for, and a bound on how far tolook. The following works:\begin{align*}  \fn{concat}(s,t) = {} & \bmin{v < \fn{sequenceBound}(s+t,\len{s} +    \len{t})}{} \\  & \quad(\len{v} = \len{s} + \len{t} \land {}\\    & \qquad \bforall{i < \len{s}}{((v)_i = (s)_i) \land {} \\      & \qquad \bforall{j < \len{t}}{((v)_{\len{s}+j} = (t)_j)})}\end{align*}\begin{prob}Show that there is a primitive recursive function~$\fn{sconcat}(s)$with the property that\[\fn{sconcat}(\tuple{s_0, \dots, s_k}) = s_0 \concat \dots \concat s_k.\]\end{prob}\begin{prob}Show that there is a primitive recursive function~$\fn{tail}(s)$with the property that\begin{align*}  \fn{tail}(\emptyseq) & = 0 \text{ and}\\  \fn{tail}(\tuple{s_0, \dots, s_{k}}) & = \tuple{s_1, \dots, s_{k}}.\end{align*}\end{prob}\begin{prop}  \ollabel{prop:subseq}  The function $\fn{subseq}(s, i, n)$ which returns the subsequence  of $s$ of length~$n$ beginning at the $i$th element, is primitive  recursive.\end{prop}\begin{proof}  Exercise.\end{proof}\begin{prob}  Prove \olref[cmp][rec][seq]{prop:subseq}.\end{prob}  \end{document}

content/computability/recursive-functions/trees.tex

% Part: computability% Chapter: recursive-functions% Section: trees\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{tre}\olsection{Trees}Sometimes it is useful to represent trees as natural numbers, justlike we can represent sequences by numbers and properties of andoperations on them by primitive recursive relations and functions ontheir codes.  We'll use sequences and their codes to do this. A treecan be either a single node (possibly with a label) or else a node(possibly with a label) connected to a number of subtrees. The node iscalled the \emph{root} of the tree, and the subtrees it is connectedto its \emph{immediate subtrees}.We code trees recursively as a sequence $\tuple{k, d_1, \dots, d_k}$,where $k$ is the number of immediate subtrees and $d_1$, \dots,~$d_k$the codes of the immediate subtrees. If the nodes have labels, theycan be included after the immediate subtrees. So a tree consistingjust of a single node with label~$l$ would be coded by $\tuple{0,l}$,and a tree consisting of a root (labelled~$l_1$) connected to twosingle nodes (labelled $l_2$, $l_3$) would be coded by $\tuple{2,  \tuple{0, l_2}, \tuple{0, l_3}, l_1}$.\begin{prop}  \ollabel{prop:subtreeseq}  The function $\fn{SubtreeSeq}(t)$, which returns the code of a  sequence the elements of which are the codes of all subtrees of the  tree with code~$t$, is primitive recursive.\end{prop}\begin{proof}  First note that $\fn{ISubtrees}(t) = \fn{subseq}(t, 1, (t)_0)$ is  primitive recursive and returns the codes of the immediate subtrees  of a tree~$t$. Now we can define a helper function  $\fn{hSubtreeSeq}(t,n)$ which computes the sequence of all subtrees  which are $n$ nodes removed from the root. The sequence of subtrees  of~$t$ which is $0$ nodes removed from the root---in other words,  begins at the root of~$t$---is the sequence consisting just  of~$t$. To obtain a sequence of all level~$n+1$ subtrees of $t$, we  concatenate the level $n$ subtrees with a sequence consisting of all  immediate subtrees of the level $n$ subtrees. To get a list of all  these, note that if $f(x)$ is a primitive recursive function  returning codes of sequences, then $g_f(s, k) = f((s)_0) \concat  \dots \concat f((s)_k)$ is also primitive recursive:    \begin{align*}      g(s, 0) & = f((s)_0)\\      g(s, k+1) & = g(s, k) \concat f((s)_{k+1})    \end{align*}    For instance, if $s$ is a sequence of trees, then    $h(s) = g_{\fn{ISubtrees}}(s, \len{s})$ gives the sequence of the    immediate subtrees of the elements of~$s$. We can use it to define    $\fn{hSubtreeSeq}$ by    \begin{align*}      \fn{hSubtreeSeq}(t, 0) & = \tuple{t} \\      \fn{hSubtreeSeq}(t, n+1) & = \fn{hSubtreeSeq}(t, n) \concat      h(\fn{hSubtreeSeq}(t, n)).    \end{align*}    The maximum level of subtrees in a tree coded by~$t$, i.e., the    maximum distance between the root and a leaf node, is bounded by    the code~$t$. So a sequence of codes of all subtrees of the tree    coded by~$t$ is given by $\fn{hSubtreeSeq}(t, t)$.\end{proof}\begin{prob}  The definition of $\fn{hSubtreeSeq}$ in the proof of  \olref[cmp][rec][tre]{prop:subtreeseq} in general includes  repetitions. Give an alternative definition which guarantees that  the code of a subtree occurs only once in the resulting list.\end{prob}\end{document}

content/computability/recursive-functions/other-recursions.tex

% Part: computability% Chapter: recursive-functions% Section: other-recursions\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{ore}\olsection{Other Recursions}Using pairing and sequencing, we can justify more exotic (anduseful) forms of primitive recursion. For example, it is often usefulto define two functions simultaneously, such as in the followingdefinition:\begin{align*}h_0(\vec x, 0) & = f_0(\vec x) \\h_1(\vec x, 0) & = f_1(\vec x) \\h_0(\vec x, y+1) & = g_0(\vec x, y, h_0(\vec x, y), h_1(\vec x, y)) \\h_1(\vec x, y+1) & = g_1(\vec x, y, h_0(\vec x, y), h_1(\vec x, y))\end{align*}This is an instance of \emph{simultaneous recursion}. Another usefulway of defining functions is to give the value of $h(\vec x, y+1)$ interms of \emph{all} the values $h(\vec x, 0)$, \dots,~$h(\vec x, y)$, as inthe following definition:\begin{align*}h(\vec x, 0) & = f(\vec x) \\h(\vec x, y+1) & = g(\vec x, y, \tuple{h(\vec x, 0), \dots, h(\vec x, y)}).\end{align*}The following schema captures this idea more succinctly:\[h(\vec x, y) = g(\vec x, y, \tuple{h(\vec x, 0), \dots, h(\vec x, y-1)})\]with the understanding that the last argument to $g$ is just theempty sequence when $y$ is $0$. In either formulation, the idea isthat in computing the ``successor step,'' the function $h$ can makeuse of the entire sequence of values computed so far.This is known as a \emph{course-of-values} recursion. For a particularexample, it can be used to justify the following type of definition:\begin{align*}h(\vec x, y) & = \begin{cases}  g(\vec x, y, h(\vec x, k(\vec x, y))) & \text{if $k(\vec x, y) < y$} \\  f(\vec x) & \text{otherwise}\end{cases}\end{align*}In other words, the value of $h$ at $y$ can be computed in terms ofthe value of $h$ at \emph{any} previous value, given by~$k$.\begin{prob}  Define the remainder function $r(x,y)$ by course-of-values  recursion. (If $x$, $y$ are natural numbers and $y > 0$, $r(x,y)$ is  the number less than~$y$ such that $x = z\times y + r(x,y)$ for  some~$z$. For definiteness, let's say that if $y=0$, $r(x,0) = 0$.)\end{prob}You should think about how to obtain these functions using ordinaryprimitive recursion. One final version of primitive recursion is moreflexible in that one is allowed to change the \emph{parameters} (sidevalues) along the way:\begin{align*}h(\vec x, 0) & = f(\vec x) \\h(\vec x, y+1) & = g(\vec x, y, h(k(\vec x), y))\end{align*}This, too, can be simulated with ordinary primitive recursion. (Doingso is tricky. For a hint, try unwinding the computation by hand.)\end{document}

content/computability/recursive-functions/non-pr-functions.tex

% Part: computability% Chapter: recursive-functions% Section: non-pr-functions\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{npr}\olsection{Non-Primitive Recursive Functions}The primitive recursive functions do not exhaust the intuitivelycomputable functions. It should be intuitively clear that we can makea list of all the unary primitive recursive functions,$f_0$, $f_1$, $f_2$,~\dots such that we can effectively compute the value of$f_x$ on input $y$; in other words, the function $g(x,y)$, defined by\[g(x,y) = f_x(y)\]is computable. But then so is the function\begin{eqnarray*}h(x) & = & g(x,x) + 1 \\& = & f_x(x) +1.\end{eqnarray*}For each primitive recursive function $f_i$, the value of $h$ and$f_i$ differ at $i$. So $h$ is computable, but not primitiverecursive; and one can say the same about $g$. This is an``effective'' version of Cantor's diagonalization argument.One can provide more explicit examples of computable functions thatare not primitive recursive. For example, let the notation $g^n(x)$denote $g(g(\dots g(x)))$, with $n$ $g$'s in all; and define asequence $g_0,g_1,\dots$ of functions by\begin{eqnarray*}g_0(x) & = & x+1 \\g_{n + 1}(x) & = & g_n^x(x)\end{eqnarray*}You can confirm that each function $g_n$ is primitive recursive. Eachsuccessive function grows much faster than the one before; $g_1(x)$ isequal to $2x$, $g_2(x)$ is equal to $2^x \cdot x$, and $g_3(x)$ growsroughly like an exponential stack of $x$ $2$'s. The Ackermann--P\'eterfunction is essentially the function $G(x) = g_x(x)$, and one can showthat this grows faster than any primitive recursive function.Let us return to the issue of enumerating the primitive recursivefunctions. Remember that we have assigned symbolic notations to eachprimitive recursive function; so it suffices to enumeratenotations. We can assign a natural number $\#(F)$ to each notation $F$,recursively, as follows:\begin{eqnarray*}\#(0) & = & \langle 0 \rangle \\\#(S) & = & \langle 1 \rangle \\\#(\Proj{n}{i}) & = & \langle 2, n, i \rangle \\\#(\fn{Comp}_{k,l}[H,G_0,\dots,G_{k-1}]) & = & \langle3,k,l,\#(H),\#(G_0),\dots,\#(G_{k-1}) \rangle \\\#(\fn{Rec}_l[G,H]) & = & \langle 4, l, \#(G), \#(H) \rangle\end{eqnarray*}Here we are using the fact that every sequence of numbers can be viewedas a natural number, using the codes from the last section. The upshotis that every code is assigned a natural number. Of course, somesequences (and hence some numbers) do not correspond to notations; butwe can let $f_i$ be the unary primitive recursive function withnotation coded as $i$, if $i$ codes such a notation; and the constant$0$ function otherwise. The net result is that we have an explicit way ofenumerating the unary primitive recursive functions.(In fact, some functions, like the constant zero function, will appearmore than once on the list. This is not just an artifact of ourcoding, but also a result of the fact that the constant zero function hasmore than one notation. We will later see that one can not computablyavoid these repetitions; for example, there is no computable functionthat decides whether or not a given notation represents the constantzero function.)We can now take the function $g(x,y)$ to be given by $f_x(y)$, where$f_x$ refers to the enumeration we have just described. How do we knowthat $g(x,y)$ is computable? Intuitively, this is clear: to compute$g(x,y)$, first ``unpack'' $x$, and see if it is a notation for a unaryfunction. If it is, compute the value of that function on input~$y$.\begin{tagblock}{TMs}\begin{digress}You may already be convinced that (with some work!) one can write aprogram (say, in Java or C++) that does this; and now we can appeal tothe Church--Turing thesis, which says that anything that, intuitively,is computable can be computed by a Turing machine.Of course, a more direct way to show that $g(x,y)$ is computable is todescribe a Turing machine that computes it, explicitly. This would,in particular, avoid the Church--Turing thesis and appeals tointuition. Soon we will have built up enough machinery to showthat $g(x,y)$ is computable, appealing to a model of computation thatcan be \emph{simulated} on a Turing machine: namely, the recursivefunctions.\end{digress}\end{tagblock}\end{document}

content/computability/recursive-functions/partial-functions.tex

% Part: computability% Chapter: recursive-functions% Section: partial-functions\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{par}\olsection{Partial Recursive Functions}To motivate the definition of the recursive functions, note that ourproof that there are computable functions that are not primitiverecursive actually establishes much more. The argument wassimple: all we used was the fact that it is possible to enumeratefunctions $f_0,f_1,\dots$ such that, as a function of $x$ and $y$,$f_x(y)$ is computable. So the argument applies to \emph{any class of  functions that can be enumerated in such a way}. This puts us in abind: we would like to describe the computable functions explicitly;but any explicit description of a collection of computable functionscannot be exhaustive!The way out is to allow \emph{partial} functions to come into play. Wewill see that it \emph{is} possible to enumerate the partialcomputable functions.\iftag{TMs}{ In fact, we already pretty much know  that this is the case, since it is possible to enumerate Turing  machines in a systematic way.}{} We will come back to our diagonalargument later, and explore why it does not go through when partialfunctions are included.The question is now this: what do we need to add to the primitiverecursive functions to obtain all the partial recursive functions? Weneed to do two things:\begin{enumerate}\item Modify our definition of the primitive recursive functions to  allow for partial functions as well.\item \emph{Add} something to the definition, so that some new partial  functions are included.\end{enumerate}The first is easy. As before, we will start with zero, successor, andprojections, and close under composition and primitive recursion. Theonly difference is that we have to modify the definitions ofcomposition and primitive recursion to allow for the possibility thatsome of the terms in the definition are not defined. If $f$ and $g$are partial functions, we will write $f(x) \fdefined$ to mean that $f$is defined at $x$, i.e., $x$ is in 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 are both defined and equal. We will use thesenotations for more complicated terms as well. We will adopt theconvention that if $h$ and $g_0$, \dots,~$g_k$ all are partial functions,then\[h(g_0(\vec x),\dots,g_k(\vec x))\]is defined if and only if each $g_i$ is defined at $\vec x$, and $h$is defined at $g_0(\vec x)$, \dots,~$g_k(\vec x)$. With thisunderstanding, the definitions of composition and primitive recursionfor partial functions is just as above, except that we have to replace``$=$'' by ``$\simeq$''.What we will add to the definition of the primitive recursivefunctions to obtain partial functions is the \emph{unbounded search  operator}. If $f(x,\vec z)$ is any partial function on the naturalnumbers, define $\mu x \; f(x,\vec z)$ to be\begin{quote}  the least $x$ such that $f(0,\vec z), f(1,\vec z), \dots, f(x,\vec  z)$ are all defined, and $f(x,\vec z) = 0$, if such an $x$ exists\end{quote}with the understanding that $\mu x \; f(x,\vec z)$ is undefinedotherwise. This defines $\mu x \; f(x,\vec z)$ uniquely.\begin{explain}Note that our definition makes no reference to\iftag{TMs}{ Turing  machines, or}{} algorithms, or any specific computational model. Butlike composition and primitive recursion, there is an operational,computational intuition behind unbounded search. When itcomes to the computability of a partial function, argumentswhere the function is undefined correspond to inputs for which thecomputation does not halt. The procedure for computing $\mu x \;f(x,\vec z)$ will amount to this: compute $f(0,\vec z), f(1,\vec z),f(2,\vec z)$ until a value of 0 is returned. If any of theintermediate computations do not halt, however, neither does thecomputation of $\mu x \; f(x,\vec z)$.\end{explain}If $R(x,\vec z)$ is any relation, $\mu x \; R(x,\vec z)$ is defined tobe $\mu x \; (1 \tsub \Char{R}(x,\vec z))$. In other words, $\mu x \;R(x,\vec z)$ returns the least value of $x$ such that $R(x,\vec z)$holds. So, if $f(x,\vec z)$ is a total function, $\mu x \; f(x,\vecz)$ is the same as $\mu x \; (f(x,\vec z) = 0)$. But note that ouroriginal definition is more general, since it allows for thepossibility that $f(x,\vec z)$ is not everywhere defined (whereas, incontrast, the characteristic function of a relation is always total).\begin{defn}The set of \emph{partial recursive functions} is the smallest set ofpartial functions from the natural numbers to the natural numbers (ofvarious arities) containing zero, successor, and projections, andclosed under composition, primitive recursion, and unbounded search.\end{defn}Of course, some of the partial recursive functions will happen to betotal, i.e., defined for every argument.\begin{defn}\ollabel{defn:recursive-fn}The set of \emph{recursive functions} isthe set of partial recursive functions that are total.\end{defn}A recursive function is sometimes called ``total recursive'' toemphasize that it is defined everywhere.\end{document}

content/computability/recursive-functions/normal-form.tex

% Part: computability% Chapter: recursive-functions% Section: normal-form\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{nft}\olsection{The Normal Form Theorem}\begin{thm}[Kleene's Normal Form Theorem]\ollabel{thm:kleene-nf}There is a primitive recursive relation $T(e, x, s)$ and a primitiverecursive function $U(s)$, with the following property: if $f$ is anypartial recursive function, then for some~$e$,\[f(x) \simeq U(\umin{s}{T(e, x, s)})\]for every $x$.\end{thm}\begin{explain}The proof of the normal form theorem is involved, but the basic ideais simple.  Every partial recursive function has an \emph{index}~$e$,intuitively, a number coding its program or definition.  If $f(x)\fdefined$, the computation can be recorded systematically and codedby some number~$s$, and the fact that $s$ codes the computation of~$f$on input~$x$ can be checked primitive recursively using only $x$ andthe definition~$e$.  Consequently, the relation~$T$, ``the functionwith index~$e$ has a computation for input~$x$, and $s$ codes thiscomputation,'' is primitive recursive. Given the full record of thecomputation~$s$, the ``upshot'' of~$s$ is the value of~$f(x)$, and itcan be obtained from~$s$ primitive recursively as well.The normal form theorem shows that only a single unbounded search isrequired for the definition of any partial recursive function.Basically, we can search through all numbers until we find one thatcodes a computation of the function with index~$e$ for input~$x$. Wecan use the numbers~$e$ as ``names'' of partial recursive functions,and write $\cfind{e}$ for the function~$f$ defined by the equation inthe theorem.  Note that any partial recursive function can have morethan one index---in fact, every partial recursive function hasinfinitely many indices.\end{explain}\end{document}

content/computability/recursive-functions/halting-problem.tex

% Part: computability% Chapter: recursive-functions% Section: halting-problem\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{hlt}\olsection{The Halting Problem}The \emph{halting problem} in general is the problem of deciding,given the specification~$e$ (e.g., program) of a computable functionand a number~$n$, whether the computation of the function on input~$n$halts, i.e., produces a result.  Famously, Alan Turing proved thatthis problem itself cannot be solved by a computable function, i.e.,the function\[h(e, n) =\begin{cases}1 & \text{if computation $e$ halts on input $n$}\\0 & \text{otherwise,}\end{cases}\]is not computable.In the context of partial recursive functions, the role of thespecification of a program may be played by the index~$e$ given inKleene's normal form theorem.  If $f$ is a partial recursive function,any $e$~for which the equation in the normal form theorem holds, is anindex of~$f$. Given a number~$e$, the normal form theorem states that\[\cfind{e}(x) \simeq U(\mu s \; T(e, x, s))\]is partial recursive, and for every partial recursive $f\colon \Nat\to \Nat$, there is an $e \in \Nat$ such that $\cfind{e}(x) \simeqf(x)$ for all~$x \in \Nat$.  In fact, for each such $f$ there is notjust one, but infinitely many such~$e$.  The \emph{halting function}~$h$is defined by\[h(e, x) =\begin{cases}1 & \text{if $\cfind{e}(x) \fdefined$}\\0 & \text{otherwise.}\end{cases}\]Note that $h(e, x) = 0$ if $\cfind{e}(x) \fundefined$, but alsowhen~$e$ is not the index of a partial recursive function at all.\begin{thm}\ollabel{thm:halting-problem}The halting function~$h$ is not partial recursive.\end{thm}\begin{proof}If $h$were partial recursive, we could define\[d(y) =\begin{cases}1 & \text{if $h(y, y) = 0$}\\\umin{x}{x \neq x} & \text{otherwise.}\end{cases}\]Since no number $x$ satisfies $x \neq x$, there is no $\umin{x}{x \neqx}$, and so $d(y) \fundefined$ iff $h(y,y) \neq 0$. From thisdefinition it follows that\begin{enumerate}\item $d(y) \fdefined$ iff $\cfind{y}(y) \fundefined$ or $y$ is  not the index of a partial recursive function.\item $d(y) \fundefined$ iff $\cfind{y}(y) \fdefined$.\end{enumerate}If $h$ were partial recursive, then $d$ would be partial recursive aswell.  Thus, by the Kleene normal form theorem, it has an index~$e_d$.Consider the value of $h(e_d, e_d)$. There are two possible cases, $0$and~$1$.\begin{enumerate}\item If $h(e_d, e_d) = 1$ then $\cfind{e_d}(e_d) \fdefined$.  But  $\cfind{e_d} \simeq d$, and $d(e_d)$ is defined iff $h(e_d, e_d) = 0$.  So $h(e_d, e_d) \neq 1$.\item If $h(e_d, e_d) = 0$ then either $e_d$ is not the index of a  partial recursive function, or it is and $\cfind{e_d}(e_d)  \fundefined$. But again, $\cfind{e_d} \simeq d$, and $d(e_d)$ is undefined  iff $\cfind{e_d}(e_d) \fdefined$.\end{enumerate}The upshot is that $e_d$ cannot, after all, be the index of a partialrecursive function.  But if $h$ were partial recursive, $d$ would betoo, and so our definition of $e_d$ as an index of it would beadmissible.  We must conclude that $h$ cannot be partial recursive.\end{proof}\end{document}

content/computability/recursive-functions/general-recursive-functions.tex

% Part: computability% Chapter: recursive-functions% Section: general-recursive-functions\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{cmp}{rec}{gen}\olsection{General Recursive Functions}There is another way to obtain a set of total functions. Say a totalfunction $f(x,\vec z)$ is \emph{regular} if for every sequence ofnatural numbers $\vec z$, there is an $x$ such that $f(x,\vec z) = 0$.In other words, the regular functions are exactly those functions towhich one can apply unbounded search, and end up with a totalfunction. One can, conservatively, restrict unbounded search toregular functions:\begin{defn}\ollabel{defn:general-recursive}The set of \emph{general recursive functions} is the smallest set offunctions from the natural numbers to the natural numbers (of variousarities) containing zero, successor, and projections, and closed undercomposition, primitive recursion, and unbounded search applied to\emph{regular} functions.\end{defn}Clearly every general recursive function is total. The differencebetween \olref{defn:general-recursive} and\olref[par]{defn:recursive-fn} is that in the latter one is allowed touse partial recursive functions along the way; the only requirement isthat the function you end up with at the end is total. So the word``general,'' a historic relic, is a misnomer; on the surface,\olref{defn:general-recursive} is \emph{less} general than\olref[par]{defn:recursive-fn}. But, fortunately, the difference isillusory; though the definitions are different, the set of generalrecursive functions and the set of recursive functions are one and thesame.\end{document}