nLab
partial recursive function

Context

Constructivism, Realizability, Computability

Deduction and induction

Foundations

Contents

Idea

A partial recursive function (often “computable function”, but see there for disambiguation) is a partial function of natural numbers which can be defined by an algorithm or computer program (e.g., a Turing machine), taking finitely many natural numbers as inputs, and which on input may run forever, but otherwise eventually halts and returns a natural number as output.

This idea as described is vague until it is circumscribed by a specific notion of computer program (Turing machines, register machines, abaci, etc.). There is a standard article of faith called the “Church-Turing thesis”, identifying functions on natural numbers that are algorithmically computable with those that are computable using a Turing machine (or some variant class of machines that is Turing-complete).

A purely mathematical definition of the intended class of functions is given below.

Definition

Definition

A partial recursive function is a partial function from k\mathbb{N}^k to \mathbb{N} (where \mathbb{N} is the set of natural numbers and k0k \geq 0 is finite) that belongs to the smallest class 𝒞\mathcal{C} of partial functions that

  • includes all constant functions 11 \to \mathbb{N};

  • includes all projection maps π i: k\pi_i: \mathbb{N}^k \to \mathbb{N}, i=1,,ki = 1, \ldots, k;

  • includes the successor function s:s: \mathbb{N} \to \mathbb{N};

  • is closed under composition: if f 1: k,,f n: kf_1: \mathbb{N}^{k} \to \mathbb{N}, \ldots, f_n: \mathbb{N}^{k} \to \mathbb{N} and g: ng: \mathbb{N}^n \to \mathbb{N} belong to 𝒞\mathcal{C}, then so does g(f 1,,f n): kg \circ (f_1, \ldots, f_n): \mathbb{N}^{k} \to \mathbb{N};

  • is closed under primitive recursion: if g: kg: \mathbb{N}^k \to \mathbb{N} and h: k+2h: \mathbb{N}^{k+2} \to \mathbb{N} belong to 𝒞\mathcal{C}, then the function f: k+1f: \mathbb{N}^{k+1} \to \mathbb{N} defined recursively by the equations (for yy \in \mathbb{N} and x k\mathbf{x} \in \mathbb{N}^k)

    f(0,x)=g(x)f(0, \mathbf{x}) = g(\mathbf{x})
    \,
    f(y+1,x)=h(y,f(y,x),x)f(y+1, \mathbf{x}) = h(y, f(y, \mathbf{x}), \mathbf{x})

    also belongs to 𝒞\mathcal{C};

  • is closed under minimization: given any total function f: k+1f: \mathbb{N}^{k+1} \to \mathbb{N} belonging to 𝒞\mathcal{C}, the partial function g: kg: \mathbb{N}^k \to \mathbb{N}, defined by g(x)=cg(\mathbf{x}) = c iff f(c,x)=0f(c, \mathbf{x}) = 0 and f(d,x)>0f(d, \mathbf{x}) \gt 0 whenever 0dc10 \leq d \leq c-1, also belongs to 𝒞\mathcal{C}.

Definition

A primitive recursive function is a function that belongs to the smallest class of functions of the form k\mathbb{N}^k \to \mathbb{N} that contains constants, projection maps, the successor map, is closed under composition, and is closed under primitive recursion.

Clearly the primitive recursive functions are a subclass of partial recursive functions. Notice that primitive recursive functions are not merely partial functions, but actual (total) functions.

Remark

Both the class of partial recursive functions and the class of primitive recursive functions yield Lawvere theories Th(Comp)Th(Comp) and Th(PrimRec)Th(PrimRec), where a morphism k1k \to 1 of the Lawvere theory is a function k 1\mathbb{N}^k \to \mathbb{N}^1 belonging to the class. It is straightforward to check that in either case, the generating object 11 of the Lawvere theory (or \mathbb{N} if you prefer) is a parametrized NNO in that category: this is the essence of primitive recursion.

Definition

A recursive relation (or what is more usual nowadays, a computable relation) is a subset of k\mathbb{N}^k whose characteristic function χ: k{0,1}\chi: \mathbb{N}^k \to \{0, 1\} is recursive. Similarly, a primitive recursive relation is a relation whose characteristic function is primitive recursive.

