Two pages from the article in Mathematische Annalen 95:
David Hilbert "Über das Unendliche",
1925.
Hilbert's 1925 lecture (online) stops short
of the part on double recursive functions.
For a full English translation of the article,
with an introduction, see:
Jean van Heijenoort "From Frege to Gödel", 1967,
pp 367-392 "On the infinite".
So Hilbert's index under φ
functions as the second iterator of a double recursion,
suited as the third parameter of a superexponential function
H
:
H(a,1,n1) = φn+1(a,1) = ι(φn,a,1) = a H(a,b1,n1) = φn+1(a,b+1) = ι(φn,a,b+1) = φn(a,ι(φn,a,b)) = φn(a,φn+1(a,b)) = H(a,H(a,b,n1),n) == H(a,..a..,n) :b: for n>0
From the initial
φ1(a,b) = a+b
follows that
ι(φ0,a,1) = a+1
adds one.
The primitive function φ0
that Hilbert held behind is a choice successor function.
φ1(a,b+1) = a+b+1 = ι(φ0,a,b+1) = φ0(a,ι(φ0,a,b)) = φ0(a,φ1(a,b)) = φ0(a,a+b) then φ0(a,b) = φ(b) = b+1
Hilbert's function φn+2(a,b)
expresses exactly the superpowers of Knuth's up-arrows
a↑{n}b
where n
counts the number of arrows in the operator.
From here
Ackermann
went on to prove that the function
A(n) = H(n,n,n1)
is not primitive recursively definable and strictly faster
than any such φ
functions.