imported>InkoBot: Bot: Ersetze hartkodierte Farbangabe durch Farbklasse

2025-04-25T19:54:57Z

Bot: Ersetze hartkodierte Farbangabe durch Farbklasse

Neue Seite

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

Sie wurde 1927 von dem [[Rumänien|rumänischen]] [[Mathematiker]] [[Gabriel Sudan]] publiziert, der wie [[Wilhelm Ackermann (Mathematiker)|Wilhelm Ackermann]] ein Schüler [[David Hilbert]]s war.

== Definition ==
Für <math>x, y, n \in \N_0</math> gilt:

:<math>F_0 (x, y) = x+y,\,</math>

:<math>F_{n+1} (x, 0) = x, \ n \ge 0\,</math>

:<math>F_{n+1} (x, y+1) = F _n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1), \ n\ge 0.\,</math>

== Hintergrund ==
1926 vermutete [[David Hilbert]], dass jede [[berechenbare Funktion]] [[Primitiv-rekursive 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-rekursive Funktion|primitiv rekursiv]]en Funktionen.

== Wertetabellen ==

=== Werte von F0 ===
F0 lässt sich geschlossen darstellen als:  ''F''0(''x'', ''y'') = x + y
{| class="wikitable" style="text-align:right; font-size:100%"
|-
! <big>''y'' \ ''x''</big> !! 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 ===
''F1'' lässt sich geschlossen darstellen als:  ''F''1(''x'', ''y'') = 2y · (x + 2) − y − 2
{| class="wikitable" style="text-align:right; font-size:95%"
|-
! <big>''y'' \ ''x''</big> !! 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 ===
''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.
{| class="wikitable" style="text-align:right; font-size:90%"
|-
! <big>''y'' \ ''x''</big> !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
|-
! rowspan="2" | 0
| 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
| colspan="8" style="text-align:center; background:#FAF7F4" | ''x''
|-
! rowspan="4" | 1
| F1 (F2(0, 0),&emsp;  F2(0, 0)+1)
| F1 (F2(1, 0),&emsp;  F2(1, 0)+1)
| F1 (F2(2, 0),&emsp;  F2(2, 0)+1)
| F1 (F2(3, 0),&emsp;  F2(3, 0)+1)
| F1 (F2(4, 0),&emsp;  F2(4, 0)+1)
| F1 (F2(5, 0),&emsp;  F2(5, 0)+1)
| F1 (F2(6, 0),&emsp;  F2(6, 0)+1)
| F1 (F2(7, 0),&emsp;  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
|-
| colspan="8" style="text-align:center; background:#FAF7F4" | ''2x+1 · (x + 2) − x − 3'' ≈ 10lg 2·(x+1) + lg(x+2)
|-
! rowspan="4" | 2
| F1 (F2(0, 1),&emsp;  F2(0, 1)+2)
| F1 (F2(1, 1),&emsp;  F2(1, 1)+2)
| F1 (F2(2, 1),&emsp;  F2(2, 1)+2)
| F1 (F2(3, 1),&emsp;  F2(3, 1)+2)
| F1 (F2(4, 1),&emsp;  F2(4, 1)+2)
| F1 (F2(5, 1),&emsp;  F2(5, 1)+2)
| F1 (F2(6, 1),&emsp;  F2(6, 1)+2)
| F1 (F2(7, 1),&emsp;  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
|-
| colspan="8" style="text-align:center; background:#FAF7F4" | 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)&emsp; ≈ 10lg 2 · 2x+1·(x+2) + lg(2x+1·(x+2))&emsp; ≈ 10lg 2 · (2x+1·(x+2)) = 1010lg lg 2 + lg 2·(x+1) + lg(x+2)&emsp;≈ 1010lg 2·(x+1) + lg(x+2)
|-
! rowspan="5" | 3
| F1 (F2(0, 2),&emsp;  F2(0, 2)+3)
| F1 (F2(1, 2),&emsp;  F2(1, 2)+3)
| F1 (F2(2, 2),&emsp;  F2(2, 2)+3)
| F1 (F2(3, 2),&emsp;  F2(3, 2)+3)
| F1 (F2(4, 2),&emsp;  F2(4, 2)+3)
| F1 (F2(5, 2),&emsp;  F2(5, 2)+3)
| F1 (F2(6, 2),&emsp;  F2(6, 2)+3)
| F1 (F2(7, 2),&emsp;  F2(7, 2)+3)
|-
| F1(F1(1,3),&emsp;  F1(1,3)+3)
| F1(F1(8,10),&emsp;  F1(8,10)+3)
| F1(F1(27,29),&emsp;  F1(27,29)+3)
| F1(F1(74,76),&emsp;  F1(74,76)+3)
| F1(F1(185,187),&emsp;  F1(185,187)+3)
| F1(F1(440,442),&emsp;  F1(440,442)+3)
| F1(F1(1015,1017),&emsp;  F1(1015,1017)+3)
| F1(F1(2294,2297),&emsp;  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
|-
| colspan="8" style="text-align:center; background:#FAF7F4" | längerer Ausdruck, fängt mit 222x+1 an, &emsp;≈ 101010lg 2·(x+1) + lg(x+2)
|-
! rowspan="5" | 4
| F1 (F2(0, 3),&emsp;  F2(0, 3)+4)
| F1 (F2(1, 3),&emsp;  F2(1, 3)+4)
| F1 (F2(2, 3),&emsp;  F2(2, 3)+4)
| F1 (F2(3, 3),&emsp;  F2(3, 3)+4)
| F1 (F2(4, 3),&emsp;  F2(4, 3)+4)
| F1 (F2(5, 3),&emsp;  F2(5, 3)+4)
| F1 (F2(6, 3),&emsp;  F2(6, 3)+4)
| F1 (F2(7, 3),&emsp;  F2(7, 3)+4)
|-
| F1 (F1(19, 22),&emsp;  F1(19, 22)+4)
| F1 (F1(10228,&emsp;  10231),&emsp;  F1(10228,&emsp;  10231)+4)
| F1 (F1(15569256417,&emsp;  15569256420),&emsp;  F1(15569256417,&emsp;  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) || colspan="6" class="hintergrundfarbe-basis" style="border:0;" |
|-
| ≈ 3,5 · 1026514839 || colspan="7" class="hintergrundfarbe-basis" style="border:0;" |
|-
| colspan="8" style="text-align:center; background:#FAF7F4" | noch längerer Ausdruck, fängt mit 2222x+1 an, &emsp;≈ 10101010lg 2·(x+1) + lg(x+2)
|}

=== Werte von F3 ===
''F3'' lässt sich nicht mehr geschlossen darstellen.
{| class="wikitable" style="text-align:right; font-size:90%"
|-
! <big>''y'' \ ''x''</big> !! 0 !! 1 !! 2 !! 3 !! 4
|-
! rowspan="2" | 0
| 0 || 1 || 2 || 3 || 4
|-
| colspan="5" style="text-align:center; background:#FAF7F4" | ''x''
|-
! rowspan="4" | 1
| F2 (F3(0, 0),&emsp;  F3(0, 0)+1)
| F2 (F3(1, 0),&emsp;  F3(1, 0)+1)
| F2 (F3(2, 0),&emsp;  F3(2, 0)+1)
| F2 (F3(3, 0),&emsp;  F3(3, 0)+1)
| F2 (F3(4, 0),&emsp;  F3(4, 0)+1)
|-
| F2(0, 1)
| F2(1, 2)
| F2(2, 3)
| F2(3, 4)
| F2(4, 5)
|-
| 1
| 10228
| ≈ 7,82 · 104686813201
| class="hintergrundfarbe-basis" colspan="2" |
|-
| colspan="5" style="text-align:center; background:#FAF7F4" | keine geschlossenen Ausdrücke im Rahmen normaler mathematischer Notation möglich
|-
! rowspan="4" | 2
| F3 (F4(0, 1),&emsp;  F4(0, 1)+2)
| F3 (F4(1, 1),&emsp;  F4(1, 1)+2)
| F3 (F4(2, 1),&emsp;  F4(2, 1)+2)
| F3 (F4(3, 1),&emsp;  F4(3, 1)+2)
| F3 (F4(4, 1),&emsp;  F4(4, 1)+2)
|-
| F3 (1, 3)
| F3 (10228, 10230)
| F3 (≈104686813201,  ≈104686813201)
| class="hintergrundfarbe-basis" colspan="2" |
|-
| class="hintergrundfarbe-basis" colspan="5" |  
|-
| colspan="5" style="text-align:center; background:#FAF7F4" | keine geschlossenen Ausdrücke im Rahmen normaler mathematischer Notation möglich
|}

== Literatur ==
*Gabriel Sudan: ''Sur le nombre transfini ωω.'' Bulletin Math. Soc. Roumaine des sciences 30, S. 11–30 (1927). [http://www.zentralblatt-math.org/zmath/en/advanced/?q=an:53.0171.01 JFM review]
*Wilhelm Ackermann: ''Zum Hilbertschen Aufbau der reellen Zahlen.'' [[Mathematische Annalen]] 99, S. 118–133 (1928). [http://www.zentralblatt-math.org/zmath/en/advanced/?q=an:54.0056.06 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}}

[[Kategorie:Berechenbarkeitstheorie]]
[[Kategorie:Mathematische Funktion]]

Sudanfunktion - Versionsgeschichte

imported>InkoBot: Bot: Ersetze hartkodierte Farbangabe durch Farbklasse