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

${\displaystyle {\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

${\displaystyle {\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 ${\displaystyle F(x,y,n){\stackrel {\mathrm {def} }{=}}F_{n}(x,y)}$ leads to the rewrite rules

${\displaystyle {\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 ${\displaystyle F(2,2,1)\rightarrow _{*}12}$.^[5]

The reduction sequence is^[6]

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

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

${\displaystyle \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)}$

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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
	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
	2x+1 · (x + 2) − x − 3 ≈ 10lg 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 · 1024	≈ 3,668181327 · 1058	≈ 5,019729940 · 10135	≈ 1,428323374 · 10309	≈ 3,356154368 · 10694
	22x+1·(x+2) − x − 1 · (2x+1·(x+2) − x − 1) − (2x+1·(x+2) − x + 1) ≈ 10lg 2 · (2x+1·(x+2) − x − 1) + lg(2x+1·(x+2) − x − 1) ≈ 10lg 2 · 2x+1·(x+2) + lg(2x+1·(x+2)) ≈ 10lg 2 · (2x+1·(x+2)) = 1010lg lg 2 + lg 2·(x+1) + lg(x+2) ≈ 1010lg 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·1024, ≈6·1024)	F1(≈4·1058, ≈4·1058)	F1(≈5·10135, ≈5·10135)	F1(≈10309, ≈10309)	F1(≈3·10694, ≈3·10694)
	88080360	≈ 7,04 · 103083	≈ 7,82 · 104686813201	≈ 101,72·1024	≈ 101,10·1058	≈ 101,51·10135	≈ 104,30·10308	≈ 101,01·10694
	longer expression, starts with 222x+1 an, ≈ 101010lg 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·1024, ≈5,74·1024), F1(≈5,74·1024, ≈5,74·1024))	F1 (F1(≈3,67·1058, ≈3,67·1058), F1(≈3,67·1058, ≈3,67·1058))	F1 (F1(≈5,02·10135, ≈5,02·10135), F1(≈5,02·10135, ≈5,02·10135))	F1 (F1(≈1,43·10309, ≈1,43·10309), F1(≈1,43·10309, ≈1,43·10309))	F1 (F1(≈3,36·10694, ≈3,36·10694), F1(≈3,36·10694, ≈3,36·10694))
	F1(88080360, 88080364)	F1(10230·210231−10233, 10230·210231−10229)
	≈ 3,5 · 1026514839
	much longer expression, starts with 2222x+1 an, ≈ 10101010lg 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 · 104686813201
	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 (≈104686813201,  ≈104686813201)
	No closed expressions possible within the framework of normal mathematical notation