Sudan function explained

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, Ackermann in 1928.

The Sudan function is the earliest published example of a recursive function that is not primitive recursive.

Definition

\begin{array}{lll} F _{0} (x, y) & = x + y \\ F _{n+1} (x, 0 ) & = x & if n \ge 0 \\ F _{n+1} (x, y +1 ) & = F _{n} (F _{n+1} (x, y), F _{n+1} (x, y) + y + 1 ) & if n\ge 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} .

Computation

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

The generalized function

F(x,y,n) \stackrel{ def } F_n(x,y) leads to the rewrite rules\begin{array}{lll} (r1) & F(x, y, 0 ) & → x + y \\ (r2) & F(x, 0 , n +1 ) & → x \\ (r3) & F(x, y +1 , n +1 ) & → 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 ) → _{*} 12 .

The reduction sequence is^[1]

\underline{{F( 2 , 2 , 1 )}}
→ _{r3} F(F( 2 , 1 , 1 ),F(\underline{{F( 2 , 1 , 1 )}}, 2 , 0 ), 0 )
→ _{r3} F(F( 2 , 1 , 1 ),F(F(F( 2 , 0 , 1 ),F(\underline{{F( 2 , 0 , 1 )}}, 1 , 0 ), 0 ), 2 , 0 ), 0 )
→ _{r2} F(F( 2 , 1 , 1 ),F(F(F( 2 , 0 , 1 ),\underline{{F( 2 , 1 , 0 )}}, 0 ), 2 , 0 ), 0 )
→ _{r1} F(F( 2 , 1 , 1 ),F(F(\underline{{F( 2 , 0 , 1 )}}, 3 , 0 ), 2 , 0 ), 0 )
→ _{r2} F(F( 2 , 1 , 1 ),F(\underline{{F( 2 , 3 , 0 )}}, 2 , 0 ), 0 )
→ _{r1} F(F( 2 , 1 , 1 ),\underline{{F( 5 , 2 , 0 )}}, 0 )
→ _{r1} F(\underline{{F( 2 , 1 , 1 )}}, 7 , 0 )
→ _{r3} F(F(F( 2 , 0 , 1 ),F(\underline{{F( 2 , 0 , 1 )}}, 1 , 0 ), 0 ), 7 , 0 )
→ _{r2} F(F(F( 2 , 0 , 1 ),\underline{{F( 2 , 1 , 0 )}}, 0 ), 7 , 0 )
→ _{r1} F(F(\underline{{F( 2 , 0 , 1 )}}, 3 , 0 ), 7 , 0 )
→ _{r2} F(\underline{{F( 2 , 3 , 0 )}}, 7 , 0 )
→ _{r1} \underline{{F( 5 , 7 , 0 )}}
→ _{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
	x
1	F1 (F2(0, 0),   F2(0, 0)+1)	F1 (F2(1, 0),   F2(1, 0)+1)	F1 (F2(2, 0),   F2(2, 0)+1)	F1 (F2(3, 0),   F2(3, 0)+1)	F1 (F2(4, 0),   F2(4, 0)+1)	F1 (F2(5, 0),   F2(5, 0)+1)	F1 (F2(6, 0),   F2(6, 0)+1)	F1 (F2(7, 0),   F2(7, 0)+1)
	F1(0, 1)	F1(1, 2)	F1(2, 3)	F1(3, 4)	F1(4, 5)	F1(5, 6)	F1(6, 7)	F1(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	F1 (F2(0, 1),   F2(0, 1)+2)	F1 (F2(1, 1),   F2(1, 1)+2)	F1 (F2(2, 1),   F2(2, 1)+2)	F1 (F2(3, 1),   F2(3, 1)+2)	F1 (F2(4, 1),   F2(4, 1)+2)	F1 (F2(5, 1),   F2(5, 1)+2)	F1 (F2(6, 1),   F2(6, 1)+2)	F1 (F2(7, 1),   F2(7, 1)+2)
	F1(1, 3)	F1(8, 10)	F1(27, 29)	F1(74, 76)	F1(185, 187)	F1(440, 442)	F1(1015, 1017)	F1(2294, 2296)
	19	10228	15569256417	≈ 5,742397643 · 10^24	≈ 3,668181327 · 10^58	≈ 5,019729940 · 10^135	≈ 1,428323374 · 10^309	≈ 3,356154368 · 10^694
	2^2x+1·(x+2) − x − 1 · (2^x+1·(x+2) − x − 1) − (2^x+1·(x+2) − x + 1) ≈ 10^lg 2 · (2x+1·(x+2) − x − 1) + lg(2^x+1·(x+2) − x − 1) ≈ 10^lg 2 · 2x+1·(x+2) + lg(2^x+1·(x+2)) ≈ 10^lg 2 · (2x+1·(x+2)) = 10^10lg lg 2 + lg 2·(x+1) + lg(x+2) ≈ 10^10lg 2·(x+1) + lg(x+2)
3	F1 (F2(0, 2),   F2(0, 2)+3)	F1 (F2(1, 2),   F2(1, 2)+3)	F1 (F2(2, 2),   F2(2, 2)+3)	F1 (F2(3, 2),   F2(3, 2)+3)	F1 (F2(4, 2),   F2(4, 2)+3)	F1 (F2(5, 2),   F2(5, 2)+3)	F1 (F2(6, 2),   F2(6, 2)+3)	F1 (F2(7, 2),   F2(7, 2)+3)
	F1(F1(1,3),   F1(1,3)+3)	F1(F1(8,10),   F1(8,10)+3)	F1(F1(27,29),   F1(27,29)+3)	F1(F1(74,76),   F1(74,76)+3)	F1(F1(185,187),   F1(185,187)+3)	F1(F1(440,442),   F1(440,442)+3)	F1(F1(1015,1017),   F1(1015,1017)+3)	F1(F1(2294,2297),   F1(2294,2297)+3)
	F1(19, 22)	F1(10228, 10231)	F1(15569256417, 15569256420)	F1(≈6·10^24, ≈6·10^24)	F1(≈4·10^58, ≈4·10^58)	F1(≈5·10^135, ≈5·10^135)	F1(≈10^309, ≈10^309)	F1(≈3·10^694, ≈3·10^694)
	88080360	≈ 7,04 · 10^3083	≈ 7,82 · 10^4686813201	≈ 10^1,72·1024	≈ 10^1,10·1058	≈ 10^1,51·10135	≈ 10^4,30·10308	≈ 10^1,01·10694
	longer expression, starts with 2^22x+1 an, ≈ 10^1010lg 2·(x+1) + lg(x+2)
4	F1 (F2(0, 3),   F2(0, 3)+4)	F1 (F2(1, 3),   F2(1, 3)+4)	F1 (F2(2, 3),   F2(2, 3)+4)	F1 (F2(3, 3),   F2(3, 3)+4)	F1 (F2(4, 3),   F2(4, 3)+4)	F1 (F2(5, 3),   F2(5, 3)+4)	F1 (F2(6, 3),   F2(6, 3)+4)	F1 (F2(7, 3),   F2(7, 3)+4)
	F1 (F1(19, 22),   F1(19, 22)+4)	F1 (F1(10228,   10231),   F1(10228,   10231)+4)	F1 (F1(15569256417,   15569256420),   F1(15569256417,   15569256420)+4)	F1 (F1(≈5,74·10^24, ≈5,74·10^24), F1(≈5,74·10^24, ≈5,74·10^24))	F1 (F1(≈3,67·10^58, ≈3,67·10^58), F1(≈3,67·10^58, ≈3,67·10^58))	F1 (F1(≈5,02·10^135, ≈5,02·10^135), F1(≈5,02·10^135, ≈5,02·10^135))	F1 (F1(≈1,43·10^309, ≈1,43·10^309), F1(≈1,43·10^309, ≈1,43·10^309))	F1 (F1(≈3,36·10^694, ≈3,36·10^694), F1(≈3,36·10^694, ≈3,36·10^694))
	F1(88080360, 88080364)	F1(10230·2^10231−10233, 10230·2^10231−10229)
	≈ 3,5 · 10^26514839
	much longer expression, starts with 2^222x+1 an, ≈ 10^101010lg 2·(x+1) + lg(x+2)

Values of F₃

y \ ^x	0	1	2	3	4
0	0	1	2	3	4
	x
1	F2 (F3(0, 0),   F3(0, 0)+1)	F2 (F3(1, 0),   F3(1, 0)+1)	F2 (F3(2, 0),   F3(2, 0)+1)	F2 (F3(3, 0),   F3(3, 0)+1)	F2 (F3(4, 0),   F3(4, 0)+1)
	F2(0, 1)	F2(1, 2)	F2(2, 3)	F2(3, 4)	F2(4, 5)
	1	10228	≈ 7,82 · 10^4686813201
	No closed expressions possible within the framework of normal mathematical notation
2	F3 (F4(0, 1),   F4(0, 1)+2)	F3 (F4(1, 1),   F4(1, 1)+2)	F3 (F4(2, 1),   F4(2, 1)+2)	F3 (F4(3, 1),   F4(3, 1)+2)	F3 (F4(4, 1),   F4(4, 1)+2)
	F3 (1, 3)	F3 (10228, 10230)	F3 (≈10^4686813201,  ≈10^4686813201)
	No closed expressions possible within the framework of normal mathematical notation

Bibliography

• . Wilhelm . . Zum Hilbertschen Aufbau der reellen Zahlen . 1928 . 99 . 118–133 . 10.1007/BF01459088 . 123431274 . 54.0056.06.
• Calude . Cristian . Cristian S. Calude . Marcus . Solomon . Solomon Marcus . Tevy . Ionel . The first example of a recursive function which is not primitive recursive . . 1979 . 10.1016/0315-0860(79)90024-7 . free . 6 . 4 . 380–384.
• Book: Calude , Cristian . Cristian S. Calude . Theories of Computational Complexity . 1988 . . Amsterdam . 978-0-444-70356-9.
• . Gabriel . Sur le nombre transfini ω^ω . Bulletin mathématique de la Société Roumaine des Sciences . 1927 . 30 . 11–30 . 43769875 . 53.0171.01 . Jbuch 53, 171.

External links

• Web site: . Sudan function . 23 July 2024 .
• OEIS: A260003, A260004

Notes and References

1. The rightmost innermost occurrences of F are underlined.