Properties

We may build up a stock of functions and relations that are primitive recursive as follows. (All closure properties mentioned will clearly also apply to partial recursive functions and relations.)

  1. Addition, multiplication, and exponentiation on \mathbb{N}. The factorial function nn!n \mapsto n! is primitive recursive. Binomial coefficients.

  2. The predecessor function Pred:Pred: \mathbb{N} \to \mathbb{N}, defined by the recursion Pred(0)=0Pred(0) = 0, Pred(n+1)=nPred(n+1) = n.

  3. Truncated subtraction, where xy=xyx \stackrel{\cdot}{-} y = x - y if xyx \geq y, else 00, is primitive recursive. It is defined by the recursion x0=xx \stackrel{\cdot}{-} 0 = x, x(y+1)=Pred(xy)x \stackrel{\cdot}{-} (y+1) = Pred(x \stackrel{\cdot}{-} y).

  4. The distance function |xy|=(xy)+(yx){|x-y|} = (x \stackrel{\cdot}{-} y) + (y \stackrel{\cdot}{-} x). The function α(x)=1x\alpha(x) = 1 \stackrel{\cdot}{-} x; this is the characteristic function of the unary relation or predicate “equals zero”. So “equals zero” is a computable relation. So is “doesn’t equal zero”, since this has characteristic function α(α(x))\alpha(\alpha(x)).

  5. Therefore the equality relation |xy|=0{|x-y|} = 0 is a primitive recursive relation. So is x<yx \lt y, being the relation “yxy \stackrel{\cdot}{-} x doesn’t equal zero”. If ff is a (primitive) recursive function, then its graph defined by the relation y=f(x)y = f(x) is a (primitive) recursive relation.

  6. (Boolean combinations) Similarly, if RR is a primitive recursive relation (so that its characteristic function χ R\chi_R is primitive recursive), then so is its negation ¬R\neg R, since χ ¬R=α(χ R)\chi_{\neg R} = \alpha(\chi_R). If PP, QQ are primitive recursive relations, so is PQP \wedge Q, since χ PQ=χ Pχ Q\chi_{P \wedge Q} = \chi_P \cdot \chi_Q. Hence Boolean combinations of primitive recursive relations are primitive recursive.

  7. If f(x,y,z)f(x, y, \mathbf{z}) and h(y)h(y) are primitive recursive, so is

    g(y,z) x=0 h(y)f(x,y,z)g(y, \mathbf{z}) \coloneqq \sum_{x=0}^{h(y)} f(x, y, \mathbf{z})

    and similarly with the sum replaced by a product. It follows that primitive recursive predicates are closed under bounded quantification; e.g., if R(x,y,z)R(x, y, \mathbf{z}) is a primitive recursive predicate and hh is a primitive recursive function, then the predicate QQ defined by

    Q(y,z)= 0x<yR(x,y,z) x=0 y1R(x,y,z)Q(y, \mathbf{z}) = \forall_{0 \leq x \lt y} R(x, y, \mathbf{z}) \coloneqq \bigwedge_{x=0}^{y-1} R(x, y, \mathbf{z})

    is primitive recursive since χ Q(y,z)= x=0 y1χ R(x,y,z)\chi_Q(y, \mathbf{z}) = \prod_{x=0}^{y-1} \chi_R(x, y, \mathbf{z}).

  8. (Bounded least choice operator) If R(x,y,z)R(x, y, \mathbf{z}) is a primitive recursive relation and hh is a primitive recursive function, then the function f(y,z)f(y, \mathbf{z}) defined to be “the least xh(y)x \leq h(y) such that R(x,y,z)R(x, y, \mathbf{z}) if such xx exists, else yy” is primitive recursive. Indeed,

    f(y,z)=[ x=0 h(y)(xχ R(x,y,z)( w=0 x1χ ¬R(w,y,z))]+y x=0 h(y)χ ¬R(x,y,z).f(y, \mathbf{z}) = [\sum_{x=0}^{h(y)} (x \cdot \chi_R(x, y, \mathbf{z}) \cdot (\prod_{w=0}^{x-1} \chi_{\neg R}(w, y, \mathbf{z}))] + y \cdot \prod_{x=0}^{h(y)} \chi_{\neg R}(x, y, \mathbf{z}).
  9. (Pairing and unpairing) There is an isomorphism 2\mathbb{N}^2 \to \mathbb{N} in the Lawvere theory Th(PrimRec)Th(PrimRec), i.e., there is a primitive recursive function f: 2f: \mathbb{N}^2 \to \mathbb{N} with a primitive recursive inverse g: 2g: \mathbb{N} \to \mathbb{N}^2. For example, take ff to be the function

    f:(m,n)(m+n+12)+nf: (m, n) \mapsto \binom{m+n+1}{2} + n

    Its inverse gg takes mm to the pair

    (a(m(a12)+2),m(a12))(a \stackrel{\cdot}{-} (m - \binom{a \stackrel{\cdot}{-} 1}{2}+2), m - \binom{a \stackrel{\cdot}{-} 1}{2})

    where aa is the least element less than m+2m+2 such that (a2)>m\binom{a}{2} \gt m. By the aforementioned properties, this gg is manifestly primitive recursive.

As a consequence of this last property, there exist primitive recursive isomorphisms between \mathbb{N} and k\mathbb{N}^k for any k>0k \gt 0. Since partial/primitive recursive functions are closed under composition, it is sufficient (and sometimes convenient) to consider only partial/primitive recursive functions on \mathbb{N} itself. (The exception is the case k=0k = 0, but this is trivial, since every partial function 11 \to \mathbb{N} is recursive.)

Remark

To show that 2\mathbb{N}^2 \cong \mathbb{N} in the category of primitive recursive functions, it is not enough just to exhibit a primitive recursive bijection f: 2f: \mathbb{N}^2 \to \mathbb{N}, because it is not true that every primitive recursive bijection possesses a primitive recursive inverse. In other words, it is not true that the forgetful functor Th(PrimRec)SetTh(PrimRec) \to Set (see Remark 1) reflects isomorphisms. See Example 1 below.

Remark

Similarly, it is not always true that if a graph of a function is a primitive recursive relation, then the function itself is primitive recursive. (For example, the graph of the Ackermann function, discussed below, is a primitive recursive relation.) However, we do have a sample theorem as follows.

Theorem

If a graph of a function ff is a primitive recursive relation, and if fgf \leq g for some primitive recursive gg, then ff is itself primitive recursive.

The proof can be roughly expressed as follows: if R(x,y)R(x, y) is the functional computable relation, then let f(x)f(x) be the least yg(x)y \leq g(x) such that R(x,y)R(x, y). The bounded least choice property shows that f(x)f(x) is primitive recursive.

The point hovering in the background is that there are some computable functions which grow faster (in fact, much much much faster) than any primitive recursive function. This underscores the important role of the minimization axiom for partial recursive functions, which allows unboundedly large searches to take place. Indeed, we have the following crucial fact:

Theorem

If RN 2R \subseteq{N}^2 is a graph of a function ff and is a recursive relation, then ff is a (total) recursive function. (The converse holds by one of the properties listed above.)

Proof

According to the minimization axiom in Definition 1, given that χ R: 2{0,1}\chi_R: \mathbb{N}^2 \to \{0, 1\} is a recursive function, the function that takes xx to the least yy \in \mathbb{N} such that 1χ R(x,y)=01 - \chi_R(x, y) = 0 is also recursive. But this function is simply ff. This completes the proof.

Corollary

The inverse of a recursive bijection ff is also recursive.

Proof

The graph of ff is a recursive relation, and so is the opposite graph, which is the graph of the function f 1f^{-1}. Apply the preceding theorem.

Before passing on to general recursive functions, it is good to have some idea of the scope of primitive recursive functions. Some examples:

  • The function f(n)=p nf(n) = p_n, the n thn^{th} prime, is primitive recursive.

The Ackermann function

Definition

For each nn, we define a function A n:A_n: \mathbb{N} \to \mathbb{N} by

  • A 0(m)=2mA_0(m) = 2 m;

  • A n+1(m)=(A n) m(1)A_{n+1}(m) = (A_n)^m(1)

where f mf^m denotes the composition of mm copies of ff. The Ackermann function A:A: \mathbb{N} \to \mathbb{N} is defined by A(m)=A m(m)A(m) = A_m(m).

(named after Wilhelm Ackermann)

We show that while each A nA_n is primitive recursive, the function AA grows faster than any primitive recursive function on \mathbb{N}, hence is not itself primitive recursive. It does however belong to the class of partial recursive functions.

By property 1 above, A 0A_0 is primitive recursive. Supposing that A nA_n is primitive recursive, ϕ=A n+1\phi = A_{n+1} is also primitive recursive because it satisfies the recursion ϕ(0)=1\phi(0) = 1, ϕ(m+1)=A n(ϕ(m))\phi(m+1) = A_n (\phi(m)).

By induction one may easily show A n(1)=2A_n(1) = 2 for all nn and A n(2)=4A_n(2) = 4 for all nn. We have A n+1(3)=A n(A n(A n(1)))=A n(A n(2))=A n(4)A_{n+1}(3) = A_n(A_n(A_n(1))) = A_n(A_n(2)) = A_n(4) for all nn. The function A 1A_1 gives n thn^{th} powers of 22, the function A 2A_2 gives tetrations (iterated exponentials stacked nn high) of 22, the function A 3A_3 gives iterated tetrations, and so on.

Some routine inductions establish the following facts:

  • For all nn, the function A nA_n is strictly increasing, and with the sole exception of A 0(0)=0A_0(0) = 0, we have m<A n(m)m \lt A_n(m) for all mm, i.e. A nA_n is strictly inflationary in arguments m>0m \gt 0. We also have n<A n(3)n \lt A_n(3) for all nn.
Lemma

If f: kf: \mathbb{N}^k \to \mathbb{N} is primitive recursive, then there exists nn such that f(x 1,,x k)A n(max{3,x 1,,x k})f(x_1, \ldots, x_k) \leq A_n(\max \{3, x_1, \ldots, x_k\}) for all x 1,,x kx_1, \ldots, x_k. (We say ff is dominated by A nA_n, for short.)

Proof

In the case where ff is constant with value mm, take n=mn=m. For ff the successor, use n=0n = 0. For each projection π i: k\pi_i: \mathbb{N}^k \to \mathbb{N}, again use n=0n = 0:

x i=π i(x 1,,x k)A 0(max{3,x 1,,x k}).x_i = \pi_i(x_1, \ldots, x_k) \leq A_0(\max \{3, x_1, \ldots, x_k\}).

Now proceed by induction on the construction of primitive recursive functions. Given that f: kf: \mathbb{N}^k is dominated by A nA_n and g 1,,g k: mg_1, \ldots, g_k: \mathbb{N}^m \to \mathbb{N} are dominated by A n+1A_{n+1}, we calculate that h=f(g 1,,g k): mh = f \circ (g_1, \ldots, g_k): \mathbb{N}^m \to \mathbb{N} is dominated by A n+2A_{n+2}:

h(x 1,,x m) = f(g 1(x 1,,x m),,g k(x 1,,x m)) A n(max{3,g 1(x 1,,x m),,g k(x 1,,x m)}) A n(A n+1(max{3,x 1,,x m})) = A n+1(max{3,x 1,,x m}+1) A n+2(max{3,x 1,,x m}).\array{ h(x_1, \ldots, x_m) & = & f(g_1(x_1, \ldots, x_m), \ldots, g_k(x_1, \ldots, x_m)) \\ & \leq & A_n(\max \{3, g_1(x_1, \dots, x_m), \ldots, g_k(x_1, \ldots, x_m)\}) \\ & \leq & A_n(A_{n+1}(\max\{3, x_1, \ldots, x_m\})) \\ & = & A_{n+1}(\max\{3, x_1, \ldots, x_m\} + 1) \\ & \leq & A_{n+2}(\max\{3, x_1, \ldots, x_m\}). }

And given that g: kg: \mathbb{N}^k \to \mathbb{N} is dominated by A n+1A_{n+1} and h: k+2h: \mathbb{N}^{k+2} \to \mathbb{N} is dominated by A nA_n, if we define f: k+1f: \mathbb{N}^{k+1} \to \mathbb{N} by recursion by f(0,x 1,,x k)=g(x 1,,x k)f(0, x_1, \ldots, x_k) = g(x_1, \ldots, x_k) and f(y+1,x 1,,x k)=h(y,f(y,x 1,,x k),x 1,,x k)f(y+1, x_1, \ldots, x_k) = h(y, f(y, x_1, \ldots, x_k), x_1, \ldots, x_k), we calculate that ff is dominated by A n+3A_{n+3}, in two steps. First we claim

f(y,x 1,,x k)A n+1(y+max{3,x 1,,x k}).f(y, x_1, \ldots, x_k) \leq A_{n+1}(y + \max\{3, x_1, \ldots, x_k\}).

Indeed, this is true by assumption for y=0y=0. And then

f(y+1,x 1,,x k) = h(y,f(y,x 1,,x k),x 1,,x k) A n(max{3,y,f(y,x 1,,x k),x 1,,x k)}) A n(max{3,y,A n+1(y+max{3,x 1,,x k}),x 1,,x k}) A n(A n+1(y+max{3,x 1,,x k})) = A n+1(y+1+max{3,x 1,,x k})\array{ f(y+1, x_1, \ldots, x_k) & = & h(y, f(y, x_1, \ldots, x_k), x_1, \ldots, x_k) \\ & \leq & A_n(\max\{3, y, f(y, x_1, \ldots, x_k), x_1, \ldots, x_k)\}) \\ & \leq & A_n(\max\{3, y, A_{n+1}(y + \max\{3, x_1, \ldots, x_k\}), x_1, \ldots, x_k\}) \\ & \leq & A_n(A_{n+1}(y + \max\{3, x_1, \ldots, x_k\})) \\ & = & A_{n+1}(y+1+\max\{3, x_1, \ldots, x_k\}) }

