Computability

Recursive Functions

Reading preferences

Optional display controls need JavaScript. All reading content and navigation work without it.

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.

Introduction

In order to develop a mathematical theory of computability, one has to, first of all, develop a model of computability. We now think of computability as the kind of thing that computers do, and computers work with symbols. But at the beginning of the development of theories of computability, the paradigmatic example of computation was numerical computation. Mathematicians were always interested in number-theoretic functions, i.e., functions f:ℕn→ℕf\colon \Nat^n \to \Natsource that can be computed. So it is not surprising that at the beginning of the theory of computability, it was such functions that were studied. The most familiar examples of computable numerical functions, such as addition, multiplication, exponentiation (of natural numbers) share an interesting feature: they can be defined recursively. It is thus quite natural to attempt a general definition of computable function on the basis of recursive definitions. Among the many possible ways to define number-theoretic functions recursively, one particularly simple pattern of definition here becomes central: so-called primitive recursion.

In addition to computable functions, we might be interested in computable sets and relations. A set is computable if we can compute the answer to whether or not a given number is an element of the set, and a relation is computable iff we can compute whether or not a tuple ⟨n1,…,nk⟩\tuple{n_1, \dots, n_k}source is an element of the relation. By considering the characteristic function of a set or relation, discussion of computable sets and relations can be subsumed under that of computable functions. Thus we can define primitive recursive relations as well, e.g., the relation “nnsource evenly divides mmsource” is a primitive recursive relation.

Primitive recursive functions---those that can be defined using just primitive recursion---are not, however, the only computable number-theoretic functions. Many generalizations of primitive recursion have been considered, but the most powerful and widely-accepted additional way of computing functions is by unbounded search. This leads to the definition of partial recursive functions, and a related definition to general recursive functions. General recursive functions are computable and total, and the definition characterizes exactly the partial recursive functions that happen to be total. Recursive functions can simulate every other model of computation (Turing machines, lambda calculus, etc.) and so represent one of the many accepted models of computation.

Primitive Recursion

A characteristic of the natural numbers is that every natural number can be reached from 00source by applying the successor operation +1+1source finitely many times---any natural number is either 00source or the successor of dots the successor of 00source. One way to specify a function h:ℕ→ℕh\colon\Nat \to \Natsource that makes use of this fact is this: (a) specify what the value of hhsource is for argument 00source, and (b) also specify how to, given the value of h(x)h(x)source, compute the value of h(x+1)h(x+1)source. For (a) tells us directly what h(0)h(0)source is, so hhsource is defined for 00source. Now, using the instruction given by (b) for x=0x=0source, we can compute h(1)=h(0+1)h(1) = h(0+1)source from h(0)h(0)source. Using the same instructions for x=1x=1source, we compute h(2)=h(1+1)h(2) = h(1+1)source from h(1)h(1)source, and so on. For every natural number xxsource, we'll eventually reach the step where we define h(x+1)h(x+1)source from h(x)h(x)source, and so h(x)h(x)source is defined for all x∈ℕx \in \Natsource.

For instance, suppose we specify h:ℕ→ℕh\colon \Nat \to \Natsource by the following two equations:

h(0)=1h(x+1)=2·h(x)h(0) & = 1\\ h(x+1) & = 2 \cdot h(x)source

If we already know how to multiply, then these equations give us the information required for (a) and (b) above. By successively applying the second equation, we get that

h(1)=2·h(0)=2,h(2)=2·h(1)=2·2,h(3)=2·h(2)=2·2·2,⋮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,\\ & \vdotssource

We see that the function hhsource we have specified is h(x)=2xh(x) = 2^xsource.

The characteristic feature of the natural numbers guarantees that there is only one function hhsource that meets these two criteria. A pair of equations like these is called a definition by primitive recursion of the function hhsource. It is so-called because we define hhsource “recursively,” i.e., the definition, specifically the second equation, involves hhsource itself on the right-hand-side. It is “primitive” because in defining h(x+1)h(x+1)source we only use the value h(x)h(x)source, i.e., the immediately preceding value. This is the simplest way of defining a function on ℕ\Natsource recursively.

We can define even more fundamental functions like addition and multiplication by primitive recursion. In these cases, however, the functions in question are 22source-place. We fix one of the argument places, and use the other for the recursion. E.g, to define add(x,y)\Add(x, y)source we can fix xxsource and define the value first for y=0y=0source and then for y+1y+1source in terms of yysource. Since xxsource is fixed, it will appear on the left and on the right side of the defining equations.

add(x,0)=xadd(x,y+1)=add(x,y)+1\Add(x,0) & = x\\ \Add(x,y+1) & = \Add(x,y)+1source

These equations specify the value of add\Addsource for all xxsource and yysource. To find add(2,3)\Add(2,3)source, for instance, we apply the defining equations for x=2x = 2source, using the first to find add(2,0)=2\Add(2,0) = 2source, then using the second to successively find add(2,1)=2+1=3\Add(2,1) = 2 + 1 = 3source, add(2,2)=3+1=4\Add(2, 2) = 3 + 1 = 4source, add(2,3)=4+1=5\Add(2, 3) = 4 + 1 = 5source.

In the definition of add\Addsource we used ++source on the right-hand-side of the second equation, but only to add 11source. In other words, we used the successor function succ(z)=z+1\Succ(z) = z+1source and applied it to the previous value add(x,y)\Add(x,y)source to define add(x,y+1)\Add(x,y+1)source. So we can think of the recursive definition as given in terms of a single function which we apply to the previous value. However, it doesn't hurt---and sometimes is necessary---to allow the function to depend not just on the previous value but also on xxsource and yysource. Consider:

mult(x,0)=0mult(x,y+1)=add(mult(x,y),x)\Mult(x,0) & = 0 \\ \Mult(x,y+1) & = \Add(\Mult(x,y),x)source

This is a primitive recursive definition of a function mult\Multsource by applying the function add\Addsource to both the preceding value mult(x,y)\Mult(x,y)source and the first argument xxsource. It also defines the function mult(x,y)\Mult(x,y)source for all arguments xxsource and yysource. For instance, mult(2,3)\Mult(2,3)source is determined by successively computing mult(2,0)\Mult(2,0)source, mult(2,1)\Mult(2,1)source, mult(2,2)\Mult(2,2)source, and mult(2,3)\Mult(2,3)source:

mult(2,0)=0mult(2,1)=mult(2,0+1)=add(mult(2,0),2)=add(0,2)=2mult(2,2)=mult(2,1+1)=add(mult(2,1),2)=add(2,2)=4mult(2,3)=mult(2,2+1)=add(mult(2,2),2)=add(4,2)=6\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) = 6source

The general pattern then is this: to give a primitive recursive definition of a function h(x0,…,xk−1,y)h(x_0, \dots, x_{k-1}, y)source, we provide two equations. The first defines the value of h(x0,…,xk−1,0)h(x_0, \dots, x_{k-1}, 0)source without reference to hhsource. The second defines the value of h(x0,…,xk−1,y+1)h(x_0, \dots, x_{k-1}, y+1)source in terms of h(x0,…,xk−1,y)h(x_0, \dots, x_{k-1}, y)source, the other arguments x0x_0source, dots, xk−1x_{k-1}source, and yysource. Only the immediately preceding value of hhsource may be used in that second equation. If we think of the operations given by the right-hand-sides of these two equations as themselves being functions ffsource and ggsource, then the general pattern to define a new function hhsource by primitive recursion is this:

h(x0,…,xk−1,0)=f(x0,…,xk−1)h(x0,…,xk−1,y+1)=g(x0,…,xk−1,y,h(x0,…,xk−1,y))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))source

In the case of add\Addsource, we have k=1k=1source and f(x0)=x0f(x_0) = x_0source (the identity function), and g(x0,y,z)=z+1g(x_0, y, z) = z + 1source (the 33source-place function that returns the successor of its third argument):

add(x0,0)=f(x0)=x0add(x0,y+1)=g(x0,y,add(x0,y))=succ(add(x0,y))\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))source

In the case of mult\Multsource, we have f(x0)=0f(x_0) = 0source (the constant function always returning 00source) and g(x0,y,z)=add(z,x0)g(x_0, y, z) = \Add(z,x_0)source (the 33source-place function that returns the sum of its last and first argument):

mult(x0,0)=f(x0)=0mult(x0,y+1)=g(x0,y,mult(x0,y))=add(mult(x0,y),x0)\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)source

Composition

If ffsource and ggsource are two one-place functions of natural numbers, we can compose them: h(x)=f(g(x))h(x) = f(g(x))source. The new function h(x)h(x)source is then defined by composition from the functions ffsource and ggsource. We'd like to generalize this to functions of more than one argument.

Here's one way of doing this: suppose ffsource is a kksource-place function, and g0g_0source, dots, gk−1g_{k-1}source are kksource functions which are all nnsource-place. Then we can define a new nnsource-place function hhsource as follows:

h(x0,…,xn−1)=f(g0(x0,…,xn−1),…,gk−1(x0,…,xn−1))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}))source

