Primitive Recursion

computation

Definition

Primitive Recursion

Primitive recursion is a function schema that defines $f:{\mathbb{N}}^{k+1}\to \mathbb{N}$ from a base function $g:{\mathbb{N}}^k\to \mathbb{N}$ and a step function $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$.

$$\begin{array}{rl}f& =\mathbf{Pr}(g,h)\\ f(0,x_1,\dots ,x_k)& =g(x_1,\dots ,x_k)\\ f(m+1,x_1,\dots ,x_k)& =h(m,f(m,x_1,\dots ,x_k),x_1,\dots ,x_k)\end{array}$$

The recursion is over the first argument.

Base Functions

Constant Function

Definition

Constant Function (Recursion)

$$C_n^k:C_n^k(x_1,\dots ,x_k)=n$$

Examples:

• $C_2^1=2$
• $C_0^3=0$

Link to original

Successor Function

Definition

Successor Function (Recursion)

$$S:S(x)=x+1$$

Examples:

• $S\equiv [f(x)=x+1]$
• $(S,C_2^1)\equiv \left[f(x)=(x+1,2)\right]$

Link to original

Projection Function

Definition

Projection Function (Recursion)

$$P_i^k:P_i^k(x_1,\dots ,x_k)=x_i(1\le i\le k)$$

Examples:

• $P_1^3\equiv [f(x,y,z)=x]$
• $(P_2^2,P_1^2)\equiv [f(x,y)=(y,x)]$

Link to original

Arithmetic Functions

Addition

We can define addition recursively as:

$$\begin{array}{rl}\text{Add}(0,n)& =n(\text{base})\\ \text{Add}(S(m),n)& =S(\text{Add}(m,n))(\text{transition})\end{array}$$

We observe that the definition recurses over the first argument of $\text{Add}$. Thus, we can define addition via the recursion operator as:

$$\text{Add}=\mathbf{Pr}(P_1^1,S\circ P_2^3)$$

$0+5$, $1+5$, $2+5$, $\dots$

$$\begin{array}{rlrl}\text{Add}(0,5)& =P_1^1(5)& & =5\\ \text{Add}(0+1,5)& =(S\circ P_2^3)(0,\text{Add}(0,1),5)& & =6\\ \text{Add(1+1, 5)}& =(S\circ P_2^3)(1,\text{Add(1, 5)},5)& & =7\\ \text{Add(2+1, 5)}& =(S\circ P_2^3)(2,\text{Add(2, 5)},5)& & =8\\ ⋮& & & \end{array}$$

Multiplication

We can define multiplication recursively as:

$$\begin{array}{rl}\text{Mult}(0,n)& =0(\text{base})\\ \text{Mult}(S(m),n)& =\text{Add}(n,\text{Mult}(m,n))(\text{transition})\end{array}$$

We observe that the definition recurses over the first argument of $\text{Mult}$. Thus, we can define multiplication via the recursion operator as:

$$\text{Mult}=\mathbf{Pr}(C_0^1,\text{Add}\circ (P_2^3,P_3^3))$$

Intuition

Here, we have a function $\text{Mult}$ with two parameters:

1. the parameter $m$ to be recursed over
2. the parameter $n$ to be repeatedly added $m$ times.

If $M(0,n)$, then $\forall n:0=C_0^1$. We select $1$ as arity given that $\text{Mult}$ only has one non-recursion parameter (the second one; $n$).

If $\text{Mult}(m+1,n)$, we have to add the quantity $n$ to the previous iteration $\text{Mult}(m,n)$, where:

• $P_2^3$ is the previous result, i.e. $\text{Mult}(m,n)$, and
• $P_3^3$ is the parameter $n$ (the only non-recursive one)
  Together, we add:

$$\text{Add}\circ (P_2^3,P_3^3)\widehat{=}\text{Add}\circ (\text{previous iteration},\text{n})$$

Factorial

We can define factorial recursively as:

$$\begin{array}{rl}\text{Fact}(0)& =1(\text{base})\\ \text{Fact}(S(m))& =\text{Mult}(S(m),\text{Fact}(m))(\text{transition})\end{array}$$

We observe that the definition recurses over the first argument of $\text{Fact}$. Thus, we can define multiplication via the recursion operator as:

$$\text{Fact}=\mathbf{Pr}(C_1^0,\text{Mult}\circ (P_2^2,S\circ P_1^2))$$

Signum

$$\text{Signum}=\mathbf{Pr}(C_0^0,C_0^2)$$

Truncated Predecessor Function

The truncate predecessor function, i.e. the predecessor function for $n>0$, can be defined as:

$$\text{TPred}=\mathbf{Pr}(C_0^0,P_2^1)$$

Truncated Subtraction

Let $\text{TSub}$ be the truncated subtraction defined as:

