5
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – C7X
    Apr 3 at 8:27

1 Answer 1

8
$\begingroup$

In Recursive predicates and quantifiers (Trans. Amer. Math. Soc. 53 (1943), 41-73) Kleene gives a description of general recursive functions acording to Herbrand and Gödel, as understood before the paper "standardized" the subject.

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.

It's not at all clear how to deal with a system of arbitrary equations. It is not so surprising that the definition of general recursive functions was considered unsatisfactory at the time.

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.

$\endgroup$
2
  • $\begingroup$ Kleene also proved the equivalence between the Herbrand-Gödel "metamathematical" definition and his own definition. If this equivalence is not mentioned in that paper then it should be in Kleene's "General recursive functions of natural numbers" Math Ann vol 112 (1936), pp. 727-766. So it does not seem to correspond to the notion the OP quoted. $\endgroup$
    – godelian
    Apr 3 at 13:52
  • $\begingroup$ @godelian: Thank you for the reference, I am not very familiar with this particular corner of literature. My main takeaway from poking around was that, prior to Kleene's normal form theorem, the definition of "general recursive" was very general and at first sight unmanageable. I hope that's a fair assessment. $\endgroup$ Apr 3 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.