If ffsource and all gig_isource are computable, so is hhsource: To compute h(x0,…,xn−1)h(x_0, \dots, x_{n-1})source, first compute the values yi=gi(x0,…,xn−1)y_i = g_i(x_0, \dots, x_{n-1})source for each i=0i = 0source, dots, k−1k-1source. Then feed these values into ffsource to compute h(x0,…,xn−1)=f(y0,…,yk−1)h(x_0, \dots, x_{n-1}) = f(y_0, \dots, y_{k-1})source.

This may seem like an overly restrictive characterization of what happens when we compute a new function using some existing ones. For one thing, sometimes we do not use all the arguments of a function, as when we defined g(x,y,z)=succ(z)g(x, y, z) = \Succ(z)source for use in the primitive recursive definition of add\Addsource. Suppose we are allowed use of the following functions:

Pin(x0,…,xn−1)=xi\Proj{n}{i}(x_0, \dots, x_{n-1}) = x_isource

The functions Pin\Proj{n}{i}source are called projection functions: Pin\Proj{n}{i}source is an nnsource-place function. Then ggsource can be defined by

g(x,y,z)=succ(P23(x,y,z)).g(x, y, z) = \Succ(\Proj{3}{2}(x, y, z)).source

Here the role of ffsource is played by the 11source-place function succ\Succsource, so k=1k=1source. And we have one 33source-place function P23\Proj{3}{2}source which plays the role of g0g_0source. The result is a 33source-place function that returns the successor of the third argument.

The projection functions also allow us to define new functions by reordering or identifying arguments. For instance, the function h(x)=add(x,x)h(x) = \Add(x, x)source can be defined by

h(x0)=add(P01(x0),P01(x0)).h(x_0) = \Add(\Proj{1}{0}(x_0),\Proj{1}{0}(x_0)).source

Here k=2k=2source, n=1n=1source, the role of f(y0,y1)f(y_0,y_1)source is played by add\Addsource, and the roles of g0(x0)g_0(x_0)source and g1(x0)g_1(x_0)source are both played by P01(x0)\Proj{1}{0}(x_0)source, the one-place projection function (aka the identity function).

If f(y0,y1)f(y_0, y_1)source is a function we already have, we can define the function h(x0,x1)=f(x1,x0)h(x_0, x_1) = f(x_1, x_0)source by

h(x0,x1)=f(P12(x0,x1),P02(x0,x1)).h(x_0, x_1) = f(\Proj{2}{1}(x_0, x_1),\Proj{2}{0}(x_0, x_1)).source

Here k=2k=2source, n=2n = 2source, and the roles of g0g_0source and g1g_1source are played by P12\Proj{2}{1}source and P02\Proj{2}{0}source, respectively.

You may also worry that g0g_0source, dots, gk−1g_{k-1}source are all required to have the same arity nnsource. (Remember that the arity of a function is the number of arguments; an nnsource-place function has arity nnsource.) But adding the projection functions provides the desired flexibility. For example, suppose ffsource and ggsource are 33source-place functions and hhsource is the 22source-place function defined by

h(x,y)=f(x,g(x,x,y),y).h(x,y) = f(x,g(x,x,y),y).source

The definition of hhsource can be rewritten with the projection functions, as

h(x,y)=f(P02(x,y),g(P02(x,y),P02(x,y),P12(x,y)),P12(x,y)).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)).source

Then hhsource is the composition of ffsource with P02\Proj{2}{0}source, llsource, and P12\Proj{2}{1}source, where

l(x,y)=g(P02(x,y),P02(x,y),P12(x,y)),l(x,y) = g(\Proj{2}{0}(x,y),\Proj{2}{0}(x,y),\Proj{2}{1}(x,y)),source

i.e., llsource is the composition of ggsource with P02\Proj{2}{0}source, P02\Proj{2}{0}source, and P12\Proj{2}{1}source.

Primitive Recursion Functions

Let us record again how we can define new functions from existing ones using primitive recursion and composition.

Definition of primitive recursion

Suppose ffsource is a kksource-place function (k≥1k\ge 1source) and ggsource is a (k+2)(k+2)source-place function. The function defined by primitive recursion from ffsource and ggsource is the (k+1)(k+1)source-place function hhsource defined by the equations

h(x0,…,xk−1,0)=f(x0,…,xk−1)h(x0,…,xk−1,y+1)=g(x0,…,xk−1,y,h(x0,…,xk−1,y))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))source

Definition of composition

Suppose ffsource is a kksource-place function, and g0g_0source, dots, gk−1g_{k-1}source are kksource functions which are all nnsource-place. The function defined by composition from ffsource and g0g_0source, dots, gk−1g_{k-1}source is the nnsource-place function hhsource defined by

h(x0,…,xn−1)=f(g0(x0,…,xn−1),…,gk−1(x0,…,xn−1)).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})).source

In addition to succ\Succsource and the projection functions

Pin(x0,…,xn−1)=xi,\Proj{n}{i}(x_0,\dots,x_{n-1}) = x_i,source

for each natural number nnsource and i<ni < nsource, we will include among the primitive recursive functions the function zero(x)=0\Zero(x) = 0source.

Definition of primitive recursive functions

The set of primitive recursive functions is the set of functions from ℕn\Nat^nsource to ℕ\Natsource, defined inductively by the following clauses:

  1. zero\Zerosource is primitive recursive.

  2. succ\Succsource is primitive recursive.

  3. Each projection function Pin\Proj{n}{i}source is primitive recursive.

  4. If ffsource is a kksource-place primitive recursive function and g0g_0source, dots, gk−1g_{k-1}source are nnsource-place primitive recursive functions, then the composition of ffsource with g0g_0source, dots, gk−1g_{k-1}source is primitive recursive.

  5. If ffsource is a kksource-place primitive recursive function and ggsource is a k+2k+2source-place primitive recursive function, then the function defined by primitive recursion from ffsource and ggsource is primitive recursive.

Explain

Put more concisely, the set of primitive recursive functions is the smallest set containing zero\Zerosource, succ\Succsource, and the projection functions Pjn\Proj{n}{j}source, and which is closed under composition and primitive recursion.

Another way of describing the set of primitive recursive functions is by defining it in terms of “stages.” Let S0S_0source denote the set of starting functions: zero\Zerosource, succ\Succsource, and the projections. These are the primitive recursive functions of stage 00source. Once a stage SiS_isource has been defined, let Si+1S_{i+1}source be the set of all functions you get by applying a single instance of composition or primitive recursion to functions already in SiS_isource. Then

S=⋃i∈ℕSiS = \bigcup_{i \in \Nat} S_isource

is the set of all primitive recursive functions

Let us verify that add\Addsource is a primitive recursive function.

Addition is primitive recursive proposition

The addition function add(x,y)=x+y\Add(x,y) = x+ysource is primitive recursive.

Proof

We already have a primitive recursive definition of add\Addsource in terms of two functions ffsource and ggsource which matches the format of Addition construction reference to primitive recursion:

add(x0,0)=f(x0)=x0add(x0,y+1)=g(x0,y,add(x0,y))=succ(add(x0,y))\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))source

So add\Addsource is primitive recursive provided ffsource and ggsource are as well. f(x0)=x0=P01(x0)f(x_0) = x_0 = \Proj{1}{0}(x_0)source, and the projection functions count as primitive recursive, so ffsource is primitive recursive. The function ggsource is the three-place function g(x0,y,z)g(x_0, y, z)source defined by

g(x0,y,z)=succ(z).g(x_0, y, z) = \Succ(z).source

This does not yet tell us that ggsource is primitive recursive, since ggsource and succ\Succsource are not quite the same function: succ\Succsource is one-place, and ggsource has to be three-place. But we can define ggsource “officially” by composition as

g(x0,y,z)=succ(P23(x0,y,z))g(x_0, y, z) = \Succ(\Proj{3}{2}(x_0, y, z))source

Since succ\Succsource and P23\Proj{3}{2}source count as primitive recursive functions, ggsource does as well, since it can be defined by composition from primitive recursive functions.

Multiplication is primitive recursive proposition

The multiplication function mult(x,y)=x·y\Mult(x,y) = x \cdot ysource is primitive recursive.

Proof

Exercise.

Multiplication proof exercise

Prove Multiplication exercise reference to multiplication proposition by showing that the primitive recursive definition of mult\Multsource can be put into the form required by Multiplication exercise reference to primitive recursion and showing that the corresponding functions ffsource and ggsource are primitive recursive.

First primitive recursion example

Here's our very first example of a primitive recursive definition:

h(0)=1h(y+1)=2·h(y).h(0) & = 1 \\ h(y+1) & = 2 \cdot h(y).source

This function cannot fit into the form required by First example obstacle reference to primitive recursion, since k=0k=0source. The definition also involves the constants 11source and 22source. To get around the first problem, let's introduce a dummy argument and define the function h′h'source:

h′(x0,0)=f(x0)=1h′(x0,y+1)=g(x0,y,h′(x0,y))=2·h′(x0,y).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).source

The function f(x0)=1f(x_0) = 1source can be defined from succ\Succsource and zero\Zerosource by composition: f(x0)=succ(zero(x0))f(x_0) = \Succ(\Zero(x_0))source. The function ggsource can be defined by composition from g′(z)=2·zg'(z) = 2 \cdot zsource and projections:

