Ackermann vs. Sudan [comp.theory #15314]

[Ranan Fraer]

[ Un mesaj interesant din comp.theory despre prioritatea unui
matematician roman - Gabriel Sudan - in descoperirea unei functii
tip Ackermann.]

------ Forwarded Article <y8zoh5y...@berne.ai.mit.edu>
------ From Bill Dubuque <w...@berne.ai.mit.edu>

m...@abacus.concordia.ca ( JOHN MCKAY ) writes:
|
| Can someone assess who originated the so-called "Ackermann fn" ?
| It appears it may not be Ackermann.

Cristian Calude has written a number of papers on the history
of the Ackermann and Sudan functions, e.g. see

Calude, Cristian; Marcus, Solomon; \cedla Tevy, Ionel
The first example of a recursive function which is not primitive recursive.
Historia Math. 6 (1979), no. 4, 380--384. MR 80i:03053 03D20 01A60

Chronologically, Sudan's function is the first example of a recursive
but not primitive recursive function (Bull. Math. Soc. Roumaine Sci.
30 (1927), 11 - 30; Jbuch 53, 171). Ackermann's work was published
slightly later (Math. Ann. 99 (1928), 118 - 133; Jbuch 54, 56). Both
were students of Hilbert, and were working on a problem posed by
Hilbert, and were acquainted with each other's work. Sudan's function
extends to ordinals and majorizes Ackermann's function (except at
a single point). As Smorynski says in his book Logical Number Theory

independently, to two of Hilbert's students, Wilhelm Ackermann and
Gabriel Sudan. Although they gave essentially the same recursion,
Sudan worked with functions of transfinite ordinals and Ackermann
with functions of natural numbers, whence Hilbert cited Ackermann
and Ackermann's is the name associated with the resulting functions.

The paper cited above also has speculations as to why Hilbert and
Bernays did not mention Sudan's construction.

According to MR 82k:03061, Sudan's function is as follows

F (x, y) = x+y
0

F (x, 0) = x
n+1

F (x, y+1) = F ( F (x, y), F (x, y)+y+1 )
n+1 n n+1 n+1

By the way, an excellent forum for mathematical history is
math-his...@enterprise.maa.org -- which includes many
professional math historians. I've CC'ed math-history-list.

-Bill Dubuque

------ End of Forwarded Article