www.wikidata.de-de.nina.az

Sudanfunktion Die ist eine rekursive berechenbare Funktion die total μ rekursiv jedoch nicht primitiv rekursiv ist was s

Sudanfunktion

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.

Definition Bearbeiten

Für gilt:

Hintergrund Bearbeiten

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.

Wertetabellen Bearbeiten

Werte von F0 Bearbeiten

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

Werte von F1 Bearbeiten

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

Werte von F2 Bearbeiten

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)

Werte von F3 Bearbeiten

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

Literatur Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Sudanfunktion ist eine rekursive berechenbare Funktion die total m rekursiv jedoch nicht primitiv rekursiv ist was sie mit der bekannteren Ackermannfunktion gemeinsam hat Sie wurde 1927 von dem rumanischen Mathematiker Gabriel Sudan publiziert der wie Wilhelm Ackermann ein Schuler David Hilberts war Inhaltsverzeichnis 1 Definition 2 Hintergrund 3 Wertetabellen 3 1 Werte von F0 3 2 Werte von F1 3 3 Werte von F2 3 4 Werte von F3 4 LiteraturDefinition BearbeitenFur x y n N 0 displaystyle x y n in mathbb N 0 nbsp gilt F 0 x y x y displaystyle F 0 x y x y nbsp F n 1 x 0 x n 0 displaystyle F n 1 x 0 x n geq 0 nbsp F n 1 x y 1 F n F n 1 x y F n 1 x y y 1 n 0 displaystyle F n 1 x y 1 F n F n 1 x y F n 1 x y y 1 n geq 0 nbsp Hintergrund Bearbeiten1926 vermutete David Hilbert dass jede berechenbare Funktion primitiv rekursiv sei Dies wurde durch Wilhelm Ackermann und Gabriel Sudan beides seine Schuler mittels unterschiedlichen Funktionen die zeitnah Sudan 1927 und Ackermann 1928 publiziert wurden widerlegt Die Sudanfunktion und die Ackermannfunktion waren so die ersten veroffentlichten nicht primitiv rekursiven Funktionen Wertetabellen BearbeitenWerte von F0 Bearbeiten F0 lasst sich geschlossen darstellen als F0 x y x y y x 0 1 2 3 4 5 6 7 8 9 100 0 1 2 3 4 5 6 7 8 9 101 1 2 3 4 5 6 7 8 9 10 112 2 3 4 5 6 7 8 9 10 11 123 3 4 5 6 7 8 9 10 11 12 134 4 5 6 7 8 9 10 11 12 13 145 5 6 7 8 9 10 11 12 13 14 156 6 7 8 9 10 11 12 13 14 15 167 7 8 9 10 11 12 13 14 15 16 178 8 9 10 11 12 13 14 15 16 17 189 9 10 11 12 13 14 15 16 17 18 1910 10 11 12 13 14 15 16 17 18 19 20Werte von F1 Bearbeiten F1 lasst sich geschlossen darstellen als F1 x y 2y x 2 y 2 y x 0 1 2 3 4 5 6 7 8 9 100 0 1 2 3 4 5 6 7 8 9 101 1 3 5 7 9 11 13 15 17 19 212 4 8 12 16 20 24 28 32 36 40 443 11 19 27 35 43 51 59 67 75 83 914 26 42 58 74 90 106 122 138 154 170 1865 57 89 121 153 185 217 249 281 313 345 3776 120 184 248 312 376 440 504 568 632 696 7607 247 375 503 631 759 887 1015 1143 1271 1399 15278 502 758 1014 1270 1526 1782 2038 2294 2550 2806 30629 1013 1525 2037 2549 3061 3573 4085 4597 5109 5621 613310 2036 3060 4084 5108 6132 7156 8180 9204 10228 11252 12276Werte von F2 Bearbeiten F2 lasst sich nicht mehr allgemein geschlossen darstellen Fur gegebene y lasst es sich geschlossen darstellen wobei die Ausdrucke schnell langere Ausdrucke werden y x 0 1 2 3 4 5 6 70 0 1 2 3 4 5 6 7x1 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 22842x 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 1069422x 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 10694langerer Ausdruck fangt 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 1026514839noch langerer Ausdruck fangt mit 2222x 1 an 10101010lg 2 x 1 lg x 2 Werte von F3 Bearbeiten F3 lasst sich nicht mehr geschlossen darstellen y x 0 1 2 3 40 0 1 2 3 4x1 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 104686813201keine geschlossenen Ausdrucke im Rahmen normaler mathematischer Notation moglich2 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 Ausdrucke im Rahmen normaler mathematischer Notation moglichLiteratur BearbeitenGabriel Sudan Sur le nombre transfini ww Bulletin Math Soc Roumaine des sciences 30 S 11 30 1927 JFM review Wilhelm Ackermann Zum Hilbertschen Aufbau der reellen Zahlen Mathematische Annalen 99 S 118 133 1928 JFM review Cristian S Calude Solomon Marcus Ionel Tevy The first example of a recursive function which is not primitive recursive Historia Mathematica 6 1979 no 4 S 380 384 doi 10 1016 0315 0860 79 90024 7 Abgerufen von https de wikipedia org w index php title Sudanfunktion amp oldid 233499494