Primitive Recursion

computation

Definition

Primitive Recursion

Let $g:{\mathbb{N}}^k\to \mathbb{N}$ and $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$ with $k\ge 0$. Then:

$$f=\mathbf{Pr}(g,h):{\mathbb{N}}^{k+1}\to \mathbb{N}$$

is defined by a base case:

$$f(0,x_1,\dots ,x_k)=g(x_1,\dots ,x_k)$$

and a step:

$$f(m+1,x_1,\dots ,x_k)=h(m,f(m,x_1,\dots ,x_k),x_1,\dots ,x_k)$$

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

Examples

Addition

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

Examples

$$\begin{array}{rl}Add(0,n)& =P_1^1(n)=n\end{array}$$

Multiplication

$$\begin{array}{rl}Mul& =\mathbf{Pr}(C_0^1,Add\circ (P_2^3,P_3^3))\\ & =\mathbf{Pr}(C_0^1,\mathbf{Pr}(P_1^1,S\circ P_2^3)\circ (P_2^3,P_3^3))\end{array}$$

Factorial

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

Signum

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

Truncated Predecessor Function

$$APred=\mathbf{Pr}(C_0^0,P_1^2)$$

Truncated Subtraction

$$\begin{array}{rl}ASub& =\mathbf{Pr}(P_1^1,APred\circ P_2^3)\circ (P_2^2,P_1^2)\\ ASub(m,n)& =\{\begin{array}{ll}m-n& \text{if }m\ge n\\ 0& \text{else}\end{array}\end{array}$$

Negation

$$Not=ASub\circ (C_1^1,P_1^1)$$

Conjunction

$$And=Mul$$

Disjunction

$$Or=Signum\circ Add$$

Less Than

$$less=Signum\circ ASub\circ (P_2^2,P_1^2)$$