Sudan function

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

In the theory of computation, the Sudan function is an example of a function that is recursive, but not primitive recursive. This is also true of the better-known Ackermann function.

In 1926, David Hilbert conjectured that every computable function was primitive recursive. This was refuted by Gabriel Sudan and Wilhelm Ackermann — both his students — using different functions that were published in quick succession: Sudan in 1927,^[1] Ackermann in 1928.^[2]

The Sudan function is the earliest published example of a recursive function that is not primitive recursive.^[3]

Definition

{\begin{array}{lll}F_{0}(x,y)&=x+y\\F_{n+1}(x,0)&=x&{\text{if }}n\geq 0\\F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)&{\text{if }}n\geq 0\\\end{array}}

The last equation can be equivalently written as

{\begin{array}{lll}F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{0}(F_{n+1}(x,y),y+1))\\\end{array}}

.^[4]

Computation

These equations can be used as rules of a term rewriting system (TRS).

The generalized function $F(x,y,n){\stackrel {\mathrm {def} }{=}}F_{n}(x,y)$ leads to the rewrite rules

{\begin{array}{lll}{\text{(r1)}}&F(x,y,0)&\rightarrow x+y\\{\text{(r2)}}&F(x,0,n+1)&\rightarrow x\\{\text{(r3)}}&F(x,y+1,n+1)&\rightarrow F(F(x,y,n+1),F(F(x,y,n+1),y+1,0),n)\\\end{array}}

At each reduction step the rightmost innermost occurrence of F is rewritten, by application of one of the rules (r1) - (r3).

Calude (1988) gives an example: compute $F(2,2,1)\rightarrow _{*}12$ .^[5]

The reduction sequence is^[6]

{\underline {F(2,2,1)}}

\rightarrow _{r3}F(F(2,1,1),F({\underline {F(2,1,1)}},2,0),0)

\rightarrow _{r3}F(F(2,1,1),F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),2,0),0)

\rightarrow _{r2}F(F(2,1,1),F(F(F(2,0,1),{\underline {F(2,1,0)}},0),2,0),0)

\rightarrow _{r1}F(F(2,1,1),F(F({\underline {F(2,0,1)}},3,0),2,0),0)

\rightarrow _{r2}F(F(2,1,1),F({\underline {F(2,3,0)}},2,0),0)

\rightarrow _{r1}F(F(2,1,1),{\underline {F(5,2,0)}},0)

\rightarrow _{r1}F({\underline {F(2,1,1)}},7,0)

\rightarrow _{r3}F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),7,0)

\rightarrow _{r2}F(F(F(2,0,1),{\underline {F(2,1,0)}},0),7,0)

\rightarrow _{r1}F(F({\underline {F(2,0,1)}},3,0),7,0)

\rightarrow _{r2}F({\underline {F(2,3,0)}},7,0)

\rightarrow _{r1}{\underline {F(5,7,0)}}

\rightarrow _{r1}12

Value tables

Values of F₀

F₀(x, y) = x + y

_y \ ^x	0	1	2	3	4	5	6	7	8	9	10
0	0	1	2	3	4	5	6	7	8	9	10
1	1	2	3	4	5	6	7	8	9	10	11
2	2	3	4	5	6	7	8	9	10	11	12
3	3	4	5	6	7	8	9	10	11	12	13
4	4	5	6	7	8	9	10	11	12	13	14
5	5	6	7	8	9	10	11	12	13	14	15
6	6	7	8	9	10	11	12	13	14	15	16
7	7	8	9	10	11	12	13	14	15	16	17
8	8	9	10	11	12	13	14	15	16	17	18
9	9	10	11	12	13	14	15	16	17	18	19
10	10	11	12	13	14	15	16	17	18	19	20

Values of F₁

F₁(x, y) = 2^y · (x + 2) − y − 2

_y \ ^x	0	1	2	3	4	5	6	7	8	9	10
0	0	1	2	3	4	5	6	7	8	9	10
1	1	3	5	7	9	11	13	15	17	19	21
2	4	8	12	16	20	24	28	32	36	40	44
3	11	19	27	35	43	51	59	67	75	83	91
4	26	42	58	74	90	106	122	138	154	170	186
5	57	89	121	153	185	217	249	281	313	345	377
6	120	184	248	312	376	440	504	568	632	696	760
7	247	375	503	631	759	887	1015	1143	1271	1399	1527
8	502	758	1014	1270	1526	1782	2038	2294	2550	2806	3062
9	1013	1525	2037	2549	3061	3573	4085	4597	5109	5621	6133
10	2036	3060	4084	5108	6132	7156	8180	9204	10228	11252	12276

Values of F₂