which justifies the claim. Finally, we have

f(y,x 1,,x k) A n+1(y+max{3,x 1,,x k}) A n+1(2max{3,y,x 1,,x k}) A n+1(A n+2(max{3,y,x 1,,x k})) = A n+2(max{3,y,x 1,,x k}+1) A n+3(max{y,x 1,,x k})\array{ f(y, x_1, \ldots, x_k) & \leq & A_{n+1}(y + \max\{3, x_1, \ldots, x_k\}) \\ & \leq & A_{n+1}(2\max\{3, y, x_1, \ldots, x_k\}) \\ & \leq & A_{n+1}(A_{n+2}(\max\{3, y, x_1, \ldots, x_k\})) \\ & = & A_{n+2}(\max\{3, y, x_1, \ldots, x_k\} + 1) \\ & \leq & A_{n+3}(\max\{y, x_1, \ldots, x_k\}) }

so that ff is dominated by A n+3A_{n+3}. This completes the proof.

Corollary

The Ackermann function AA is not primitive recursive.

Proof

If A:xA x(x)A: x \mapsto A_x(x) were recursive, then so would be the function ϕ:xA x(x)+1\phi: x \mapsto A_x(x) + 1. In that case, ϕ\phi is dominated by A nA_n for some n3n \geq 3. We then arrive at the contradiction

