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
The last equation can be equivalently written as .
Computation 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 .
The reduction sequence isThe rightmost innermost occurrences of F are underlined.
Value tables
Values of F0 F0(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 F1 F1(x, y) = 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 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 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
Bibliography
External links
OEIS: A260003, A260004