Sudan function

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

Concrete implementations can be found on Rosetta Code.[7]

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.
Rosetta Code.

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. "Sudan function".

OEIS: A260003, A260004

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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.

[FOOTNOTERosetta_Code-7] Rosetta Code.