$$\text{TSub}(m,n)=\{\begin{array}{ll}m-n& \text{if }m\ge n\\ 0& \text{else}\end{array}$$

Then, we can define it using the primitive recursion operator as follows:

$$\text{TSub}=\mathbf{Pr}(P_1^1,\text{TPred}\circ P_2^3)\circ \underset{(m,n)\to (n,m)}{\underbrace{(P_2^2,P_1^2)}}$$

Negation

We can define $\text{Not}(x)=1-x\forall x\in \{0,1\}$ as:

$$\text{Not}=\text{TSub}\circ (C_1^1,P_1^1)$$

Conjunction

We can define $\text{AND}(m,n)=m\cdot n$ as:

$$\text{AND}=\text{Mult}$$

Disjunction

$$\text{OR}=\text{Signum}\circ \text{Add}$$

Less Than

$$\text{Less}=\text{Signum}\circ \text{TSub}\circ (P_2^2,P_1^2)$$

Computability

Primitive-recursive functions are computable and total. However, not every computable total function is primitive-recursive.

We can list all primitive-recursive functions as $F_0,F_1,F_2,\dots$. This gives the following table:

$n$	$F_0$	$F_1$	$F_2$	$F_3$	$\dots$
$0$	$F_0(0)$	$F_1(0)$	$F_2(0)$	$F_3(0)$	$\dots$
$1$	$F_0(1)$	$F_1(1)$	$F_2(1)$	$F_3(1)$	$\dots$
$2$	$F_0(2)$	$F_1(2)$	$F_2(2)$	$F_3(2)$	$\dots$
$3$	$F_0(3)$	$F_1(3)$	$F_2(3)$	$F_3(3)$	$\dots$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$\ddots$

Then the diagonal function

$$D(n)=F_n(n)+1$$

is computable and total.

For any fixed $i$, compare $D$ with $F_i$ at input $i$:

$$D(i)=F_i(i)+1$$

The output of $D$ is exactly one larger than the output of $F_i$ at that input. Therefore, $D(i)\ne F_i(i)$. Since equal functions must agree on every input, $D\ne F_i$. This holds for every $i$, so $D$ is not primitive-recursive.

Not all total computable functions are primitive-recursive

Not all computable total functions are primitive-recursive.

Ackermann function

The Ackermann function is computable and total, but not primitive-recursive.

Guaranteed termination forces incompleteness

There is no programming language in which every program terminates and in which every total computable function is expressible.

Examples

Examples: Using Base Functions

Example

$$\begin{array}{rl}S\circ P_2^2& \equiv x_1,x_2\mapsto S(P_2^2(x_1,x_2))\\ & \equiv x_1,x_2\mapsto S(x_2)\\ & \equiv x_1,x_2\mapsto x_2+1\end{array}$$

Example

$$\begin{array}{rl}S\circ S\circ S& \equiv x_1\mapsto S(S(S(x_1)))\\ & \equiv x_1\mapsto S(S(x_1+1))\\ & \equiv x_1\mapsto S(x_1+2)\\ & \equiv x_1\mapsto x_1+3\end{array}$$

Example

$$\begin{array}{rl}{P}_2^2\circ (C_1^1,S)& \equiv x_1\mapsto P_2^2(C_1^1(x_1),S(x_1))\\ & \equiv x_1\mapsto P_2^2(1,x_1+1)\\ & \equiv x_1\mapsto x_1+1\end{array}$$

Example

$$\begin{array}{rl}{C}_0^1\circ S& \equiv x_1\mapsto C_0^1(S(x_1))\\ & \equiv x_1\mapsto C_0^1(x_1+1)\\ & \equiv x_1\mapsto 0\end{array}$$

Example

$$\begin{array}{rl}S\circ S\circ C_0^0& \equiv \mapsto S(S(C_0^0))\\ & \equiv \mapsto S(S(0))\\ & \equiv \mapsto S(1)\\ & \equiv \mapsto 2\end{array}$$

Example

$$\begin{array}{rl}S\circ C_0^1& \equiv x_1\mapsto S(C_0^1(x_1))\\ & \equiv x_1\mapsto S(0)\\ & \equiv x_1\mapsto 1\end{array}$$

$E(m,n)=(n+6{)}^{2m+1}$

We want to find an equivalent $\mathbf{Pr}$-expression for:

$$E(m,n)=(n+6{)}^{2m+1}$$

First, we want to represent $E(m,n)$ recursively:

$$\begin{array}{rl}E(0,n)& =n+6\\ E(1,n)& =(n+6{)}^3\\ E(2,n)& =(n+6{)}^5\\ ⋮& \\ E(m+1,n)& =E(m,n)\cdot (n+6{)}^2\end{array}$$

Now, it’s easier to write $E(m,n)$ as $\mathbf{Pr}$-expresion:

$$E=\mathbf{Pr}(\underset{n+6}{\underbrace{P_1^1}},\underset{E(m,n)\cdot (n+6{)}^2}{\underbrace{\text{Mult}\circ (\underset{E(m,n)}{\underbrace{P_2^3}},\underset{(n+6{)}^2}{\underbrace{\text{Mult}\circ (\underset{n+6}{\underbrace{P_3^3}},\underset{n+6}{\underbrace{P_3^3}})}})}})\circ (\underset{m}{\underbrace{P_1^2}},\underset{n+6}{\underbrace{\text{Add}\circ (P_2^2,C_6^2)}})$$

The above immediately increments $n\mapsto n+6$, as the $E(m,n)$ never uses $n$ alone and uses $n+6$ multiple times in the recursive definition.