(Notes from Chapter 3, Sections 1 - 3)

Composition

Let \[h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_k(x_1,\ldots,x_n))\] where \(f:\mathbb{N}^k \rightarrow \mathbb{N}\) and \(g_1,\ldots,g_k:\mathbb{N}^n\rightarrow \mathbb{N}\). Then \(h\) is said to be obtained from \(f\) and \(g_1,\ldots,g_k\) by composition.

Theorem 1.1. If \(h\) is obtained from the (partially) computable functions \(f,g_1,\ldots,g_k\) by composition, then \(h\) is (partially) computable.

Proof. The following program (note the use of macros) computes \(h\): \begin{eqnarray*} Z_1 & \leftarrow & g_1(X_1,\ldots,X_n) \\ & \vdots & \\ Z_k & \leftarrow & g_k(X_1,\ldots,X_n) \\ Y & \leftarrow & f(Z_1,\ldots,Z_k) \end{eqnarray*}

Clearly, \(h\) is total if \(f,g_1,\ldots, g_k\) are total.

Recursion

Let \(h:\mathbb{N}^{n+1}\) be defined by \begin{eqnarray*} h(x_1,\ldots,x_n, 0) & = & f(x_1,\ldots,x_n) \\ h(x_1,\ldots,x_n, t+1) & = & g(x_1,\ldots, x_n, t, h(x_1,\ldots,x_n,t)) \end{eqnarray*} where \(f:\mathbb{N}^n\rightarrow \mathbb{N}\) and \(g:\mathbb{N}^{n+2}\rightarrow \mathbb{N}\) are total. Then \(h\) is said to be obtained from \(f\) and \(g\) by primitive recursion (or simply, recursion).

Theorem 2.2. If \(h\) is obtained from \(f\) and \(g\) as above, then \(h\) is computable.

\[ \begin{array}{ll} & Y \leftarrow f(X_1,\ldots,X_n) \\ [A] & \textbf{if } X_{n+1} = 0 \textbf{ goto } E \\ & Y \leftarrow g(X_1,\ldots,X_n, Z, Y) \\ & Z \leftarrow Z+ 1\\ & X_{n+1} \leftarrow X_{n+1} ~\dot{-}~ 1\\ & \textbf{goto } A \end{array} \]

Clearly, \(h\) is total if \(f,g_1,\ldots, g_k\) are total.

Remark. The requirement that \(f\) and \(g\) be total functions in the definition of primitive recursive will eventually be dropped. Clearly, if \(f\) or \(g\) are not total functions, \(h\) is not necessarily total. Under this more general definition of primitive recursion, the proof of Theorem 2.2 still shows that if \(h\) is obtained from \(f\) and \(g\) by primitive recursion, then \(h\) is partially computable.

PRC classes

Recall that the initial functions we have introduced are: \begin{eqnarray*} \operatorname{n}(x_1,\ldots,x_n) & = & 0 ~~~ n \in \mathbb{N}\\ s(x) & = & x+1 \\ u_i^n(x_1,\ldots,x_n) & = & x_i~~~(1\leq i \leq n) \end{eqnarray*}

A class of total functions \({\cal C}\) is called a PRC class if

1. the initial functions belong to \({\cal C}\),

2. a function obtained from functions belonging to \({\cal C}\) by either composition or recursion also belongs to \({\cal C}\).

In other words, a PRC class contains the initial functions and is closed under composition and recursion.

Theorem 3.1. The class of computable functions is a PRC class.

Proof. One only needs to prove that the initial functions are computable.

Primitive recursive functions

A function is called primitive recursive if it can be obtained from the initial functions by a finite number of applications of composition and recursion.

Corollary 3.2. The class of primitive recursive functions is a PRC class.

Corollary 3.4. Every primitive recursive function is computable.

Proof. Follows from Theorems 3.1 and 3.3.