[FOM] "Recursive"
praatika@mappi.helsinki.fi
praatika at mappi.helsinki.fi
Mon Sep 25 02:57:43 EDT 2006
Dear Lucius
Recursive definitions of addition and multiplication were, of course, used
already by Dedekind in 1888.
Hilbert used the expression ”rekurrente” in 1905, and in 1923 the
word ”Rekursion”. Skolem (1923) in turn demanded for a recursive mode of
thinking in the foundations of mathematics. He also proved the (primitive)
recursiveness of many familiar functions.
In his paper on the infinite, Hilbert (1926) extended the extension of the
term and considered more general forms of recursion (with many variables).
Ackermann (1928) proved that this leads indeed to functions which are not
(in modern terms) primitive recursive (p.r.).
In his incompleteness paper, Gödel (1931) defined exactly functions for
which he used the label "rekursiv"; these are the p.r. functions. Rozsa
Peter (1934) suggested the name "primitive recursive".
Gödel was corresponding with Herbrand in 1931. The latter suggested a
definition of general recursive functions. Gödel develeped the suggestion
and presented his own definition in his Princeton lectures in 1934. Kleene
(1936) streamlined it further; he also started to use Peter's "primitive
recursive" for the narrower class of functions.
I guess that it was Kleene's Introduction to Metamathematics (1952) that
made the terminology so widespread.
All the Best, Panu
Panu Raatikainen
Ph.D., Academy Research Fellow,
Docent in Theoretical Philosophy
Department of Philosophy
University of Helsinki
Finland
E-mail: panu.raatikainen at helsinki.fi
http://www.helsinki.fi/collegium/eng/Raatikainen/raatikainen.htm
Lainaus Lucius Schoenbaum <ltsbaum at gmail.com>:
> Hi All,
>
> I was wondering if anyone knows whether Gödel was the one (in Gödel
> 1931) to coin the definition of (what became) primitive recursive
> which I find in Boolos, Burgess, Jeffrey (2002) and in Cori & Lascar
> (2001), which I assume must still be widely accepted by way of
> Kleene? I am curious about the history of this notion.
>
> Thanks,
>
> Lucius Schoenbaum
>
> -
> Lucius T. Schoenbaum
> 706-206-9121
> ltsbaum at gmail.com
>
>
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
More information about the FOM
mailing list