A n(n)+1=ϕ(n)A n(max{3,n})=A n(n).A_n(n) + 1 = \phi(n) \leq A_n(\max\{3, n\}) = A_n(n).
Proposition

The graph of the Ackermann function is a primitive recursive relation.

Proof

The rough idea is to let zz bound the search for solutions (x,y)(x, y) to A x(y)=zA_x(y) = z. For x,y>0x, y \gt 0 we have A x(y)=A x1(A x(y1))=A x(y)A_x(y) = A_{x-1}(A_x(y-1)) = A_x(y') where yA x(y1)y' \coloneqq A_x(y-1). We have y<A x1(y)=zy' \lt A_{x-1}(y') = z. Starting with y 0=y<zy_0 = y \lt z, iterate this procedure so that

z=A x(y 0)=A x1(y 1)=A x2(y 2)==A 0(y x)=2y xz = A_x(y_0) = A_{x-1}(y_1) = A_{x-2}(y_2) = \ldots = A_0(y_x) = 2 y_x

with each y iy_i less than zz. (Explicitly, the iteration is y i+1A xi(y i1)y_{i+1} \coloneqq A_{x-i}(y_i - 1).)

Thus, after disposing of some trivial low number cases, WLOG we may take z>4z \gt 4, where the ternary predicate