g(x0,y,z)=g′(P23(x0,y,z))and g′ in turn can be defined by composition asg′(z)=mult(g′′(z),P01(z))andg′′(z)=succ(f(z)),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)),source

where ffsource is as above: f(z)=succ(zero(z))f(z) = \Succ(\Zero(z))source. Now that we have h′h'source, we can use composition again to let h(y)=h′(P01(y),P01(y))h(y) = h'(\Proj{1}{0}(y),\Proj{1}{0}(y))source. This shows that hhsource can be defined from the basic functions using a sequence of compositions and primitive recursions, so hhsource is primitive recursive.

Primitive Recursion Notations

One advantage to having the precise inductive description of the primitive recursive functions is that we can be systematic in describing them. For example, we can assign a “notation” to each such function, as follows. Use symbols zero\Zerosource, succ\Succsource, and Pin\Proj{n}{i}source for zero, successor, and the projections. Now suppose hhsource is defined by composition from a kksource-place function ffsource and nnsource-place functions g0g_0source, dots, gk−1g_{k-1}source, and we have assigned notations FFsource, G0G_0source, dots, Gk−1G_{k-1}source to the latter functions. Then, using a new symbol Compk,n\fn{Comp}_{k,n}source, we can denote the function hhsource by Compk,n[F,G0,…,Gk−1]\fn{Comp}_{k,n}[F,G_0,\dots,G_{k-1}]source.

For functions defined by primitive recursion, we can use analogous notations. Suppose the (k+1)(k+1)source-ary function hhsource is defined by primitive recursion from the kksource-ary function ffsource and the (k+2)(k+2)source-ary function ggsource, and the notations assigned to ffsource and ggsource are FFsource and GGsource, respectively. Then the notation assigned to hhsource is Reck[F,G]\fn{Rec}_k[F,G]source.

Recall that the addition function is defined by primitive recursion as

add(x0,0)=P01(x0)=x0add(x0,y+1)=succ(P23(x0,y,add(x0,y)))=add(x0,y)+1\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) +1source

Here the role of ffsource is played by P01\Proj{1}{0}source, and the role of ggsource is played by succ(P23(x0,y,z))\Succ(\Proj{3}{2}(x_0, y, z))source, which is assigned the notation Comp1,3[succ,P23]\fn{Comp}_{1,3}[\Succ,\Proj{3}{2}]source as it is the result of defining a function by composition from the 11source-ary function succ\Succsource and the 33source-ary function P23\Proj{3}{2}source. With this setup, we can denote the addition function by

Rec1[P01,Comp1,3[succ,P23]].\fn{Rec}_1[\Proj{1}{0},\fn{Comp}_{1,3}[\Succ,\Proj{3}{2}]].source

Having these notations sometimes proves useful, e.g., when enumerating primitive recursive functions.

Multiplication notation exercise

Give the complete primitive recursive notation for mult\Multsource.

Primitive Recursive Functions are Computable

Suppose a function hhsource is defined by primitive recursion

h(x→,0)=f(x→)h(x→,y+1)=g(x→,y,h(x→,y))h(\vec x, 0) & = & f(\vec x) \\ h(\vec x, y + 1) & = & g(\vec x, y, h(\vec x, y))source

and suppose the functions ffsource and ggsource are computable. (We use x→\vec xsource to abbreviate x0x_0source, dots, xk−1x_{k-1}source.) Then h(x→,0)h(\vec x, 0)source can obviously be computed, since it is just f(x→)f(\vec x)source which we assume is computable. h(x→,1)h(\vec x, 1)source can then also be computed, since 1=0+11 = 0 + 1source and so h(x→,1)h(\vec x, 1)source is just

h(x→,1)=g(x→,0,h(x→,0))=g(x→,0,f(x→)).We can go on in this way and computeh(x→,2)=g(x→,1,h(x→,1))=g(x→,1,g(x→,0,f(x→)))h(x→,3)=g(x→,2,h(x→,2))=g(x→,2,g(x→,1,g(x→,0,f(x→))))h(x→,4)=g(x→,3,h(x→,3))=g(x→,3,g(x→,2,g(x→,1,g(x→,0,f(x→)))))⋮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)))))\\ & \vdotssource

Thus, to compute h(x→,y)h(\vec x, y)source in general, successively compute h(x→,0)h(\vec x, 0)source, h(x→,1)h(\vec x, 1)source, dots, until we reach h(x→,y)h(\vec x, y)source.

Thus, a primitive recursive definition yields a new computable function if the functions ffsource and ggsource are computable. Composition of functions also results in a computable function if the functions ffsource and gig_isource are computable.

Since the basic functions zero\Zerosource, succ\Succsource, and Pin\Proj{n}{i}source are computable, and composition and primitive recursion yield computable functions from computable functions, this means that every primitive recursive function is computable.

Examples of Primitive Recursive Functions

We already have some examples of primitive recursive functions: the addition and multiplication functions add\Addsource and mult\Multsource. The identity function id(x)=x\fn{id}(x) = xsource is primitive recursive, since it is just P01\Proj{1}{0}source. The constant functions constn(x)=n\fn{const}_n(x) = nsource are primitive recursive since they can be defined from zero\Zerosource and succ\Succsource by successive composition. This is useful when we want to use constants in primitive recursive definitions, e.g., if we want to define the function f(x)=2·xf(x) = 2 \cdot xsource can obtain it by composition from const2(x)\fn{const}_2(x)source and multiplication as f(x)=mult(const2(x),P01(x))f(x) = \Mult(\fn{const}_2(x), \Proj{1}{0}(x))source. We'll make use of this trick from now on.

Exponentiation is primitive recursive proposition

The exponentiation function exp(x,y)=xy\fn{exp}(x, y) = x^ysource is primitive recursive.

Proof

We can define exp\fn{exp}source primitive recursively as

exp(x,0)=1exp(x,y+1)=mult(x,exp(x,y)).Strictly speaking, this is not a recursive definition from primitive recursive functions. Officially, though, we have:exp(x,0)=f(x)exp(x,y+1)=g(x,y,exp(x,y)).wheref(x)=succ(zero(x))=1g(x,y,z)=mult(P03(x,y,z),P23(x,y,z))=x·z\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 zsource

and so ffsource and ggsource are defined from primitive recursive functions by composition.

Predecessor is primitive recursive proposition

The predecessor function pred(y)\fn{pred}(y)source defined by

pred(y)={0if y=0y−1otherwise\fn{pred}(y) = \begin{cases} 0 & \text{if $y=0$}\\ y-1 & \text{otherwise} \end{cases}source

is primitive recursive.

Proof

Note that

pred(0)=0 andpred(y+1)=y.\fn{pred}(0) & = 0 \text{ and}\\ \fn{pred}(y+1) & = y.source

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 xxsource. It is also odd in that it does not actually use pred(y)\fn{pred}(y)source in the definition of pred(y+1)\fn{pred}(y+1)source. But we can first define pred′(x,y)\fn{pred}'(x, y)source by

pred′(x,0)=zero(x)=0,pred′(x,y+1)=P13(x,y,pred′(x,y))=y.\fn{pred}'(x, 0) & = \Zero(x) = 0,\\ \fn{pred}'(x, y+1) & = \Proj{3}{1}(x, y, \fn{pred'}(x, y)) = y.source

and then define pred\fn{pred}source from it by composition, e.g., as pred(x)=pred′(zero(x),P01(x))\fn{pred}(x) = \fn{pred}'(\Zero(x), \Proj{1}{0}(x))source.

Factorial is primitive recursive proposition

The factorial function fac(x)=x!=1·2·3·…·x\fn{fac}(x) = \fact{x} = 1 \cdot 2 \cdot 3 \cdot \dots \cdot xsource is primitive recursive.

Proof

The obvious primitive recursive definition is

fac(0)=1fac(y+1)=fac(y)·(y+1).Officially, we have to first define a two-place function hh(x,0)=const1(x)h(x,y+1)=g(x,y,h(x,y))where g(x,y,z)=mult(P23(x,y,z),succ(P13(x,y,z))) and then letfac(y)=h(P01(y),P01(y))=h(y,y).\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).source

From now on we'll be a bit more laissez-faire and not give the official definitions by composition and primitive recursion.

Truncated subtraction is primitive recursive proposition

Truncated subtraction, x∸yx \tsub ysource, defined by

x∸y={0if x<yx−yotherwisex \tsub y = \begin{cases} 0 & \text{if $x < y$}\\ x-y & \text{otherwise} \end{cases}source

is primitive recursive.

Proof

We have:

x∸0=xx∸(y+1)=pred(x∸y)x \tsub 0 & = x\\ x \tsub (y+1) & = \fn{pred}(x \tsub y)source

Distance is primitive recursive proposition

The distance between xxsource and yysource, |x−y|\left|x-y\right|source, is primitive recursive.

Proof

We have |x−y|=(x∸y)+(y∸x)\left| x-y \right| = (x \tsub y) + (y \tsub x)source, so the distance can be defined by composition from ++source and ∸\tsubsource, which are primitive recursive.

Maximum is primitive recursive proposition

The maximum of xxsource and yysource, max(x,y)\fn{max}(x,y)source, is primitive recursive.

Proof

We can define max(x,y)\fn{max}(x,y)source by composition from ++source and ∸\tsubsource by

max(x,y)=x+(y∸x).\fn{max}(x,y) \defis x + (y \tsub x).source

If xxsource is the maximum, i.e., x≥yx \ge ysource, then y∸x=0y \tsub x = 0source, so x+(y∸x)=x+0=xx + (y \tsub x) = x + 0 = xsource. If yysource is the maximum, then y∸x=y−xy \tsub x = y - xsource, and so x+(y∸x)=x+(y−x)=yx + (y \tsub x) = x + (y - x) = ysource.

Minimum is primitive recursive proposition

The minimum of xxsource and yysource, min(x,y)\fn{min}(x,y)source, is primitive recursive.

Proof

Exercise.

Minimum proof exercise

Prove Minimum exercise reference to minimum proposition.

Exponent tower exercise

Show that

f(x,y)=2(2⋰2x)}y 2'sf(x, y) = 2^{(2^{\iddots^{2^{x}}})}\raisebox{1ex}{\bigg\rbrace} \raisebox{1ex}{\text {$y$ $2$'s}}source

