Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

At some point of history, were the class of primitive recursive functions considered (or even conjectured) to be the class of total recursive functions?

I think I faced this claim sometime ago, but I have now some doubts on my memory... References are warmly welcomed.

share|cite|improve this question
up vote 5 down vote accepted

I haven't ever come across such a claim, if we require that it should refer to the classes that today are called "primitive recursive", respectively "total recursive". Indeed the class of functions we today call "primitive recursive" is usually cited as having been first defined in by Gödel in 1931 (Über formal unentscheidbare Sätze), which was after Ackermann had exhibited a function that is total and computable but not primitive recursive.

Of course it is conceivable, as Hilbert, Ackermann, et al. were struggling in the 1920s to find a suitable formalization of mechanical procedures, that somebody at some time considered whether something equivalent to primitive recursion would be enough to do the trick -- but whether this ever rose to the level of a "conjecture" might me more of a question of definitions than of history.

However, note that Gödel himself in 1931 when he defined the functions we know as primitive recursive, called them simply "recursive". It was only later that consensus decided, somehow, that "recursive" should mean what it does now. But that was merely a case of terminology changing, not the mathematical substance.

Later: See also here (from a book review written by Kleene in 1952):

Hilbert's lecture Über das Unendliche (published 1926) ... proposed to attack the continuum problem of set theory by showing that there is no inconsistency in supposing that the number-theoretic functions are all definable by use of forms of recursion associated with the transfinite ordinals of Cantor's second number class. ... For Hilbert's proposal it was necessary to show that higher forms of recursion do give new functions; and the first demonstration of the existence of a function definable by a double recursion but not by use only of simple or "primitive" recursion was given by Ackermann in 1928 ...

Ackermann's 1928 article works with a concept that looks to be fairly close to primitive recursion. Why Gödel is usually credited with inventing primitive recursion three years later, is then not completely clear. Perhaps just because Gödel made more heroic use of them, showing that they can do rather interesting things rather than just be the base layer in a hierarchy.

But this history seems to make clear that it probably wasn't seriously proposed that primitive recursion would be sufficient to express everything computable. It is unclear that computability was on anyone's mind in this context before 1931. In fact, the secondary sources I've been able to google up all claim that the idea that "computable function" is a robust concept at all did not congeal until the mid-1930s at the earliest, so in 1928 nobody would have even had the vocabulary to conjecture that the primitive recursive functions exhaust the computable ones.

share|cite|improve this answer
I googled around and found Ackermmans original paper, and have edited the answer to contain a discussion of it. – Henning Makholm Jul 5 '12 at 11:01

I have nothing historical to add to what Henning Makholm writes. However, it seems natural to assume that the definition of primitive recursive functions came out of an attempt to define "computable" functions on the natural numbers as those that can be defined by an induction-like process: function values are allowed to be computed in terms of already defined functions and values of the function to be defined itself at arguments that are smaller than the current argument(s). It is not immediately obvious that something fundamental is missing by not allowing unbounded searches (which constitute the difference between recursive and primitive recursive functions, in modern terminology), after all there is for instance no need for anything like that as basic ingredient of Peano's arithmetic (but of course a theory of functions and a logical theory are only very remotely related).

On the other hand it would seem the case that by limiting the recursion to only one parameter at the time and the use of only one previous value, one is missing out a lot of easily defined functions. It is not easy to define the Fibonacci numbers (the map $i\mapsto F_i$) as a primitive recusrive function, nor the binomial coefficients as defined by Pascal's recurrence. (In the latter case the well known multiplicative expression of binomial coefficients in terms of factorials provides an easy alternative, but one easily constructs similar recurrences where it is not possible to cheat using a closed formula; if you try to define such functions as primitive recursive functions you will see that it is really quite hard.) We know that using pairing and un-pairing functions to encode pairs (and more general tuples) into single numbers it is possible to do everything that can be done with a "tame" multi-parameter recursion (not as wild as in the Ackermann function) or course-of-values recursion using simple primitive recursion, but this can hardly have been clear from the outset (and I must say the books I have seen are rather wishy-washy about the matter; there is more focus on showing things that are really not primitive recursive than on showing exactly what kind of recursion schemas can be emulated by primitive recursion). So I surmise that primitive recursion as we define it now was never really considered a serious candidate for being the whole story as far as computable functions go, but maybe initially for the wrong reasons.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.