Consider the Fibonacci numbers defined by \begin{eqnarray*} F_0 & = & 0 \\ F_1 & = & 1 \\ F_{n+1} & = & F_{n} + F_{n-1} ~~~\text{for } n \geq 1. \end{eqnarray*} Is there a primitive recursive function \(f\) such that \(f(n) = F_n\)? Notice that in the definition of the Fibonacci numbers, \(F_{n+1}\) depends on the previous two Fibonacci numbers. Thus, the recursive definition schemata that we have seen so far are insufficient for defining \(f\). In effect, we need a way to “remember” previously computed values. We will now look at one way to encode lists of numbers and define primitive recursive functions that need to access any previously computed values.
There are many ways to encode a list of natural numbers as a single natural number. The following discussion uses the one given in Proofs and Algorithms by Gilles Dowek. Later on, we will use the one described in the textbook.
We will be looking at lists encoded via the pairing function \(;\) given by \[x;y = \frac{(x+y)(x+y+1)}{2} + x + 1.\] It is not difficult to show that the function \(;\) is a bijection from \(\mathbb{N}^2\) to \(\mathbb{N}\backslash \{0\}\), the set of positive natural numbers.
Using this function, a list of natural numbers \(x_1,x_2,\ldots,x_n\) is encoded as \[x_1; (x_2; (\ldots; (x_n; 0)\ldots)).\] For example, the list \(3,1,0\) is encoded as \(3 ; (1 ; (0;0)) = 3; (1; 1) = 3; 5 = 40\). We call the number \(40\) the index of the list \(3,1,0\) and is denoted \([3,1,0]\). The index of the empty list, denoted [], is defined to be 0.
For indices of lists to be useful, we need a way to extract the list elements. We can do this with the head and tail functions defined, respectively, as: \[ hd(l) = \min_{x \leq l} (\exists y)_{\leq l} Eq(x;y = l)\] \[ tl(l) = \min_{y \leq l} Eq(hd(x);y = l)\]
We now define the \(sub\) function which takes the index of a list and a natural number \(n\) and returns the index of the list with the first \(n\) elements removed: \begin{eqnarray*} sub(l,0) & = & l \\ sub(l,n+1) & = & tl(sub(l,n)) \end{eqnarray*}
Then the \(n\)th element of the list with index \(l\) is given by \(hd(sub(l,n))\). So we define the function \[nth(l,n) = hd(sub(l,n)).\]
It is easy to show that the index of a list is at least the length of the list. Hence, the length of the list with index \(l\), denoted \(len(l)\) can be defined as: \[ len(l) = \min_{n \leq l} Eq(sub(l,n) = 0). \]
With these functions, we can now define a primitive recursive function \(f\) such that \(f(n) = F_n\).
We first define an auxiliary function: \begin{eqnarray*} g(0) & = & 0;0 \\ g(n+1) & = & \textbf{if } Eq(n,0) \textbf{ then } 1 \\ & & \textbf{else } g(n);(nth(g(n),n) + nth((g(n),n-1)) \end{eqnarray*} It is not difficult to show that \(g(n) = [F_0, F_1, \ldots, F_n]\).
Setting \(f(n) = nth(g(n),n)\), we get \(f(n) = F_n\).
The following schema defines a primitive recursive function: \begin{eqnarray*} f([]) & = & l' \\ f(l) & = & h(l, f(tl(l))) \\ \end{eqnarray*} where \(h\) is primitive recursive.
To see this, consider the primitive recursive function defined as follows: \begin{eqnarray*} F(l,0) & = & l' \\ F(l, y+1) & = & h( sub( len(l)~\dot{-}~(y+1), l), F(l, y) )) \\ \end{eqnarray*}
Claim. \(F(l,y) = F(tl(l),y)\) for \(y = 0,\ldots, len(l) - 1\).
The proof is an easy induction on \(y\).
Defin \(f(l) := F(l, len(l))\). Then \(f([]) = F([], len([])) = F([],0) = l'\) and \begin{eqnarray*} f(l) & = & F(l, len(l)) \\ & = & h( sub( len(l)~\dot{-}~len(l)), l), F(l, len(l)-1) )) \\ & = & h( l, F(l, len(l)-1) )) \\ & = & h( l, F(tl(l), len(l)-1) )) ~~\text{ (By claim)}\\ & = & h( l, F(tl(l), len(tl(l))) ) \\ & = & h( l, f(tl(l)) ). \end{eqnarray*}
We encode \(+\) with the list \([0,0]\) and the natural number \(n\) as \([1,n]\). The postfix arithmetic expression \[ 3~5~+~2 +\] is encoded as the list \[ [[1,3],~[1,5],~[0,0],~[1,2],~[0,0]].\] We will describe a primitive recursive function that evaluates an encoded postfix arithmetic expression with only addition. The function will return \([]\) if the expression is invalid and \([1,m]\) if the expression is valid with \(m\) as the evaluated value of the expression. For example, for the expression above, the function will return \([1,10]\). We first define the following helper function: \begin{eqnarray*} h([], s) & = & \textbf{if } Eq(len(s), 1) \textbf{ then } [1,tl(hd(s))] \\ & & \textbf{else } [] \\ h(e, s) & = & \textbf{if } Eq(hd(hd(s)), 1) \textbf{ then } h( tl(e), tl(hd(s)); s ) \\ & & \textbf{else } \\ & & ~~~~~ \begin{array}{l} \textbf{if } AtLeast(1, len(s)) \textbf{ then } [] \\ \textbf{else } h( tl(e), (tl(hd(s))+tl(hd(tl(s))); tl(tl(s) ) \end{array} \end{eqnarray*} Then a desired function is \(Eval(e) = h(e, [])\).