is primitive recursive.

Integer division construction exercise

Show that integer division d(x,y)=⌊x/y⌋d(x, y) = \lfloor x/y \rfloorsource (i.e., division, where you disregard everything after the decimal point) is primitive recursive. When y=0y = 0source, we stipulate d(x,y)=0d(x, y) = 0source. Give an explicit definition of ddsource using primitive recursion and composition.

Finite sums and products closure proposition

The set of primitive recursive functions is closed under the following two operations:

  1. Finite sums: if f(x→,z)f(\vec x, z)source is primitive recursive, then so is the function

    g(x→,y)=∑z=0yf(x→,z).g(\vec x, y) \defis \sum_{z = 0}^y f(\vec x, z).source

  2. Finite products: if f(x→,z)f(\vec x, z)source is primitive recursive, then so is the function

    h(x→,y)=∏z=0yf(x→,z).h(\vec x, y) \defis \prod_{z = 0}^y f(\vec x, z).source

Proof

For example, finite sums are defined recursively by the equations

g(x→,0)=f(x→,0)g(x→,y+1)=g(x→,y)+f(x→,y+1).g(\vec x, 0) & = f(\vec x, 0)\\ g(\vec x, y+1) & = g(\vec x, y) + f(\vec x, y+1).source

Primitive Recursive Relations

Definition of primitive recursive relations

A relation R(x→)R(\vec x)source is said to be primitive recursive if its characteristic function,