(z>4)(A x(y)=z)(z \gt 4) \wedge (A_x(y) = z)

is equivalent to

(x>0)(y>2)(x<z) y 0,y 1,y x<z(y=y 0)( i<xy i+1=A xi(y i1))(2y x=z)(x \gt 0) \wedge (y \gt 2) \wedge (x \lt z) \wedge \exists_{y_0, y_1, \ldots y_x \lt z} (y = y_0) \wedge (\forall_{i \lt x} y_{i+1} = A_{x-i}(y_i - 1)) \wedge (2 y_x = z)

where the quantifications are manifestly bounded by zz. This shows that the ternary predicate A x(y)=zA_x(y) = z is primitive recursive.

From this it follows that the binary relation A x(x)=zA_x(x) = z is also primitive recursive, as claimed.

Combining this result with Theorem 2, we have

Corollary

The Ackermann function A:xA x(x)A: x \mapsto A_x(x) is recursive.

Example

Here we exhibit a primitive recursive bijection whose inverse is not primitive recursive. The graph y=A x(x)y = A_x(x) of the Ackermann function is primitive recursive binary predicate, and the image I={y: xy=A x(x)}I = \{y: \exists_x y = A_x(x)\} is a primitive recursive unary predicate, because the existential quantifier is a bounded quantifier applied to a primitive recursive relation:

