Primitive Recursive and Partial Computable Functions

Addition is obtained by primitive recursion from the clauses $\mathrm{add}(0,n)=n$ and $\mathrm{add}(m+1,n)=S(\mathrm{add}(m,n))$. Multiplication is then obtained by primitive recursion from $0$ and addition via $\mathrm{mul}(0,n)=0$ and $\mathrm{mul}(m+1,n)=\mathrm{add}(\mathrm{mul}(m,n),n)$. By [L1], both functions are primitive recursive.

The predecessor function is primitive recursive from $p(0)=0$ and $p(n+1)=P_1^2(n,p(n))$. Then truncated subtraction is primitive recursive by and . From this, the zero-test ${\chi }_0$ is primitive recursive via ${\chi }_0(0)=1$ and ${\chi }_0(n+1)=0$, the sign function $\mathrm{sg}(n)=1-{\chi }_0(n)$ is primitive recursive, equality is given by , and order is given by . So the listed basic arithmetic and characteristic functions are primitive recursive by [L1].

If $g:{\mathbb{N}}^{k+1}\to \mathbb{N}$ is primitive recursive, then bounded sums and products are obtained by primitive recursion through ${\mathrm{\Sigma }}_g(0,x)=g(0,x)$, ${\mathrm{\Sigma }}_g(n+1,x)={\mathrm{\Sigma }}_g(n,x)+g(n+1,x)$, ${\mathrm{\Pi }}_g(0,x)=g(0,x)$, and ${\mathrm{\Pi }}_g(n+1,x)={\mathrm{\Pi }}_g(n,x)\cdot g(n+1,x)$. Hence ${\mathrm{\Sigma }}_g$ and ${\mathrm{\Pi }}_g$ are primitive recursive by [L1].

If $r(y,x)\in \{0,1\}$ is a primitive-recursive characteristic function, then ${\chi }_{\mathrm{\exists }y\le nr(y,x)=1}(n,x)=\mathrm{sg}({\mathrm{\Sigma }}_r(n,x))$ and ${\chi }_{\mathrm{\forall }y\le nr(y,x)=1}(n,x)={\mathrm{\Pi }}_r(n,x)$. Thus bounded existential and bounded universal quantification preserve primitive recursiveness.

The displayed constructions establish every operation and quantifier listed in the statement.

By bounded search on quotients and remainders, one can primitive-recursively recover the binary length of a positive integer and each individual bit of its canonical binary numeral. Using [L2], a bounded scan first reads the sentinel and unary header, obtaining a candidate $k$. It then parses exactly $k$ self-delimiting blocks, checks that each payload is a canonical binary numeral, and verifies that the final block ends at the end of the numeral. Only if all these checks succeed does it return $k$; otherwise it returns $0$. All scan bounds are at most the binary length of $s$, so this full validity test and the total function $\mathrm{len}$ are primitive recursive by [L1].

Once $\mathrm{len}(s)=k$ is known, the start and end of the $i$th block $c(\mathrm{bin}(a_i))$ are found by another bounded scan through the same binary numeral: each block begins with a run of $1$'s whose length is the bit-length of $a_i$, followed by one delimiter $0$, followed by exactly that many payload bits. The integer represented by that payload is then recovered by a bounded primitive-recursive evaluation of binary place values.

If the bounded scan shows that $i\ge \mathrm{len}(s)$ or that the numeral of $s$ is not of the required form, define the output to be $0$. Otherwise return the value decoded in step 2.1. Because every search range is bounded by the bit-length of $s$, the total function $\mathrm{entry}(s,i)$ is primitive recursive by [L1].

Steps 1.1 and 3.1 prove that both the length function and the total coordinate-reading function are primitive recursive.

A deterministic machine can evaluate $A(m,n)$ by keeping a finite stack of pending calls. Start with the one stack entry $(m,n)$. If the top entry is $(0,r)$, replace it by the value $r+1$; if it is $(p+1,0)$, replace it by $(p,1)$; and if it is $(p+1,r+1)$, replace it by the two pending calls $(p+1,r)$ and then $(p,\mathrm{\square })$, where the second frame waits for the value returned by the first and then substitutes it into $A(p,\cdot )$. Every individual rewrite is effective on a coded stack, so by [L2] this gives a machine procedure for evaluating $A$.

