# Hilbert's and Gödel's expanded definition of "Recursive Function"

There is a very interesting comment in this post:

I must also make one terminological caveat: Hilbert, and later Godel, used the phrase "recursive function" in a way very different from the modern sense (= computable); they considered a truly huge range of recursions, to the point that plausibly every function of natural numbers could be recursive in this sense.

This seems very interesting and I haven't heard it before. What is the definition of "recursive function" that Hilbert and Gödel use, and how is it different from just computable function?

In particular, what kind of recursions did they look at such that every possible function of the naturals could somehow be built up from them? Did they have uncountably many recursions or what?

• Stanford Encyclopedia of Philosophy seems to suggest that Gödel's usage of "recursive function" only refers to what are now known as primitive recursive functions (near the bottom of section 1.2 in "Recursive Functions".) There it also reproduces Gödel's definition of recursive function from his 1931 paper.
– C7X
Apr 3 at 8:27

According to the definition given therein (I am skipping over some details involving given, auxiliary, and principal function symbols), a sytem of equations $$\mathcal{S}$$ in function symbols $$f_1, \ldots, f_n$$, each with a given arity, is a list of equations of the form $$L = R$$, where $$L$$ and $$R$$ are expressions obtained from $$0$$, successor, variables, and the function symbols $$f_i$$. There is no restriction on how the function symbols appear, other than their arities being respected. There are basic substitution rules for manipulating expressions, see the paper.
Kleene gives an example showing hot to express the minimization operator $$\mu y . (r(x_1, \ldots, x_n, y) = 0)$$ in this way (I write $$\vec{x}$$ for $$x_1, \ldots, x_n$$ and $$n^{+}$$ for successor of $$n$$): \begin{align*} \sigma(0, \vec{x}, y) &= y\\ \sigma(z^{+}, \vec{x}, y) &= \sigma(r(\vec{x}, y^{+}), \vec{x}, y^{+}) \\ \phi(\vec{x}) &= \sigma(\rho(\vec{x},0), \vec{x}, 0) \end{align*} This is a system of equations in $$\sigma$$ and $$\phi$$, for a given $$r$$. We then set $$\mu y. (r(\vec{x}, y) = 0) \mathrel{{:}{=}} \phi(\vec{x})$$.
Kleene goes on to prove that one can reduce every system $$\mathcal{S}$$ to one involving primitive recursive functions (which he defines in the usual way) and the minimization operator $$\mu$$. Apparently after this paper everyone forgot about the original unruly definition in terms of systems of arbitrary equations.