χR(x→)={1if R(x→)0otherwise.\Char{R}(\vec x) = \left\{ \begin{array}{ll} 1 & \mbox{if $R(\vec x)$} \\ 0 & \mbox{otherwise} \end{array} \right.source

is primitive recursive.

In other words, when one speaks of a primitive recursive relation R(x→)R(\vec x)source, one is referring to a relation of the form χR(x→)=1\Char{R}(\vec x) = 1source, where χR\Char{R}source is a primitive recursive function which, on any input, returns either 1 or 0. For example, the relation IsZero(x)\fn{IsZero}(x)source, which holds if and only if x=0x = 0source, corresponds to the function χIsZero\Char{\fn{IsZero}}source, defined using primitive recursion by

χIsZero(0)=1,χIsZero(x+1)=0.\Char{\fn{IsZero}}(0) & = 1,\\ \Char{\fn{IsZero}}(x+1) & = 0.source

It should be clear that one can compose relations with other primitive recursive functions. So the following are also primitive recursive:

  1. The equality relation, x=yx = ysource, defined by IsZero(|x−y|)\fn{IsZero}(\left|x - y\right|)source

  2. The less-than relation, x≤yx \leq ysource, defined by IsZero(x∸y)\fn{IsZero}(x \tsub y)source

Boolean closure proposition for relations

The set of primitive recursive relations is closed under Boolean operations, that is, if P(x→)P(\vec x)source and Q(x→)Q(\vec x)source are primitive recursive, so are

  1. ¬P(x→)\lnot P(\vec x)source

  2. P(x→)∧Q(x→)P(\vec x) \land Q(\vec x)source

  3. P(x→)∨Q(x→)P(\vec x) \lor Q(\vec x)source

  4. P(x→)→Q(x→)P(\vec x) \lif Q(\vec x)source

Proof

Suppose P(x→)P(\vec x)source and Q(x→)Q(\vec x)source are primitive recursive, i.e., their characteristic functions χP\Char{P}source and χQ\Char{Q}source are. We have to show that the characteristic functions of ¬P(x→)\lnot P(\vec x)source, etc., are also primitive recursive.

χ¬P(x→)={0if χP(x→)=11otherwise\Char{\lnot P}(\vec x) = \begin{cases} 0 & \text{if $\Char{P}(\vec x) = 1$}\\ 1 & \text{otherwise} \end{cases}source

We can define χ¬P(x→)\Char{\lnot P}(\vec x)source as 1∸χP(x→)1 \tsub \Char{P}(\vec x)source.

χP∧Q(x→)={1if χP(x→)=χQ(x→)=10otherwise\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}source

We can define χP∧Q(x→)\Char{P \land Q}(\vec x)source as χP(x→)·χQ(x→)\Char{P}(\vec x) \cdot \Char{Q}(\vec x)source or as min(χP(x→),χQ(x→))\fn{min}(\Char{P}(\vec x), \Char{Q}(\vec x))source. Similarly,

χP∨Q(x→)=max(χP(x→),χQ(x→)) andχP→Q(x→)=max(1∸χP(x→),χQ(x→)).\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)).source

Bounded quantification closure proposition

The set of primitive recursive relations is closed under bounded quantification, i.e., if R(x→,z)R(\vec x, z)source is a primitive recursive relation, then so are the relations

(∀z<y)R(x→,z) and(∃z<y)R(x→,z).& \bforall{z < y}{R(\vec x, z)} \text{ and}\\ & \bexists{z < y}{R(\vec x, z)}.source

(∀z<y)R(x→,z)\bforall{z < y}{R(\vec x, z)}source holds of x→\vec xsource and yysource if and only if R(x→,z)R(\vec x, z)source holds for every zzsource less than yysource, and similarly for (∃z<y)R(x→,z)\bexists{z < y}{R(\vec x, z)}source.

Proof

By convention, we take (∀z<0)R(x→,z)\bforall{z < 0}{R(\vec x, z)}source to be true (for the trivial reason that there are no zzsource less than 00source) and (∃z<0)R(x→,z)\bexists{z < 0}{R(\vec x, z)}source to be false. A bounded universal quantifier functions just like a finite product or iterated minimum, i.e., if P(x→,y)⇔(∀z<y)R(x→,z)P(\vec x, y) \defiff \bforall{z < y}{R(\vec x, z)}source then χP(x→,y)\Char{P}(\vec x, y)source can be defined by

χP(x→,0)=1χP(x→,y+1)=min(χP(x→,y),χR(x→,y)).\Char{P}(\vec x, 0) & = 1\\ \Char{P}(\vec x, y+1) & = \fn{min}(\Char{P}(\vec x, y), \Char{R}(\vec x, y)).source

Bounded existential quantification can similarly be defined using max\fn{max}source. Alternatively, it can be defined from bounded universal quantification, using the equivalence (∃z<y)R(x→,z)↔¬(∀z<y)¬R(x→,z)\bexists{z < y}{R(\vec x, z)} \liff \lnot \bforall{z < y}{\lnot R(\vec x, z)}source. Note that, for example, a bounded quantifier of the form (∃x≤y)…x…\bexists{x \leq y}{\dots x\dots}source is equivalent to (∃x<y+1)…x…\bexists{x < y+1}{\dots x \dots}source.

Congruence relation exercise

Show that the three place relation x≡ymodnx \equiv y \mod nsource (congruence modulo nnsource) is primitive recursive.

Another useful primitive recursive function is the conditional function, cond(x,y,z)\fn{cond}(x,y,z)source, defined by

cond(x,y,z)={yif x=0zotherwise.This is defined recursively bycond(0,y,z)=y,cond(x+1,y,z)=z.\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.source

One can use this to justify definitions of primitive recursive functions by cases from primitive recursive relations:

Piecewise primitive recursion proposition

If g0(x→)g_0(\vec x)source, dots, gm(x→)g_m(\vec x)source are primitive recursive functions, and R0(x→)R_0(\vec x)source, dots, Rm−1(x→)R_{m-1}(\vec x)source are primitive recursive relations, then the function ffsource defined by

f(x→)={g0(x→)if R0(x→)g1(x→)if R1(x→) and not R0(x→)⋮gm−1(x→)if Rm−1(x→) and none of the previous holdgm(x→)otherwisef(\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}source

is also primitive recursive.

Proof

When m=1m = 1source, this is just the function defined by

f(x→)=cond(χ¬R0(x→),g0(x→),g1(x→)).f(\vec x) = \fn{cond}(\Char{\lnot R_0}(\vec x),g_0(\vec x),g_1(\vec x)).source

For mmsource greater than 11source, one can just compose definitions of this form.

Bounded Minimization

Explain

It is often useful to define a function as the least number satisfying some property or relation PPsource. If PPsource is decidable, we can compute this function simply by trying out all the possible numbers, 00source, 11source, 22source, dots, until we find the least one satisfying PPsource. This kind of unbounded search takes us out of the realm of primitive recursive functions. However, if we're only interested in the least number less than some independently given bound, we stay primitive recursive. In other words, and a bit more generally, suppose we have a primitive recursive relation R(x,z)R(x,z)source. Consider the function that maps xxsource and yysource to the least z<yz < ysource such that R(x,z)R(x, z)source. It, too, can be computed, by testing whether R(x,0)R(x, 0)source, R(x,1)R(x, 1)source, dots, R(x,y−1)R(x, y-1)source. But why is it primitive recursive?

Bounded minimization proposition

If R(x→,z)R(\vec x, z)source is primitive recursive, so is the function mR(x→,y)m_R(\vec{x}, y)source which returns the least zzsource less than yysource such that R(x→,z)R(\vec x, z)source holds, if there is one, and yysource otherwise. We will write the function mRm_Rsource as

(minz<y)R(x→,z),\bmin{z < y}{R(\vec{x}, z)},source

Proof

Note than there can be no z<0z < 0source such that R(x→,z)R(\vec{x}, z)source since there is no z<0z < 0source at all. So mR(x→,0)=0m_R(\vec x, 0) = 0source.

In case the bound is of the form y+1y + 1source we have three cases:

  1. There is a z<yz < ysource such that R(x→,z)R(\vec{x}, z)source, in which case mR(x→,y+1)=mR(x→,y)m_R(\vec{x}, y+1) = m_R(\vec{x}, y)source.

  2. There is no such z<yz<ysource but R(x→,y)R(\vec{x}, y)source holds, then mR(x→,y+1)=ym_R(\vec{x}, y+1) = ysource.

  3. There is no z<y+1z < y+1source such that R(x→,z)R(\vec{x}, z)source, then mR(x→,y+1)=y+1m_R(\vec{x}, y+1) = y+1source.

So we can define mR(x→,0)m_R(\vec x, 0)source by primitive recursion as follows:

mR(x→,0)=0mR(x→,y+1)={mR(x→,y)if mR(x→,y)≠yyif mR(x→,y)=y and R(x→,y)y+1otherwise.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}source

Note that there is a z<yz<ysource such that R(x→,z)R(\vec x, z)source iff mR(x→,y)≠ym_R(\vec x, y) \neq ysource.

Alternative bounded search exercise

Suppose R(x→,z)R(\vec x, z)source is primitive recursive. Define the function m'R(x→,y)m'_R(\vec{x}, y)source which returns the least zzsource less than yysource such that R(x→,z)R(\vec{x}, z)source holds, if there is one, and 00source otherwise, by primitive recursion from χR\Char{R}source.

Primes

Bounded quantification and bounded minimization provide us with a good deal of machinery to show that natural functions and relations are primitive recursive. For example, consider the relation “xxsource divides yysource”, written x∣yx \mid ysource. The relation x∣yx \mid ysource holds if division of yysource by xxsource is possible without remainder, i.e., if yysource is an integer multiple of xxsource. (If it doesn't hold, i.e., the remainder when dividing yysource by xxsource is >0> 0source, we write x∤yx \nmid ysource.) In other words, x∣yx \mid ysource iff for some zzsource, x·z=yx \cdot z = ysource. Obviously, any such zzsource, if it exists, must be ≤y\leq ysource. So, we have that x∣yx \mid ysource iff for some z≤yz \le ysource, x·z=yx \cdot z = ysource. We can define the relation x∣yx \mid ysource by bounded existential quantification from ==source and multiplication by

x∣y⇔(∃z≤y)(x·z)=y.x \mid y \defiff \bexists{z \leq y}{(x \cdot z) = y}.source

We've thus shown that x∣yx \mid ysource is primitive recursive.

A natural number xxsource is prime if it is neither 00source nor 11source and is only divisible by 11source and itself. In other words, prime numbers are such that, whenever y∣xy \mid xsource, either y=1y = 1source or y=xy=xsource. To test if xxsource is prime, we only have to check if y∣xy \mid xsource for all y≤xy \le xsource, since if y>xy > xsource, then automatically y∤xy \nmid xsource. So, the relation Prime(x)\fn{Prime}(x)source, which holds iff xxsource is prime, can be defined by

Prime(x)⇔x≥2∧(∀y≤x)(y∣x→y=1∨y=x)\fn{Prime}(x) \defiff x \geq 2 \land \bforall{y \leq x}{(y \mid x \lif y = 1 \lor y = x)}source

and is thus primitive recursive.

The primes are 22source, 33source, 55source, 77source, 1111source, etc. Consider the function p(x)p(x)source which returns the xxsourceth prime in that sequence, i.e., p(0)=2p(0) = 2source, p(1)=3p(1) = 3source, p(2)=5p(2) = 5source, etc. (For convenience we will often write p(x)p(x)source as pxp_xsource (p0=2p_0=2source, p1=3p_1=3source, etc.)

If we had a function nextPrime(x)\fn{nextPrime}(x)source, which returns the first prime number larger than xxsource, ppsource can be easily defined using primitive recursion:

p(0)=2p(x+1)=nextPrime(p(x))p(0) & = 2\\ p(x+1) & = \fn{nextPrime}(p(x))source

Since nextPrime(x)\fn{nextPrime}(x)source is the least yysource such that y>xy > xsource and yysource is prime, it can be easily computed by unbounded search. But it can also be defined by bounded minimization, thanks to a result due to Euclid: there is always a prime number between xxsource and x!+1\fact{x}+1source.

nextPrime(x)=(miny≤x!+1)(y>x∧Prime(y)).\fn{nextPrime}(x) = \bmin{y \leq \fact{x}+1}{(y > x \land \fn{Prime}(y))}.source

This shows, that nextPrime(x)\fn{nextPrime}(x)source and hence p(x)p(x)source are (not just computable but) primitive recursive.

(If you're curious, here's a quick proof of Euclid's theorem. Suppose pnp_nsource is the largest prime ≤x\le xsource and consider the product p=p0·p1·…·pnp = p_0\cdot p_1 \cdot \dots \cdot p_nsource of all primes ≤x\le xsource. Either p+1p+1source is prime or there is a prime between xxsource and p+1p+1source. Why? Suppose p+1p+1source is not prime. Then some prime number q∣p+1q \mid p+1source where q<p+1q < p+1source. None of the primes ≤x\le xsource divide p+1p+1source. (By definition of ppsource, each of the primes pi≤xp_i \le xsource divides ppsource, i.e., with remainder 00source. So, each of the primes pi≤xp_i \le xsource divides p+1p+1source with remainder 11source, and so pi∤p+1p_i \nmid p+1source.) Hence, qqsource is a prime >x> xsource and <p+1< p+1source. And p≤x!p \le \fact{x}source, so there is a prime >x> xsource and ≤x!+1\le \fact{x}+1source.)

Bounded minimization division exercise

Define integer division d(x,y)d(x, y)source using bounded minimization.

Sequences

The set of primitive recursive functions is remarkably robust. But we will be able to do even more once we have developed a adequate means of handling sequences. We will identify finite sequences of natural numbers with natural numbers in the following way: the sequence ⟨a0,a1,a2,…,ak⟩\langle a_0, a_1, a_2, \dots, a_k \ranglesource corresponds to the number

p0a0+1·p1a1+1·p2a2+1·…·pkak+1.p_0^{a_0+1} \cdot p_1^{a_1+1} \cdot p_2^{a_2+1} \cdot \dots \cdot p_k^{a_k+1}.source

We add one to the exponents to guarantee that, for example, the sequences ⟨2,7,3⟩\langle 2, 7, 3\ranglesource and ⟨2,7,3,0,0⟩\langle 2, 7, 3, 0, 0 \ranglesource have distinct numeric codes. We can take both 00source and 11source to code the empty sequence; for concreteness, let Λ\emptyseqsource denote 00source.

The reason that this coding of sequences works is the so-called Fundamental Theorem of Arithmetic: every natural number n≥2n \ge 2source can be written in one and only one way in the form

n=p0a0·p1a1·…·pkakn = p_0^{a_0} \cdot p_1^{a_1} \cdot \dots \cdot p_k^{a_k}source

with ak≥1a_k \ge 1source. This guarantees that the mapping ⟨⟩(a0,…,ak)=⟨a0,…,ak⟩\tuple{}(a_0, \dots, a_k) = \tuple{a_0, \dots, a_k}source is injective: different sequences are mapped to different numbers; to each number only at most one sequence corresponds.

We'll now show that the operations of determining the length of a sequence, determining its iisourceth element, appending an element to a sequence, and concatenating two sequences, are all primitive recursive.

Sequence length proposition

The function len(s)\len{s}source, which returns the length of the sequence sssource, is primitive recursive.

Proof

Let R(i,s)R(i, s)source be the relation defined by

R(i,s) iff pi∣s∧pi+1∤s.R(i, s) \text{ iff } p_i \mid s \land p_{i+1} \nmid s.source

RRsource is clearly primitive recursive. Whenever sssource is the code of a non-empty sequence, i.e.,

s=p0a0+1·…·pkak+1,s = p_0^{a_0+1} \cdot \dots \cdot p_{k}^{a_{k}+1},source

R(i,s)R(i,s)source holds if pip_isource is the largest prime such that pi∣sp_i \mid ssource, i.e., i=ki = ksource. The length of sssource thus is i+1i+1source iff pip_isource is the largest prime that divides sssource, so we can let

len(s)={0if s=0 or s=11+(mini<s)R(i,s)otherwise\len{s} = \begin{cases} 0 & \text{if $s = 0$ or $s = 1$} \\ 1 + \bmin{i < s}{R(i, s)} & \text{otherwise} \end{cases}source

We can use bounded minimization here, since there is only one iisource that satisfies R(i,s)R(i,s)source when sssource is a code of a sequence, and if iisource exists it is less than sssource itself.

Sequence append proposition

The function append(s,a)\fn{append}(s,a)source, which returns the result of appending aasource to the sequence sssource, is primitive recursive.

Proof

append\fn{append}source can be defined by:

append(s,a)={2a+1if s=0 or s=1s·plen(s)a+1otherwise.\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}source

Sequence element proposition

The function element(s,i)\fn{element}(s,i)source, which returns the iisourceth element of sssource (where the initial element is called the 00sourceth), or 00source if iisource is greater than or equal to the length of sssource, is primitive recursive.

Proof

Note that aasource is the iisourceth element of sssource iff pia+1p_i^{a+1}source is the largest power of pip_isource that divides sssource, i.e., pia+1∣sp_i^{a+1} \mid ssource but pia+2∤sp_i^{a+2} \nmid ssource. So:

element(s,i)={0if i≥len(s)(mina<s)(pia+2∤s)otherwise.\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}source

Instead of using the official names for the functions defined above, we introduce a more compact notation. We will use (s)i(s)_isource instead of element(s,i)\fn{element}(s,i)source, and ⟨s0,…,sk⟩\tuple{s_0, \dots, s_k}source to abbreviate

append(append(…append(Λ,s0)…),sk).\fn{append}(\fn{append}(\dots \fn{append}(\emptyseq,s_0) \dots),s_k).source

Note that if sssource has length kksource, the elements of sssource are (s)0(s)_0source, dots, (s)k−1(s)_{k-1}source.

Sequence concatenation proposition

The function concat(s,t)\fn{concat}(s,t)source, which concatenates two sequences, is primitive recursive.

Proof

We want a function concat\fn{concat}source with the property that

concat(⟨a0,…,ak⟩,⟨b0,…,bl⟩)=⟨a0,…,ak,b0,…,bl⟩.\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}.source

We'll use a “helper” function hconcat(s,t,n)\fn{hconcat}(s,t,n)source which concatenates the first nnsource symbols of ttsource to sssource. This function can be defined by primitive recursion as follows:

hconcat(s,t,0)=shconcat(s,t,n+1)=append(hconcat(s,t,n),(t)n)Then we can define concat byconcat(s,t)=hconcat(s,t,len(t)).\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}).source

We will write s⌢ts \concat tsource instead of concat(s,t)\fn{concat}(s,t)source.

It will be useful for us to be able to bound the numeric code of a sequence in terms of its length and its largest element. Suppose sssource is a sequence of length kksource, each element of which is less than or equal to some number xxsource. Then sssource has at most kksource prime factors, each at most pk−1p_{k-1}source, and each raised to at most x+1x+1source in the prime factorization of sssource. In other words, if we define

sequenceBound(x,k)=pk−1k·(x+1),\fn{sequenceBound}(x,k) = p_{k-1}^{k \cdot (x+1)},source

then the numeric code of the sequence sssource described above is at most sequenceBound(x,k)\fn{sequenceBound}(x,k)source.

Having such a bound on sequences gives us a way of defining new functions using bounded search. For example, we can define concat\fn{concat}source using bounded search. All we need to do is write down a primitive recursive specification of the object (number of the concatenated sequence) we are looking for, and a bound on how far to look. The following works:

concat(s,t)={Λif len(s)+len(t)=0,(minv<sequenceBound(s+t,len(s)+len(t)))len(v)=len(s)+len(t)∧(∀i<len(s))(v)i=(s)i∧(∀j<len(t))(v)len(s)+j=(t)jotherwise.\fn{concat}(s,t)=\begin{cases}\emptyseq & \text{if }\len{s}+\len{t}=0,\\ \bmin{v < \fn{sequenceBound}(s+t,\len{s}+\len{t})}{\len{v}=\len{s}+\len{t} \land \bforall{i<\len{s}}{(v)_i=(s)_i} \land \bforall{j<\len{t}}{(v)_{\len{s}+j}=(t)_j} }& \text{otherwise.}\end{cases}source

Sequence list concatenation exercise

Show that there is a primitive recursive function sconcat(s)\fn{sconcat}(s)source with the property that

sconcat(⟨s0,…,sk⟩)=s0⌢…⌢sk.\fn{sconcat}(\tuple{s_0, \dots, s_k}) = s_0 \concat \dots \concat s_k.source

Sequence tail exercise

Show that there is a primitive recursive function tail(s)\fn{tail}(s)source with the property that

tail(Λ)=0 andtail(⟨s0,…,sk⟩)=⟨s1,…,sk⟩.\fn{tail}(\emptyseq) & = 0 \text{ and}\\ \fn{tail}(\tuple{s_0, \dots, s_{k}}) & = \tuple{s_1, \dots, s_{k}}.source

Subsequence is primitive recursive proposition

The function subseq(s,i,n)\fn{subseq}(s, i, n)source which returns the subsequence of sssource of length nnsource beginning at the iisourceth element, is primitive recursive.

Proof

Exercise.

Subsequence proof exercise

Prove Subsequence exercise reference to subsequence proposition.

Trees

Sometimes it is useful to represent trees as natural numbers, just like we can represent sequences by numbers and properties of and operations on them by primitive recursive relations and functions on their codes. We'll use sequences and their codes to do this. A tree can 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 is called the root of the tree, and the subtrees it is connected to its immediate subtrees.

We code trees recursively as a sequence ⟨k,d1,…,dk⟩\tuple{k, d_1, \dots, d_k}source, where kksource is the number of immediate subtrees and d1d_1source, dots, dkd_ksource the codes of the immediate subtrees. If the nodes have labels, they can be included after the immediate subtrees. So a tree consisting just of a single node with label llsource would be coded by ⟨0,l⟩\tuple{0,l}source, and a tree consisting of a root (labelled l1l_1source) connected to two single nodes (labelled l2l_2source, l3l_3source) would be coded by ⟨2,⟨0,l2⟩,⟨0,l3⟩,l1⟩\tuple{2, \tuple{0, l_2}, \tuple{0, l_3}, l_1}source.

Subtree sequence is primitive recursive proposition

The function SubtreeSeq(t)\fn{SubtreeSeq}(t)source, which returns the code of a sequence the elements of which are the codes of all subtrees of the tree with code ttsource, is primitive recursive.

Proof

First note that ISubtrees(t)=subseq(t,1,(t)0)\fn{ISubtrees}(t) = \fn{subseq}(t, 1, (t)_0)source is primitive recursive and returns the codes of the immediate subtrees of a tree ttsource. Now we can define a helper function hSubtreeSeq(t,n)\fn{hSubtreeSeq}(t,n)source which computes the sequence of all subtrees which are nnsource nodes removed from the root. The sequence of subtrees of ttsource which is 00source nodes removed from the root---in other words, begins at the root of ttsource---is the sequence consisting just of ttsource. To obtain a sequence of all level n+1n+1source subtrees of ttsource, we concatenate the level nnsource subtrees with a sequence consisting of all immediate subtrees of the level nnsource subtrees. To get a list of all these, note that if f(x)f(x)source is a primitive recursive function returning codes of sequences, then gf(s,k)={Λif k=0,f((s)0)⌢…⌢f((s)k−1)if k>0.g_f(s,k)=\begin{cases}\emptyseq & \text{if }k=0,\\ f((s)_0)\concat\dots\concat f((s)_{k-1}) & \text{if }k>0.\end{cases}source is also primitive recursive:

gf(s,0)=Λgf(s,k+1)=gf(s,k)⌢f((s)k)g_f(s,0)=\emptyseq \\ g_f(s,k+1)=g_f(s,k)\concat f((s)_k)source

For instance, if sssource is a sequence of trees, then h(s)=gISubtrees(s,len(s))h(s) = g_{\fn{ISubtrees}}(s, \len{s})source gives the sequence of the immediate subtrees of the elements of sssource. We can use it to define hSubtreeSeq\fn{hSubtreeSeq}source by

hSubtreeSeq(t,0)=⟨t⟩hSubtreeSeq(t,n+1)=hSubtreeSeq(t,n)⌢h(hSubtreeSeq(t,n)).\fn{hSubtreeSeq}(t, 0) & = \tuple{t} \\ \fn{hSubtreeSeq}(t, n+1) & = \fn{hSubtreeSeq}(t, n) \concat h(\fn{hSubtreeSeq}(t, n)).source

The maximum level of subtrees in a tree coded by ttsource, i.e., the maximum distance between the root and a leaf node, is bounded by the code ttsource. So a sequence of codes of all subtrees of the tree coded by ttsource is given by hSubtreeSeq(t,t)\fn{hSubtreeSeq}(t, t)source.

Duplicate free subtree exercise

The definition of hSubtreeSeq\fn{hSubtreeSeq}source in the proof of Duplicate free subtree exercise reference in general includes repetitions. Give an alternative definition which guarantees that the code of a subtree occurs only once in the resulting list.

Other Recursions

Using pairing and sequencing, we can justify more exotic (and useful) forms of primitive recursion. For example, it is often useful to define two functions simultaneously, such as in the following definition:

h0(x→,0)=f0(x→)h1(x→,0)=f1(x→)h0(x→,y+1)=g0(x→,y,h0(x→,y),h1(x→,y))h1(x→,y+1)=g1(x→,y,h0(x→,y),h1(x→,y))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))source

This is an instance of simultaneous recursion. Another useful way of defining functions is to give the value of h(x→,y+1)h(\vec x, y+1)source in terms of all the values h(x→,0)h(\vec x, 0)source, dots, h(x→,y)h(\vec x, y)source, as in the following definition:

h(x→,0)=f(x→)h(x→,y+1)=g(x→,y,⟨h(x→,0),…,h(x→,y)⟩).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)}).source

The following schema captures this idea more succinctly:

h(x→,y)=g(x→,y,⟨h(x→,0),…,h(x→,y−1)⟩)h(\vec x, y) = g(\vec x, y, \tuple{h(\vec x, 0), \dots, h(\vec x, y-1)})source

with the understanding that the last argument to ggsource is just the empty sequence when yysource is 00source. In either formulation, the idea is that in computing the “successor step,” the function hhsource can make use of the entire sequence of values computed so far. This is known as a course-of-values recursion. For a particular example, it can be used to justify the following type of definition:

h(x→,y)={g(x→,y,h(x→,k(x→,y)))if k(x→,y)<yf(x→)otherwiseh(\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}source

In other words, the value of hhsource at yysource can be computed in terms of the value of hhsource at any previous value, given by kksource.

Remainder by course of values exercise

Define the remainder function r(x,y)r(x,y)source by course-of-values recursion. (If xxsource, yysource are natural numbers and y>0y > 0source, r(x,y)r(x,y)source is the number less than yysource such that x=z×y+r(x,y)x = z\times y + r(x,y)source for some zzsource. For definiteness, let's say that if y=0y=0source, r(x,0)=0r(x,0) = 0source.)

You should think about how to obtain these functions using ordinary primitive recursion. One final version of primitive recursion is more flexible in that one is allowed to change the parameters (side values) along the way:

h(x→,0)=f(x→)h(x→,y+1)=g(x→,y,h(k(x→),y))h(\vec x, 0) & = f(\vec x) \\ h(\vec x, y+1) & = g(\vec x, y, h(k(\vec x), y))source

This, too, can be simulated with ordinary primitive recursion. (Doing so is tricky. For a hint, try unwinding the computation by hand.)

Non-Primitive Recursive Functions

The primitive recursive functions do not exhaust the intuitively computable functions. It should be intuitively clear that we can make a list of all the unary primitive recursive functions, f0f_0source, f1f_1source, f2f_2source, dots such that we can effectively compute the value of fxf_xsource on input yysource; in other words, the function g(x,y)g(x,y)source, defined by

g(x,y)=fx(y)g(x,y) = f_x(y)source

is computable. But then so is the function

h(x)=g(x,x)+1=fx(x)+1.h(x) & = & g(x,x) + 1 \\ & = & f_x(x) +1.source

For each primitive recursive function fif_isource, the value of hhsource and fif_isource differ at iisource. So hhsource is computable, but not primitive recursive; and one can say the same about ggsource. This is an “effective” version of Cantor's diagonalization argument.

One can provide more explicit examples of computable functions that are not primitive recursive. For example, let the notation gn(x)g^n(x)source denote g(g(…g(x)))g(g(\dots g(x)))source, with nnsource ggsource's in all; and define a sequence g0,g1,…g_0,g_1,\dotssource of functions by

g0(x)=x+1gn+1(x)=gnx(x)g_0(x) & = & x+1 \\ g_{n + 1}(x) & = & g_n^x(x)source

You can confirm that each function gng_nsource is primitive recursive. Each successive function grows much faster than the one before; g1(x)g_1(x)source is equal to 2x2xsource, g2(x)g_2(x)source is equal to 2x·x2^x \cdot xsource, and g3(x)g_3(x)source grows roughly like an exponential stack of xxsource 22source's. The Ackermann--P\'eter function is essentially the function G(x)=gx(x)G(x) = g_x(x)source, and one can show that this grows faster than any primitive recursive function.

Let us return to the issue of enumerating the primitive recursive functions. Remember that we have assigned symbolic notations to each primitive recursive function; so it suffices to enumerate notations. We can assign a natural number #(F)\#(F)source to each notation FFsource, recursively, as follows:

#(0)=⟨0⟩#(S)=⟨1⟩#(Pin)=⟨2,n,i⟩#(Compk,l[H,G0,…,Gk−1])=⟨3,k,l,#(H),#(G0),…,#(Gk−1)⟩#(Recl[G,H])=⟨4,l,#(G),#(H)⟩\#(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}]) & = & \langle 3,k,l,\#(H),\#(G_0),\dots,\#(G_{k-1}) \rangle \\ \#(\fn{Rec}_l[G,H]) & = & \langle 4, l, \#(G), \#(H) \ranglesource

Here we are using the fact that every sequence of numbers can be viewed as a natural number, using the codes from the last section. The upshot is that every code is assigned a natural number. Of course, some sequences (and hence some numbers) do not correspond to notations; but we can let fif_isource be the unary primitive recursive function with notation coded as iisource, if iisource codes such a notation; and the constant 00source function otherwise. The net result is that we have an explicit way of enumerating the unary primitive recursive functions.

(In fact, some functions, like the constant zero function, will appear more than once on the list. This is not just an artifact of our coding, but also a result of the fact that the constant zero function has more than one notation. We will later see that one can not computably avoid these repetitions; for example, there is no computable function that decides whether or not a given notation represents the constant zero function.)

We can now take the function g(x,y)g(x,y)source to be given by fx(y)f_x(y)source, where fxf_xsource refers to the enumeration we have just described. How do we know that g(x,y)g(x,y)source is computable? Intuitively, this is clear: to compute g(x,y)g(x,y)source, first “unpack” xxsource, and see if it is a notation for a unary function. If it is, compute the value of that function on input yysource.

Digress

You may already be convinced that (with some work!) one can write a program (say, in Java or C++) that does this; and now we can appeal to the 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)g(x,y)source is computable is to describe a Turing machine that computes it, explicitly. This would, in particular, avoid the Church--Turing thesis and appeals to intuition. Soon we will have built up enough machinery to show that g(x,y)g(x,y)source is computable, appealing to a model of computation that can be simulated on a Turing machine: namely, the recursive functions.

Partial Recursive Functions

To motivate the definition of the recursive functions, note that our proof that there are computable functions that are not primitive recursive actually establishes much more. The argument was simple: all we used was the fact that it is possible to enumerate functions f0,f1,…f_0,f_1,\dotssource such that, as a function of xxsource and yysource, fx(y)f_x(y)source is computable. So the argument applies to any class of functions that can be enumerated in such a way. This puts us in a bind: we would like to describe the computable functions explicitly; but any explicit description of a collection of computable functions cannot be exhaustive!

The way out is to allow partial functions to come into play. We will see that it is possible to enumerate the partial computable functions. 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 diagonal argument later, and explore why it does not go through when partial functions are included.

The question is now this: what do we need to add to the primitive recursive functions to obtain all the partial recursive functions? We need to do two things:

  1. Modify our definition of the primitive recursive functions to allow for partial functions as well.

  2. Add something to the definition, so that some new partial functions are included.

The first is easy. As before, we will start with zero, successor, and projections, and close under composition and primitive recursion. The only difference is that we have to modify the definitions of composition and primitive recursion to allow for the possibility that some of the terms in the definition are not defined. If ffsource and ggsource are partial functions, we will write f(x)↓f(x) \fdefinedsource to mean that ffsource is defined at xxsource, i.e., xxsource is in the domain of ffsource; and f(x)↑f(x) \fundefinedsource to mean the opposite, i.e., that ffsource is not defined at xxsource. We will use f(x)≃g(x)f(x) \simeq g(x)source to mean that either f(x)f(x)source and g(x)g(x)source are both undefined, or they are both defined and equal. We will use these notations for more complicated terms as well. We will adopt the convention that if hhsource and g0g_0source, dots, gkg_ksource all are partial functions, then

h(g0(x→),…,gk(x→))h(g_0(\vec x),\dots,g_k(\vec x))source

is defined if and only if each gig_isource is defined at x→\vec xsource, and hhsource is defined at g0(x→)g_0(\vec x)source, dots, gk(x→)g_k(\vec x)source. With this understanding, the definitions of composition and primitive recursion for partial functions is just as above, except that we have to replace “==source” by “≃\simeqsource”.

What we will add to the definition of the primitive recursive functions to obtain partial functions is the unbounded search operator. If f(x,z→)f(x,\vec z)source is any partial function on the natural numbers, define μx;f(x,z→)\mu x \; f(x,\vec z)source to be

the least xxsource such that f(0,z→),f(1,z→),…,f(x,z→)f(0,\vec z), f(1,\vec z), \dots, f(x,\vec z)source are all defined, and f(x,z→)=0f(x,\vec z) = 0source, if such an xxsource exists

with the understanding that μx;f(x,z→)\mu x \; f(x,\vec z)source is undefined otherwise. This defines μx;f(x,z→)\mu x \; f(x,\vec z)source uniquely.

Explain

Note that our definition makes no reference to Turing machines, or algorithms, or any specific computational model. But like composition and primitive recursion, there is an operational, computational intuition behind unbounded search. When it comes to the computability of a partial function, arguments where the function is undefined correspond to inputs for which the computation does not halt. The procedure for computing μx;f(x,z→)\mu x \; f(x,\vec z)source will amount to this: compute f(0,z→),f(1,z→),f(2,z→)f(0,\vec z), f(1,\vec z), f(2,\vec z)source until a value of 0 is returned. If any of the intermediate computations do not halt, however, neither does the computation of μx;f(x,z→)\mu x \; f(x,\vec z)source.

If R(x,z→)R(x,\vec z)source is any relation, μx;R(x,z→)\mu x \; R(x,\vec z)source is defined to be μx;(1∸χR(x,z→))\mu x \; (1 \tsub \Char{R}(x,\vec z))source. In other words, μx;R(x,z→)\mu x \; R(x,\vec z)source returns the least value of xxsource such that R(x,z→)R(x,\vec z)source holds. So, if f(x,z→)f(x,\vec z)source is a total function, μx;f(x,z→)\mu x \; f(x,\vec z)source is the same as μx;(f(x,z→)=0)\mu x \; (f(x,\vec z) = 0)source. But note that our original definition is more general, since it allows for the possibility that f(x,z→)f(x,\vec z)source is not everywhere defined (whereas, in contrast, the characteristic function of a relation is always total).

Definition of partial recursive functions

The set of partial recursive functions is the smallest set of partial functions from the natural numbers to the natural numbers (of various arities) containing zero, successor, and projections, and closed under composition, primitive recursion, and unbounded search.

Of course, some of the partial recursive functions will happen to be total, i.e., defined for every argument.

Definition of recursive functions

The set of recursive functions is the set of partial recursive functions that are total.

A recursive function is sometimes called “total recursive” to emphasize that it is defined everywhere.

The Normal Form Theorem

Kleene normal form theorem

[Kleene's Normal Form Theorem] There is a primitive recursive relation T(e,x,s)T(e, x, s)source and a primitive recursive function U(s)U(s)source, with the following property: if ffsource is any partial recursive function, then for some eesource,

f(x)≃U(μsT(e,x,s))f(x) \simeq U(\umin{s}{T(e, x, s)})source

for every xxsource.

Explain

The proof of the normal form theorem is involved, but the basic idea is simple. Every partial recursive function has an index eesource, intuitively, a number coding its program or definition. If f(x)↓f(x) \fdefinedsource, the computation can be recorded systematically and coded by some number sssource, and the fact that sssource codes the computation of ffsource on input xxsource can be checked primitive recursively using only xxsource and the definition eesource. Consequently, the relation TTsource, “the function with index eesource has a computation for input xxsource, and sssource codes this computation,” is primitive recursive. Given the full record of the computation sssource, the “upshot” of sssource is the value of f(x)f(x)source, and it can be obtained from sssource primitive recursively as well.

The normal form theorem shows that only a single unbounded search is required for the definition of any partial recursive function. Basically, we can search through all numbers until we find one that codes a computation of the function with index eesource for input xxsource. We can use the numbers eesource as “names” of partial recursive functions, and write φe\cfind{e}source for the function ffsource defined by the equation in the theorem. Note that any partial recursive function can have more than one index---in fact, every partial recursive function has infinitely many indices.

The Halting Problem

The halting problem in general is the problem of deciding, given the specification eesource (e.g., program) of a computable function and a number nnsource, whether the computation of the function on input nnsource halts, i.e., produces a result. Famously, Alan Turing proved that this problem itself cannot be solved by a computable function, i.e., the function

h(e,n)={1if computation e halts on input n0otherwise,h(e, n) = \begin{cases} 1 & \text{if computation $e$ halts on input $n$}\\ 0 & \text{otherwise,} \end{cases}source

is not computable.

In the context of partial recursive functions, the role of the specification of a program may be played by the index eesource given in Kleene's normal form theorem. If ffsource is a partial recursive function, any eesource for which the equation in the normal form theorem holds, is an index of ffsource. Given a number eesource, the normal form theorem states that

φe(x)≃U(μs;T(e,x,s))\cfind{e}(x) \simeq U(\mu s \; T(e, x, s))source

is partial recursive, and for every partial recursive f:ℕ→ℕf\colon \Nat \to \Natsource, there is an e∈ℕe \in \Natsource such that φe(x)≃f(x)\cfind{e}(x) \simeq f(x)source for all x∈ℕx \in \Natsource. In fact, for each such ffsource there is not just one, but infinitely many such eesource. The halting function hhsource is defined by

h(e,x)={1if φe(x)↓0otherwise.h(e, x) = \begin{cases} 1 & \text{if $\cfind{e}(x) \fdefined$}\\ 0 & \text{otherwise.} \end{cases}source

Note that h(e,x)=0h(e, x) = 0source if φe(x)↑\cfind{e}(x) \fundefinedsource, but also when φe(x)↑\cfind{e}(x) \fundefinedsource is not the index of a partial recursive function at all.

Halting function nonrecursiveness theorem

The halting function hhsource is not partial recursive.

Proof

If hhsource were partial recursive, we could define

d(y)={1if h(y,y)=0μxx≠xotherwise.d(y) = \begin{cases} 1 & \text{if $h(y, y) = 0$}\\ \umin{x}{x \neq x} & \text{otherwise.} \end{cases}source

Since no number xxsource satisfies x≠xx \neq xsource, there is no μxx≠x\umin{x}{x \neq x}source, and so d(y)↑d(y) \fundefinedsource iff h(y,y)≠0h(y,y) \neq 0source. From this definition it follows that

  1. d(y)↓d(y) \fdefinedsource iff φy(y)↑\cfind{y}(y) \fundefinedsource or yysource is not the index of a partial recursive function.

  2. d(y)↑d(y) \fundefinedsource iff φy(y)↓\cfind{y}(y) \fdefinedsource.

If hhsource were partial recursive, then ddsource would be partial recursive as well. Thus, by the Kleene normal form theorem, it has an index ede_dsource. Consider the value of h(ed,ed)h(e_d, e_d)source. There are two possible cases, 00source and 11source.

  1. If h(ed,ed)=1h(e_d, e_d) = 1source then φed(ed)↓\cfind{e_d}(e_d) \fdefinedsource. But φed≃d\cfind{e_d} \simeq dsource, and d(ed)d(e_d)source is defined iff h(ed,ed)=0h(e_d, e_d) = 0source. So h(ed,ed)≠1h(e_d, e_d) \neq 1source.

  2. If h(ed,ed)=0h(e_d, e_d) = 0source then either ede_dsource is not the index of a partial recursive function, or it is and φed(ed)↑\cfind{e_d}(e_d) \fundefinedsource. But again, φed≃d\cfind{e_d} \simeq dsource, and d(ed)d(e_d)source is undefined iff φed(ed)↓\cfind{e_d}(e_d) \fdefinedsource.

The upshot is that ede_dsource cannot, after all, be the index of a partial recursive function. But if hhsource were partial recursive, ddsource would be too, and so our definition of ede_dsource as an index of it would be admissible. We must conclude that hhsource cannot be partial recursive.

General Recursive Functions

There is another way to obtain a set of total functions. Say a total function f(x,z→)f(x,\vec z)source is regular if for every sequence of natural numbers z→\vec zsource, there is an xxsource such that f(x,z→)=0f(x,\vec z) = 0source. In other words, the regular functions are exactly those functions to which one can apply unbounded search, and end up with a total function. One can, conservatively, restrict unbounded search to regular functions:

Definition of general recursive functions

The set of general recursive functions is the smallest set of functions from the natural numbers to the natural numbers (of various arities) containing zero, successor, and projections, and closed under composition, primitive recursion, and unbounded search applied to regular functions.

Clearly every general recursive function is total. The difference between Initial comparison reference to general recursion definition and Initial comparison reference to recursive function definition is that in the latter one is allowed to use partial recursive functions along the way; the only requirement is that the function you end up with at the end is total. So the word “general,” a historic relic, is a misnomer; on the surface, Misnomer comparison reference to general recursion definition is less general than Equivalence comparison reference to recursive function definition. But, fortunately, the difference is illusory; though the definitions are different, the set of general recursive functions and the set of recursive functions are one and the same.

Source disclosures