7
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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"? $\endgroup$
    – boumol
    Commented Jul 5, 2012 at 11:27
  • $\begingroup$ Related discussion at (math.stackexchange.com/questions/166668/…. $\endgroup$
    – Goldstern
    Commented Jul 5, 2012 at 13:01

1 Answer 1

Reset to default
18
$\begingroup$

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).

Improve this answer
$\endgroup$
1