Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Sudan function

Wikipedia contributorsAdapted for Fathomly · View authors
4 min read
Source updated August 28, 2024

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.

01Definition

{\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}}.

02Computation

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.

The reduction sequence is

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

03Value tables

Values of F0

F0(x, y) = x + y

y \ x012345678910
0 012345678910
1 1234567891011
2 23456789101112
3 345678910111213
4 4567891011121314
5 56789101112131415
6 678910111213141516
7 7891011121314151617
8 89101112131415161718
9 910111213141516171819
10 1011121314151617181920

Values of F1

F1(x, y) = 2y · (x + 2) − y − 2

y \ x012345678910
0 012345678910
1 13579111315171921
2 48121620242832364044
3 1119273543515967758391
4 2642587490106122138154170186
5 5789121153185217249281313345377
6 120184248312376440504568632696760
7 24737550363175988710151143127113991527
8 502758101412701526178220382294255028063062
9 10131525203725493061357340854597510956216133
10 20363060408451086132715681809204102281125212276

Values of F2

y \ x01234567
0 01234567
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)
18277418544010152294
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 F3

y \ x01234
0 01234
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
Watch videos about Sudan functionExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Sudan function”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.