Gödel numbering for sequences.
Thus
encodes the first n values of f. The function
where append(n,s,x) computes, whenever s encodes a sequence of length n, a new sequence t of length n + 1 such that t[n] = x and t[i] = s[i] for all i < n. This is a primitive recursive function, under the assumption of an appropriate Gödel numbering; h is assumed primitive recursive to begin with. Thus the recursion relation can be written as primitive recursion:
-
f
¯
(
n
+
1
)
=
g
(
n
,
f
¯
(
n
)
)
{\displaystyle {\bar {f}}(n+1)=g(n,{\bar {f}}(n))}

where g is itself primitive recursive, being the composition of two such functions:
-
g
(
i
,
j
)
=
a
p
p
e
n
d
(
i
,
j
,
h
(
i
,
j
)
)
,
{\displaystyle g(i,j)={\mathit {append}}(i,j,h(i,j)),}

Given
f
where g is itself primitive recursive, being the composition of two such functions:
-
g
(
i
,
j
)
=
a
p
p
e
n
d
(
i
,
j
,
h
(
i
,
j
)
)
,
{\displaystyle g(i,j)={\mathit {append}}(i,j,h(i,j)),}
Given
f
¯
{\displaystyle {\bar {f}}}
, the original function f can be defined by
f
(
n
)
=
f
¯
(
n
+
1
)
[
n
]
{\displaystyle f(n)={\bar {f}}(n+1)[n]}
, which shows that it is also a primitive recursive function.
Application to primitive recursive functions
In the context of primitive recursive functions, it is convenient to have a means to represent finite sequences of natural numbers as single natural numbers. One such method, Gödel's encoding, represents a sequence of positive integers
⟨
n
0
,
n
1
,
n
2
,
…
,
n
In the context of primitive recursive functions, it is convenient to have a means to represent finite sequences of natural numbers as single natural numbers. One such method, Gödel's encoding, represents a sequence of positive integers
⟨
n
0
,
n
1
,
n
2
,
…
,
n
k
⟩
{\displaystyle \langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle }
as
-
∏
is allowed to include zeros, it is instead represented as
-
⟨
n
0
,
n
1
,
n
2
,
…
,
n
k
⟩
{\displaystyle \langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle }
is allowed to include zeros, it is instead represented as
which makes it possible to distinguish the codes for the sequences
⟨
0
⟩
{\displaystyle \langle 0\rangle }
and
⟨
0
,
0
⟩
{\displaystyle \langle 0,0\rangle }
.
Limitations
Not every recursive definition can be transformed into a primitive recursive definition. One known example is Ackermann's function, which is of the form A(m,n) and is provably not primitive recursive.
Indeed, every new value A(m+1, n) depends on the sequence of previously defined values A(i, j), but the i-s and j-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (i, j) = (m, A(m+1, n)). Thus one cannot encode the previously computed sequence of values in a primitive recursive way in the manner suggested above (or at all, as it turns out this function is not primitive recursive).
References
- Hinman, P.G., 2006, Fundame
Not every recursive definition can be transformed into a primitive recursive definition. One known example is Ackermann's function, which is of the form A(m,n) and is provably not primitive recursive.
Indeed, every new value A(m+1, n) depends on the sequence of previously defined values A(i, j), but the i-s and j-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (i, j) = (<
Indeed, every new value A(m+1, n) depends on the sequence of previously defined values A(i, j), but the i-s and j-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (i, j) = (m, A(m+1, n)). Thus one cannot encode the previously computed sequence of values in a primitive recursive way in the manner suggested above (or at all, as it turns out this function is not primitive recursive).