For each primitive recursive $k$-ary function $f$, structural induction on its construction from [L1] gives constants $c,r$ such that $f(x_1,\dots ,x_k)\le A_c({\max }_i{x}_i+r)$ for all inputs. The initial functions satisfy such a bound. For composition, apply the induction bounds to all inner functions, take their maximum, and then apply the bound for the outer function; monotonicity and the absorption property in [F1] replace the resulting finite composition by one higher fixed row. For primitive recursion, the recursion variable bounds the number of successive applications of the step function; [F1] again absorbs those boundedly many lower-row iterations into a higher fixed row.

The defining recursion decreases the left argument whenever the right argument is reset, and otherwise decreases the right argument before the left argument is used again. Induction on $m$ and then on $n$ therefore shows that every call chain eventually reaches the base clause $A(0,r)=r+1$. Hence the machine from step 1.1 halts on every input $(m,n)$, so $A$ is total computable.

If $A$ itself were primitive recursive, step 1.2 would give fixed $c,r$ with $A(m,n)\le A_c(\max \{m,n\}+r)$ for all $m,n$. Setting $m=n$ and then taking $n>c$ sufficiently large gives $A(n,n)>A_c(n+r)$ by [F1], contradicting that bound. Therefore $A$ is not primitive recursive.

Steps 2.1 and 2.2 prove that Ackermann's function is total computable but not primitive recursive.

By the configuration-code definition in the statement and [L3], primitive recursive functions recover from $c$ the decoded length of the tuple, its first two entries $q,h$, the currently scanned symbol $t(h)$, and any later tape symbol that may need to be copied into the output code.

Using the explicit tuple format from [L1], together with the primitive-recursive arithmetic and bounded searches from [L4], one can scan the canonical binary numeral of $e$: count the initial unary arity header, locate each self-delimiting block, verify the tuple-length and alphabet constraints, and recover the first three numerals and every transition-table coordinate, returning the default branch on malformed inputs. A bounded search through the recovered transition list therefore finds the unique transition triple $(q^{\mathrm{\prime }},b,D)$ attached to the pair $(q,t(h))$ when $q$ is nonhalting. Using [L2] and the decoded tape coordinates from step 1.1, form the updated tape, state, and head position $h^{\mathrm{\prime }}$. Then use a bounded backward search through positions at most $r+1$ to find the rightmost nonblank updated cell, taking $0$ if none exists, and set $r^{\mathrm{\prime }}$ to the maximum of that position and $h^{\mathrm{\prime }}$. The output tuple is exactly $(q^{\mathrm{\prime }},h^{\mathrm{\prime }},t^{\mathrm{\prime }}(0),\dots ,t^{\mathrm{\prime }}(r^{\mathrm{\prime }}))$, so erasing the former rightmost nonblank cell trims the trailing blank while a head move onto a blank cell still records the head position.

If the decoded state $q$ is already accepting or rejecting, step 2.1 is skipped and the output is the original code $c$. If the input code is malformed, return one fixed default code. These are again primitive-recursive case distinctions because the relevant checks are bounded and finite.

Re-encoding the canonically trimmed updated sequence from step 2.1 uses only primitive-recursive arithmetic on its boundedly many coordinates, so the total function $\mathrm{Step}(e,c)$ is primitive recursive and has the stated behavior.

By [L1], the function $f$ is presented by a finite derivation from the initial functions using composition, primitive recursion, and minimization. Build a machine for that derivation by structural induction. The zero, successor, and projection functions have immediate machines. For composition, run the machines for the inner functions in sequence and feed their outputs to the outer machine; divergence of any required subcomputation propagates. For primitive recursion, store the parameters and previous value and iterate the step machine from $0$ to the recursion argument. For minimization, evaluate the search function at $0,1,2,\dots$ in order and halt at the first zero; if an earlier required value is undefined, the machine diverges as prescribed by partial minimization. Since the derivation is finite, this yields one machine code $e$ computing $f$.

