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

edit
 

The last equation can be equivalently written as

 .[4]

Computation

edit

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

The generalized function   leads to the rewrite rules

 

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

The reduction sequence is[6]

 
     
     
     
     
     
     
     
     
     
     
     
     
     

Value tables

edit

Values of F0

edit

F0(xy) = 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 F1

edit

F1(xy) = 2y · (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 F2

edit
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 F3

edit
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

Notes and references

edit
  1. ^ Sudan 1927.
  2. ^ Ackermann 1928.
  3. ^ Calude, Marcus & Tevy 1979.
  4. ^ Calude 1988, p. 92.
  5. ^ Calude 1988, pp. 92–95.
  6. ^ The rightmost innermost occurrences of F are underlined.

Bibliography

edit
  • Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. doi:10.1007/BF01459088. JFM 54.0056.06. S2CID 123431274.
  • 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
edit