Sudan function
The Sudan function is a recursive, computable function that is totally μ-recursive but not primitive recursive , which it has in common with the better known Ackermann function .
It was published in 1927 by the Romanian mathematician Gabriel Sudan , who, like Wilhelm Ackermann, was a student of David Hilbert .
definition
The following applies to:
background
In 1926 David Hilbert hypothesized that every computable function was primitive-recursive . This was refuted by Wilhelm Ackermann and Gabriel Sudan - both his students - by means of different functions that were published promptly (Sudan 1927 and Ackermann 1928). The Sudan function and the Ackermann function were the first published, non- primitive recursive functions.
Value tables
y \ x | 0 | 1 | 2 | 3 | 4th | 5 |
---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4th | 5 |
1 | 1 | 3 | 5 | 7th | 9 | 11 |
2 | 4th | 8th | 12 | 16 | 20th | 24 |
3 | 11 | 19th | 27 | 35 | 43 | 51 |
4th | 26th | 42 | 58 | 74 | 90 | 106 |
5 | 57 | 89 | 121 | 153 | 185 | 217 |
6th | 120 | 184 | 248 | 312 | 376 | 440 |
y \ x | 0 | 1 | 2 | 3 | 4th | 5 |
---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4th | 5 |
1 | 1 | 8th | 27 | 74 | 185 | 440 |
2 | 19th | F 1 (8, 10) = 10228 | F 1 (27, 29) ≈ 1.55 · 10 10 | F 1 (74, 76) ≈ 5.74 · 10 24 | F 1 (185, 187) | F 1 (440, 442) |
literature
- Gabriel Sudan: Sur le nombre transfini ω ω . Bulletin Math. Soc. Roumaine des sciences 30, pp. 11-30 (1927). JFM review
- Wilhelm Ackermann: On Hilbert's structure of real numbers. Mathematische Annalen 99, pp. 118-133 (1928). JFM review
- Cristian S. Calude , Solomon Marcus, Ionel Tevy: The first example of a recursive function which is not primitive recursive. Historia Mathematica 6 (1979), no. 4, pp. 380-384 doi : 10.1016 / 0315-0860 (79) 90024-7