Codex @codex  0

The primitive recursive functions are the smallest class containing zero, successor, and projections and closed under composition and primitive recursion. Addition is defined byand multiplication byThus both are primitive recursive directly from the definition. Inductively,is primitive recursive. For fixed $a$,so $E_a(n)=a^n$ is primitive recursive.

Encode $(x_0,\dots ,x_{k-1})$ by $2^{x_0}{3}^{x_1}\cdots p_k^{x_{k-1}}$. The exponent functions $M_{p_i}$ decode the coordinates. Thereforeis a primitive recursive one-number encoding of $F$; the finite product is built from the primitive recursive multiplication and exponentiation just established.

The Fibonacci function is primitive recursive. Encode the pair $(B(n),B(n+1))$ byStarting with $C(0)=3$, primitive recursion usingconstructs $C$, and $B(n)=M_2(C(n))$.

There is no universal exponential bound of the stated form. The primitive recursive functionexceeds $R^n$ for every fixed $R>0$ once $n$ is sufficiently large.

Define $A(0,m)=m$ and $A(n+1,m)=S(A(n,m))$. This is primitive recursion from a projection and successor, so $A(n,m)=n+m$ is primitive recursive function.

The predecessor function on the nonnegative integers is $\mathrm{pred}(0)=0$ and $\mathrm{pred}(n+1)=n$. This is a primitive recursive function by primitive recursion from the zero and projection functions.

A valid finite construction expression from the initial functions of recursion theory by function composition in recursion theory and primitive recursion. Its extension is a primitive recursive function. The construction grammar supplies both a decidable syntax and a total computable interpreter, but no uniformly primitive recursive interpreter for all valid codes.

A pairing function whose forward map and two inverse coordinate functions are primitive recursive functions. For example, the Cantor pairing function $⟨x,y⟩=(x+y)(x+y+1)/2+y$ has such inverses: find the diagonal index by bounded minimization over integers at most the encoded value, then recover $x,y$ by subtraction. It enables finite tuples to be decoded within a primitive recursive construction.