Sudan function

From HandWiki

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.[1] The Sudan function was the first function having this property to be published.[2] It was discovered (and published [3]) in 1927 by Gabriel Sudan, a Romanian mathematician who was a student of David Hilbert.

Definition

[math]\displaystyle{ \begin{array}{lll} F_0 (x, y) & = x+y \\ F_{n+1} (x, 0) & = x & \text{if } n \ge 0 \\ F_{n+1} (x, y+1) & = F_n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1) & \text{if } n\ge 0 \\ \end{array} }[/math]

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

  1. ↑ Ackermann 1928.
  2. ↑ Calude, Marcus & Tevy 1979.
  3. ↑ Sudan 1927.

Bibliography

  • 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. 
  • Sudan, Gabriel (1927). "Sur le nombre transfini ωω". Bulletin mathématique de la Société Roumaine des Sciences 30: 11–30. "Jbuch 53, 171". 

External links

  • OEIS: A260003, A260004




Retrieved from "https://handwiki.org/wiki/index.php?title=Sudan_function&oldid=3368760"