_y \ ^x	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
0	x
1	F₁ (F₂(0, 0), F₂(0, 0)+1)	F₁ (F₂(1, 0), F₂(1, 0)+1)	F₁ (F₂(2, 0), F₂(2, 0)+1)	F₁ (F₂(3, 0), F₂(3, 0)+1)	F₁ (F₂(4, 0), F₂(4, 0)+1)	F₁ (F₂(5, 0), F₂(5, 0)+1)	F₁ (F₂(6, 0), F₂(6, 0)+1)	F₁ (F₂(7, 0), F₂(7, 0)+1)
	F₁(0, 1)	F₁(1, 2)	F₁(2, 3)	F₁(3, 4)	F₁(4, 5)	F₁(5, 6)	F₁(6, 7)	F₁(7, 8)
	1	8	27	74	185	440	1015	2294
	2^x+1 · (x + 2) − x − 3 ≈ 10^{lg 2·(x+1) + lg(x+2)}
2	F₁ (F₂(0, 1), F₂(0, 1)+2)	F₁ (F₂(1, 1), F₂(1, 1)+2)	F₁ (F₂(2, 1), F₂(2, 1)+2)	F₁ (F₂(3, 1), F₂(3, 1)+2)	F₁ (F₂(4, 1), F₂(4, 1)+2)	F₁ (F₂(5, 1), F₂(5, 1)+2)	F₁ (F₂(6, 1), F₂(6, 1)+2)	F₁ (F₂(7, 1), F₂(7, 1)+2)
	F₁(1, 3)	F₁(8, 10)	F₁(27, 29)	F₁(74, 76)	F₁(185, 187)	F₁(440, 442)	F₁(1015, 1017)	F₁(2294, 2296)
	19	10228	15569256417	≈ 5,742397643 · 10²⁴	≈ 3,668181327 · 10⁵⁸	≈ 5,019729940 · 10¹³⁵	≈ 1,428323374 · 10³⁰⁹	≈ 3,356154368 · 10⁶⁹⁴
	2^{2^x+1·(x+2) − x − 1} · (2^x+1·(x+2) − x − 1) − (2^x+1·(x+2) − x + 1) ≈ 10^{lg 2 · (2^x+1·(x+2) − x − 1) + lg(2^x+1·(x+2) − x − 1)} ≈ 10^{lg 2 · 2^x+1·(x+2) + lg(2^x+1·(x+2))} ≈ 10^{lg 2 · (2^x+1·(x+2))} = 10^{10^{lg lg 2 + lg 2·(x+1) + lg(x+2)}} ≈ 10^{10^{lg 2·(x+1) + lg(x+2)}}
3	F₁ (F₂(0, 2), F₂(0, 2)+3)	F₁ (F₂(1, 2), F₂(1, 2)+3)	F₁ (F₂(2, 2), F₂(2, 2)+3)	F₁ (F₂(3, 2), F₂(3, 2)+3)	F₁ (F₂(4, 2), F₂(4, 2)+3)	F₁ (F₂(5, 2), F₂(5, 2)+3)	F₁ (F₂(6, 2), F₂(6, 2)+3)	F₁ (F₂(7, 2), F₂(7, 2)+3)
	F₁(F₁(1,3), F₁(1,3)+3)	F₁(F₁(8,10), F₁(8,10)+3)	F₁(F₁(27,29), F₁(27,29)+3)	F₁(F₁(74,76), F₁(74,76)+3)	F₁(F₁(185,187), F₁(185,187)+3)	F₁(F₁(440,442), F₁(440,442)+3)	F₁(F₁(1015,1017), F₁(1015,1017)+3)	F₁(F₁(2294,2297), F₁(2294,2297)+3)
	F₁(19, 22)	F₁(10228, 10231)	F₁(15569256417, 15569256420)	F₁(≈6·10²⁴, ≈6·10²⁴)	F₁(≈4·10⁵⁸, ≈4·10⁵⁸)	F₁(≈5·10¹³⁵, ≈5·10¹³⁵)	F₁(≈10³⁰⁹, ≈10³⁰⁹)	F₁(≈3·10⁶⁹⁴, ≈3·10⁶⁹⁴)
	88080360	≈ 7,04 · 10³⁰⁸³	≈ 7,82 · 10^4686813201	≈ 10^{1,72·10²⁴}	≈ 10^{1,10·10⁵⁸}	≈ 10^{1,51·10¹³⁵}	≈ 10^{4,30·10³⁰⁸}	≈ 10^{1,01·10⁶⁹⁴}
	longer expression, starts with 2^{2^{2^x+1}} an, ≈ 10^{10^{10^{lg 2·(x+1) + lg(x+2)}}}
