Sudanfunktion

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Sudanfunktion ist eine rekursive berechenbare Funktion, die total μ-rekursiv, jedoch nicht primitiv rekursiv ist, was sie mit der bekannteren Ackermannfunktion gemeinsam hat.

Sie wurde 1927 von dem rumänischen Mathematiker Gabriel Sudan publiziert, der wie Wilhelm Ackermann ein Schüler David Hilberts war.

Für gilt:

1926 vermutete David Hilbert, dass jede berechenbare Funktion primitiv-rekursiv sei. Dies wurde durch Wilhelm Ackermann und Gabriel Sudan – beides seine Schüler – mittels unterschiedlichen Funktionen, die zeitnah (Sudan 1927 und Ackermann 1928) publiziert wurden, widerlegt. Die Sudanfunktion und die Ackermannfunktion waren so die ersten veröffentlichten, nicht primitiv rekursiven Funktionen.

F0 lässt sich geschlossen darstellen als:  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

F1 lässt sich geschlossen darstellen als:  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

F2 lässt sich nicht mehr allgemein geschlossen darstellen.

Für gegebene y lässt es sich geschlossen darstellen, wobei die Ausdrücke schnell längere Ausdrücke werden.

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 2284
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
längerer Ausdruck, fängt mit 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
noch längerer Ausdruck, fängt mit 2222x+1 an,  ≈ 10101010lg 2·(x+1) + lg(x+2)

F3 lässt sich nicht mehr geschlossen darstellen.

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
keine geschlossenen Ausdrücke im Rahmen normaler mathematischer Notation möglich
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)
 
keine geschlossenen Ausdrücke im Rahmen normaler mathematischer Notation möglich