Primitive recursive functions

As part of trying to formalize foundations of arithmetic Richard Dedekind began around 1888 to discuss possible functions that could be defined using recursion (induction). By the 1920s there had then emerged a definite notion of primitive recursive functions. The proof of Gödel's Theorem in 1931 made use of both primitive and general recursive functions—and by the mid-1930s emphasis had shifted to discussion of general recursive functions.

Primitive recursive functions are defined to deal with non-negative integers and to be set up by combining the basic functions z = 0 & (zero), s = # + 1 & (successor) and p[i_] := Slot[i] & (projection) using the operations of composition and primitive recursion

f[0, y___Integer] := g[y]

f[x_Integer, y___Integer] := h[f[x - 1, y], x - 1, y]

Plus and Times can then for example be defined as

plus[0, y_] = y; plus[x_, y_] := s[plus[x - 1, y]]

times[0, y_] = 0; times[x_, y_] := plus[times[x - 1, y], y]

Most familiar integer mathematical functions also turn out to be primitive recursive—examples being Power, Mod, Binomial, GCD and Prime. And indeed in the early 1900s it was thought that perhaps any function that could reasonably be computed would be primitive recursive (see page 1125). But the construction in the late 1920s of the Ackermann function f[m, x, y] discussed above showed that this was not correct. For any primitive recursive function can grow for large x at most like f[m, x, x] with fixed m. Yet f[x, x, x] will always eventually grow faster than this—demonstrating that the whole Ackermann function cannot be primitive recursive. (See page 1162.)

A crucial feature of primitive recursive functions is that the number of steps they take to evaluate is always limited, and can always in effect be determined in advance, since the basic operation of primitive recursion can be unwound simply as

f[x_, y___] := Fold[h[#1, #2, y] &, g[y], Range[0, x - 1]]

And what this means is that any computation that for example fundamentally involves a search that might not terminate cannot be implemented by a primitive recursive function. General recursive functions, however, also allow

μ[f_] = NestWhile[# + 1 &, 0, Function[n, f[n, ##] ≠0]]&

which can perform unbounded searches. (Ordinary primitive recursive functions are always total functions, that give definite values for every possible input. But general recursive functions can be partial functions, that do not terminate for some inputs.) As discussed on page 1121 it turns out that general recursive functions are universal, so that they can be used to represent any possible computable function. (Note that any general recursive function can be expressed in the form c[f, μ[g]] where f and g are primitive recursive.)

In enumerating recursive functions it is convenient to use symbolic definitions for composition and primitive recursion

c[g_, h___] = Apply[g, Through[{h}[##]]] &

r[g_, h_] = If[#1 0, g[##2], h[#0[#1 - 1, ##2], #1 - 1, ##2]] &

where the more efficient unwound form is

r[g_,h_] = Fold[Function[{u, v}, h[u, v, ##2]], g[##2], Range[0, #1 - 1]] &

And in terms of these, for example, plus = r[p[1], s].

The total number of recursive functions grows roughly exponentially in the size (LeafCount) of such expressions, and roughly linearly in the number of arguments.

Most randomly selected primitive recursive functions show very simple behavior—either constant or linearly increasing when fed successive integers as arguments. The smallest examples that show other behavior are:

• r[z, r[s, s]], which is 1/2#(# + 1)&, with quadratic growth

• r[z, r[s, c[s, s]]], which is 2^{# + 1} - # - 2 &, with exponential growth

• r[z, r[s, p[2]]], which is 2^Ceiling[Log[2, # + 2]] - # - 2 &, which shows very simple nesting

• r[z, r[c[s, z], z]], which is Mod[#, 2]&, with repetitive behavior

• r[z, r[s, r[s, s]]] which is Fold[1/2#1(# + 1) + #2 &, 0, Range[#]]&, growing like 2^{2}^{x}.

r[z, r[s, r[s, r[s, p[2]]]]] is the first function to show significantly more complex behavior, and indeed as the picture below indicates, it already shows remarkable randomness. From its definition, the function can be written as

Fold[Fold[2^Ceiling[Log[2, Ceiling[(#1 + 2)/(#2 + 2)]]] (#2 + 2) - 2 - #1 &, #2, Range[#1]] &, 0, Range[#]]&

Its first zeros are at {4, 126, 813, 966, 1166, 1177, 1666, 1897}.

Each zero is immediately followed by a maximum equal to x, and as picture below shows, values tend to accumulate for example on lines of the form ± x/2^{u} ± (2m + 1)2^{v}.

Note that functions of the form Nest[r[c[s, z], #] &, c[s, s], n] are given in terms of the original Ackermann function in the note above by f[n + 1, 2, # + 1] - 1 &.

Before the example above one might have thought that primitive recursive functions would always have to show rather simple behavior. But already an immediate counterexample is Prime. And it turns out that if they never sample values below f[0] the functions in the main text are also all primitive recursive. (Their definitions have a primitive recursive structure, but to operate correctly they must be given integers that are non-negative.)

Among functions with simple explicit definitions, essentially the only examples known fundamentally to be not primitive recursive are ones closely related to the Ackermann function. But given an enumeration of primitive recursive functions (say ordered first by LeafCount, then with Sort) in which the m^{th} function is w[m] diagonalization (see page 1128) yields the function w[x][x] shown below which cannot be primitive recursive. It is inevitable that the function shown must eventually grow faster than any primitive recursive function (at x = 356 its value is 63190, while at x = 1464 it is 1073844). But by reducing the results modulo 2 one gets a function that does not grow—and has seemingly quite random behavior—yet is presumably again not primitive recursive.

(Note that multiple arguments to a recursive function can be encoded as a single argument using functions like the β of page 1120—though the irregularity of such functions tends to make it difficult then to tell what is going on in the underlying recursive function.)