4	F₁ (F₂(0, 3), F₂(0, 3)+4)	F₁ (F₂(1, 3), F₂(1, 3)+4)	F₁ (F₂(2, 3), F₂(2, 3)+4)	F₁ (F₂(3, 3), F₂(3, 3)+4)	F₁ (F₂(4, 3), F₂(4, 3)+4)	F₁ (F₂(5, 3), F₂(5, 3)+4)	F₁ (F₂(6, 3), F₂(6, 3)+4)	F₁ (F₂(7, 3), F₂(7, 3)+4)
	F₁ (F₁(19, 22), F₁(19, 22)+4)	F₁ (F₁(10228, 10231), F₁(10228, 10231)+4)	F₁ (F₁(15569256417, 15569256420), F₁(15569256417, 15569256420)+4)	F₁ (F₁(≈5,74·10²⁴, ≈5,74·10²⁴), F₁(≈5,74·10²⁴, ≈5,74·10²⁴))	F₁ (F₁(≈3,67·10⁵⁸, ≈3,67·10⁵⁸), F₁(≈3,67·10⁵⁸, ≈3,67·10⁵⁸))	F₁ (F₁(≈5,02·10¹³⁵, ≈5,02·10¹³⁵), F₁(≈5,02·10¹³⁵, ≈5,02·10¹³⁵))	F₁ (F₁(≈1,43·10³⁰⁹, ≈1,43·10³⁰⁹), F₁(≈1,43·10³⁰⁹, ≈1,43·10³⁰⁹))	F₁ (F₁(≈3,36·10⁶⁹⁴, ≈3,36·10⁶⁹⁴), F₁(≈3,36·10⁶⁹⁴, ≈3,36·10⁶⁹⁴))
	F₁(88080360, 88080364)	F₁(10230·2¹⁰²³¹−10233, 10230·2¹⁰²³¹−10229)
	≈ 3,5 · 10^26514839
	much longer expression, starts with 2^{2^{2^{2^x+1}}} an, ≈ 10^{10^{10^{10^{lg 2·(x+1) + lg(x+2)}}}}

Values of F₃

_y \ ^x	0	1	2	3	4
0	0	1	2	3	4
0	x
1	F₂ (F₃(0, 0), F₃(0, 0)+1)	F₂ (F₃(1, 0), F₃(1, 0)+1)	F₂ (F₃(2, 0), F₃(2, 0)+1)	F₂ (F₃(3, 0), F₃(3, 0)+1)	F₂ (F₃(4, 0), F₃(4, 0)+1)
	F₂(0, 1)	F₂(1, 2)	F₂(2, 3)	F₂(3, 4)	F₂(4, 5)
	1	10228	≈ 7,82 · 10^4686813201
	No closed expressions possible within the framework of normal mathematical notation
2	F₃ (F₄(0, 1), F₄(0, 1)+2)	F₃ (F₄(1, 1), F₄(1, 1)+2)	F₃ (F₄(2, 1), F₄(2, 1)+2)	F₃ (F₄(3, 1), F₄(3, 1)+2)	F₃ (F₄(4, 1), F₄(4, 1)+2)
	F₃ (1, 3)	F₃ (10228, 10230)	F₃ (≈10^4686813201, ≈10^4686813201)

	No closed expressions possible within the framework of normal mathematical notation

Notes and references

^ Sudan 1927.
^ Ackermann 1928.
^ Calude, Marcus & Tevy 1979.
^ Calude 1988, p. 92.
^ Calude 1988, pp. 92–95.
^ The rightmost innermost occurrences of F are underlined.

Bibliography

Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. doi:10.1007/BF01459088. JFM 54.0056.06. S2CID 123431274.

Calude, Cristian; Marcus, Solomon; Tevy, Ionel (1979). "The first example of a recursive function which is not primitive recursive". Historia Mathematica. 6 (4): 380–384. doi:10.1016/0315-0860(79)90024-7.

Calude, Cristian (1988). Theories of Computational Complexity. Amsterdam: North-Holland. ISBN 978-0-444-70356-9.

Sudan, Gabriel (1927). "Sur le nombre transfini ω^ω". Bulletin mathématique de la Société Roumaine des Sciences. 30: 11–30. JFM 53.0171.01. JSTOR 43769875. Jbuch 53, 171

External links

Rosetta Code (23 July 2024). "Sudan function".

OEIS: A260003, A260004

[FOOTNOTESudan1927-1] Sudan 1927.

[FOOTNOTEAckermann1928-2] Ackermann 1928.

[FOOTNOTECaludeMarcusTevy1979-3] Calude, Marcus & Tevy 1979.

[FOOTNOTECalude198892-4] Calude 1988, p. 92.

[FOOTNOTECalude198892–95-5] Calude 1988, pp. 92–95.

[6] The rightmost innermost occurrences of F are underlined.

[1]

[2]

[3]

[4]

[5]

[6]