For this fixed code $e$, the predicate from [L2] recognizes exactly the coded halting histories of that machine. Therefore, if $f(x)=y$, there is at least one code $s$ with $T(e,x,s)$, and every such successful history has halting output $y$, so $U(s)=y$. If the minimization search never finds a zero or some earlier subcomputation diverges, then the machine has no halting history on $x$, so there is no $s$ with $T(e,x,s)$.

In the defined case, the least successful history code $\mu s{\tau }_T(e,x,s)$ exists, and step 2.1 gives $f(x)=U(\mu s{\tau }_T(e,x,s))$. In the undefined case, step 2.1 gives the second clause of the statement.

Assume first that $f$ is partial recursive. By [L3], choose $e$ with $f(x)=U(\mu s{\tau }_T(e,x,s))$ whenever $f(x)$ is defined. Every primitive-recursive function is Turing computable: the initial functions have immediate machines, machine composition realizes composition, and a finite loop realizes primitive recursion. Hence machines compute the primitive-recursive functions ${\tau }_T$ and $U$ from [L5]. A machine can therefore search successively through $s=0,1,2,\dots$, evaluate ${\tau }_T(e,x,s)$, and at the first zero compute $U(s)$ and halt with its binary numeral. If there is no successful $s$, the search continues forever. By [L1], this machine computes $f$.

Conversely, assume that $f$ is Turing computable. Then by [L1] there is a machine code $e$ whose halting computations on input $x$ produce exactly the values of $f(x)$. By [L5], the characteristic function of the relation $T(e,x,s)$ is primitive recursive, so the total search function $g_e(x,s)$ that returns $0$ exactly when $T(e,x,s)$ holds and $1$ otherwise is primitive recursive. By [L2], the partial search $m_e(x):=\mu s{g}_e(x,s)$ is therefore partial recursive, and composing with the primitive recursive output map $U$ shows that $x\mapsto U(m_e(x))$ is partial recursive as well. Its domain and values agree with $f$ because $m_e(x)$ exists exactly when the machine coded by $e$ has a halting history on $x$, and then [L5] says that $U(m_e(x))$ is exactly the machine's output. Hence $f$ is partial recursive.

Steps 1.1 and 1.2 prove both implications, so $f$ is partial recursive if and only if it is Turing computable.

Assume $f$ is partial recursive. By [L2], it is built from the initial arithmetic functions by composition, primitive recursion, and minimization. The initial functions are represented by the standard lambda terms for zero, successor, and projections; composition is represented by term substitution; primitive recursion is represented by the usual iterator on Church numerals; and minimization is represented by a fixpoint term that performs the unbounded search $y=0,1,2,\dots$ until a zero-test succeeds. Hence some lambda term represents $f$ in the sense of [L1].

Conversely, assume $f$ is lambda-definable. By [L1], there is a lambda term $F$ such that $F\overline{n_1}\cdots \overline{n_k}$ reaches a Church numeral exactly on the tuples where $f$ is defined, and the numeral reached is its value. Given the sequence code of $(n_1,\dots ,n_k)$, a Turing machine uses [L4] to recover the coordinates, forms that application, and performs a breadth-first search through all finite beta-reduction sequences, halting when a branch reaches a Church numeral. This computes the unary coded version of $f$, so [L3] makes that coded function partial recursive. Composing with the primitive-recursive tuple coder from [L5] and coordinate readers from [L4] makes the original $k$-ary $f$ partial recursive.

Steps 1.1 and 1.2 prove both directions, so lambda-definability and partial recursiveness are equivalent for $f$.

By [L1], the Ackermann function $A$ is a total computable function on ${\mathbb{N}}^2$, so it is directly an instance of the universal claim [A1].

The same fact [L1] states that $A$ is not primitive recursive. This contradicts [A1].

Take the total computable function $g(x,y)=1$ for all $x,y\in \mathbb{N}$. For this $g$, there is no $y$ with $g(x,y)=0$ for any input $x$.

By [L1], the minimization $\mu yg(x,y)$ is therefore undefined for every $x$. In particular it is not total, contradicting [A1].