I= x=0 y1[A x(x)=y].I = \bigvee_{x=0}^{y-1} [A_x(x) = y].

Observe that both II and its complement ¬I\neg I in \mathbb{N} are infinite.

For any infinite set JJ \subseteq \mathbb{N}, let p J:p_J: \mathbb{N} \to \mathbb{N} be the function taking nn to the n thn^{th} element of JJ (with respect to the usual order <\lt). For example, p I(x)=A x(x)p_I(x) = A_x(x). Now define a function f:f: \mathbb{N} \to \mathbb{N} by

f(m) = 2p I 1(m) ifmI = 2p ¬I 1(m)+1 ifm¬I\array{ f(m) & = & 2p_I^{-1}(m) & \text{if} \; m \in I \\ & = & 2p_{\neg I}^{-1}(m) + 1 & \text{if} \; m \in \neg I }

Then f(m)2m+1f(m) \leq 2m + 1 and the graph of ff is primitive recursive, so by Theorem 1, ff is a primitive recursive function. It is a bijection by construction. But f 1f^{-1} is not primitive recursive, because f 1(2x)=p I(x)=A(x)f^{-1}(2x) = p_I(x) = A(x), and AA is not primitive recursive.

Busy Beaver function

computability

type I computabilitytype II computability
typical domainnatural numbers \mathbb{N}Baire space of infinite sequences 𝔹= \mathbb{B} = \mathbb{N}^{\mathbb{N}}
computable functionspartial recursive functioncomputable function (analysis)
type of computable mathematicsrecursive mathematicscomputable analysis, Type Two Theory of Effectivity
type of realizabilitynumber realizabilityfunction realizability
partial combinatory algebraKleene's first partial combinatory algebraKleene's second partial combinatory algebra

References

A standard textbook in recursive functions is

  • Hartley Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, 1967.

Quite a bit of the arrangement and proofs above were taken from clear and useful lecture notes of Stephen Simpson,

  • Stephen G. Simpson, Foundations of Mathematics (Lecture Notes), October 1, 2009. (pdf)

Of course, there is always good old Wikipedia:

Last revised on December 9, 2017 at 11:39:49. See the history of this page for a list of all contributions to it.