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: ${\displaystyle x,y,n\in \mathbb {N} _{0}}$

${\displaystyle F_{0}(x,y)=x+y,\,}$

${\displaystyle F_{n+1}(x,0)=x,\ n\geq 0\,}$

${\displaystyle F_{n+1}(x,y+1)=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1),\ n\geq 0.\,}$

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

Values ​​of F ₁ ( x ,  y )

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

Values ​​of F ₂ ( x ,  y )

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