MathOverflow is a question and answer site for professional mathematicians. 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

I have thought that Gödel introduced the concept of Primitive recursive functions in his seminal paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme" (I hope I got the title right...). This paper, to best of my knowledge, was published in 1931.

Ackermann published the famous Ackermann function in his paper "Zum Hilbertschen Aufbau der reellen Zahlen" in (again, to best of my knowledge) 1928. His publication seems to enclose primitive recursive functions and the main results is that there exists a total computable function outside PR. This suggests that PR has been known prior 1928, thus prior Gödel's work.

Who introduced primitive recursive functions first?

share|cite|improve this question
Just to clarify your question. Is it about "who was the first to introduce this family of functions" or about "who coined the term primitive recursive functions"? – boumol Jul 5 '12 at 11:27
Related discussion at (…. – Goldstern Jul 5 '12 at 13:01
up vote 16 down vote accepted

I believe the explicit use of definitions by primitive recursion goes back to Grassman, 1861.

Dedekind in 1888 not only highlighted such definitions but had a proof that they work as intended, i.e. define unique functions.

But it is probably Skolem who first clearly recognised the primitive recursive functions as together forming a class of functions of particular interest. Indeed, his 1923 paper is entitled "The foundations of elementary arithmetic established by means of the recursive mode of thought ...", and, as with Gödel in 1931, by "recursive" Skolem here means "primitive recursive". This paper is usually credited with isolating Primitive Recursive Arithmetic as of particular interest for finitism (and hence for the Hilbert Programme).

share|cite|improve this answer
I suggest you take a look at the book for a more detailed explanation of Peter Smith's remark. – boumol Jul 5 '12 at 14:10

Your Answer


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