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
F 0 ( x , y ) = x + y F n + 1 ( x , 0 ) = x if n ≥ 0 F n + 1 ( x , y + 1 ) = F n ( F n + 1 ( x , y ) , F n + 1 ( x , y ) + y + 1 ) if n ≥ 0 {\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
F n + 1 ( x , y + 1 ) = F n ( F n + 1 ( x , y ) , F 0 ( F n + 1 ( x , y ) , y + 1 ) ) {\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}}} .4Computation
These equations can be used as rules of a term rewriting system (TRS).
The generalized function F ( x , y , n ) = d e f F n ( x , y ) {\displaystyle F(x,y,n){\stackrel {\mathrm {def} }{=}}F_{n}(x,y)} leads to the rewrite rules
(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 ) {\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 F ( 2 , 2 , 1 ) → ∗ 12 {\displaystyle F(2,2,1)\rightarrow _{*}12} .5
The reduction sequence is6
| F ( 2 , 2 , 1 ) _ {\displaystyle {\underline {F(2,2,1)}}} |
| → r 3 F ( F ( 2 , 1 , 1 ) , F ( F ( 2 , 1 , 1 ) _ , 2 , 0 ) , 0 ) {\displaystyle \rightarrow _{r3}F(F(2,1,1),F({\underline {F(2,1,1)}},2,0),0)} |
| → r 3 F ( F ( 2 , 1 , 1 ) , F ( F ( F ( 2 , 0 , 1 ) , F ( F ( 2 , 0 , 1 ) _ , 1 , 0 ) , 0 ) , 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)} |
| → r 2 F ( F ( 2 , 1 , 1 ) , F ( F ( F ( 2 , 0 , 1 ) , F ( 2 , 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)} |
| → r 1 F ( F ( 2 , 1 , 1 ) , F ( F ( F ( 2 , 0 , 1 ) _ , 3 , 0 ) , 2 , 0 ) , 0 ) {\displaystyle \rightarrow _{r1}F(F(2,1,1),F(F({\underline {F(2,0,1)}},3,0),2,0),0)} |
| → r 2 F ( F ( 2 , 1 , 1 ) , F ( F ( 2 , 3 , 0 ) _ , 2 , 0 ) , 0 ) {\displaystyle \rightarrow _{r2}F(F(2,1,1),F({\underline {F(2,3,0)}},2,0),0)} |
| → r 1 F ( F ( 2 , 1 , 1 ) , F ( 5 , 2 , 0 ) _ , 0 ) {\displaystyle \rightarrow _{r1}F(F(2,1,1),{\underline {F(5,2,0)}},0)} |
| → r 1 F ( F ( 2 , 1 , 1 ) _ , 7 , 0 ) {\displaystyle \rightarrow _{r1}F({\underline {F(2,1,1)}},7,0)} |
| → r 3 F ( F ( F ( 2 , 0 , 1 ) , F ( F ( 2 , 0 , 1 ) _ , 1 , 0 ) , 0 ) , 7 , 0 ) {\displaystyle \rightarrow _{r3}F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),7,0)} |
| → r 2 F ( F ( F ( 2 , 0 , 1 ) , F ( 2 , 1 , 0 ) _ , 0 ) , 7 , 0 ) {\displaystyle \rightarrow _{r2}F(F(F(2,0,1),{\underline {F(2,1,0)}},0),7,0)} |
| → r 1 F ( F ( F ( 2 , 0 , 1 ) _ , 3 , 0 ) , 7 , 0 ) {\displaystyle \rightarrow _{r1}F(F({\underline {F(2,0,1)}},3,0),7,0)} |
| → r 2 F ( F ( 2 , 3 , 0 ) _ , 7 , 0 ) {\displaystyle \rightarrow _{r2}F({\underline {F(2,3,0)}},7,0)} |
| → r 1 F ( 5 , 7 , 0 ) _ {\displaystyle \rightarrow _{r1}{\underline {F(5,7,0)}}} |
| → r 1 12 {\displaystyle \rightarrow _{r1}12} |
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
- Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. doi:10.1007/BF01459088. JFM 54.0056.06. S2CID 123431274.
- Calude, Cristian; Marcus, Solomon; Tevy, Ionel (1979). "The first example of a recursive function which is not primitive recursive". Historia Mathematica. 6 (4): 380–384. doi:10.1016/0315-0860(79)90024-7.
- Calude, Cristian (1988). Theories of Computational Complexity. Amsterdam: North-Holland. ISBN 978-0-444-70356-9.
- 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
External links
- Rosetta Code (23 July 2024). "Sudan function".
- OEIS: A260003, A260004
References
Sudan 1927. - 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 https://zbmath.org/?format=complete&q=an:53.0171.01 ↩
Ackermann 1928. - Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. doi:10.1007/BF01459088. JFM 54.0056.06. S2CID 123431274. http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PPN=PPN235181684_0099&DMDID=DMDLOG_0009 ↩
Calude, Marcus & Tevy 1979. - Calude, Cristian; Marcus, Solomon; Tevy, Ionel (1979). "The first example of a recursive function which is not primitive recursive". Historia Mathematica. 6 (4): 380–384. doi:10.1016/0315-0860(79)90024-7. https://doi.org/10.1016%2F0315-0860%2879%2990024-7 ↩
Calude 1988, p. 92. - Calude, Cristian (1988). Theories of Computational Complexity. Amsterdam: North-Holland. ISBN 978-0-444-70356-9. https://www.sciencedirect.com/science/book/9780444703569 ↩
Calude 1988, pp. 92–95. - Calude, Cristian (1988). Theories of Computational Complexity. Amsterdam: North-Holland. ISBN 978-0-444-70356-9. https://www.sciencedirect.com/science/book/9780444703569 ↩
The rightmost innermost occurrences of F are underlined. ↩