Sudanfunktion
# 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

Für $x,y,n\in \mathbb {N} _{0}$ gilt:

    $F_{0}(x,y)=x+y,\,$
    $F_{n+1}(x,0)=x,\ n\geq 0\,$
    $F_{n+1}(x,y+1)=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1),\ n\geq 0.\,$

## Hintergrund

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

### Werte von $F_0$

$F_0$ lässt sich geschlossen darstellen als: $F_0(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 $F_1$

$F_1$ lässt sich geschlossen darstellen als: $F_1(x,$ y) = $2^y$ · (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 $F_2$

$F_2$ 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 | $F_1$ $(F_2(0,$ 0),   $F_2(0,$ 0)+1) | $F_1$ $(F_2(1,$ 0),   $F_2(1,$ 0)+1) | $F_1$ $(F_2(2,$ 0),   $F_2(2,$ 0)+1) | $F_1$ $(F_2(3,$ 0),   $F_2(3,$ 0)+1) | $F_1$ $(F_2(4,$ 0),   $F_2(4,$ 0)+1) | $F_1$ $(F_2(5,$ 0),   $F_2(5,$ 0)+1) | $F_1$ $(F_2(6,$ 0),   $F_2(6,$ 0)+1) | $F_1$ $(F_2(7,$ 0),   $F_2(7,$ 0)+1) |
| 1 | $F_1(0,$ 1) | $F_1(1,$ 2) | $F_1(2,$ 3) | $F_1(3,$ 4) | $F_1(4,$ 5) | $F_1(5,$ 6) | $F_1(6,$ 7) | $F_1(7,$ 8) |
| 1 | 1 | 8 | 27 | 74 | 185 | 440 | 1015 | 2284 |
| $2^{x+1}$ · (x + 2) − x − 3 ≈ $10^{lg2·(x+1)+lg(x+2)}$ ||||||||
| 2 | $F_1$ $(F_2(0,$ 1),   $F_2(0,$ 1)+2) | $F_1$ $(F_2(1,$ 1),   $F_2(1,$ 1)+2) | $F_1$ $(F_2(2,$ 1),   $F_2(2,$ 1)+2) | $F_1$ $(F_2(3,$ 1),   $F_2(3,$ 1)+2) | $F_1$ $(F_2(4,$ 1),   $F_2(4,$ 1)+2) | $F_1$ $(F_2(5,$ 1),   $F_2(5,$ 1)+2) | $F_1$ $(F_2(6,$ 1),   $F_2(6,$ 1)+2) | $F_1$ $(F_2(7,$ 1),   $F_2(7,$ 1)+2) |
| 2 | $F_1(1,$ 3) | $F_1(8,$ 10) | $F_1(27,$ 29) | $F_1(74,$ 76) | $F_1(185,$ 187) | $F_1(440,$ 442) | $F_1(1015,$ 1017) | $F_1(2294,$ 2296) |
| 2 | 19 | 10228 | 15569256417 | ≈ 5,742397643 · $10^{24}$ | ≈ 3,668181327 · $10^{58}$ | ≈ 5,019729940 · $10^{135}$ | ≈ 1,428323374 · $10^{309}$ | ≈ 3,356154368 · $10^{694}$ |
| $2^{2x+1·(x+2)−x−1}$ · $(2^{x+1}·(x+2)$ − x − 1) − $(2^{x+1}·(x+2)$ − x + 1) ≈ $10^{lg2·(2x+1·(x+2)−x−1)+lg(2x+1·(x+2)−x−1)}$  ≈ $10^{lg2·2x+1·(x+2)+lg(2x+1·(x+2))}$  ≈ $10^{lg2·(2x+1·(x+2))}$ = $10^{10lglg2+lg2·(x+1)+lg(x+2)}$ ≈ $10^{10lg2·(x+1)+lg(x+2)}$ ||||||||
| 3 | $F_1$ $(F_2(0,$ 2),   $F_2(0,$ 2)+3) | $F_1$ $(F_2(1,$ 2),   $F_2(1,$ 2)+3) | $F_1$ $(F_2(2,$ 2),   $F_2(2,$ 2)+3) | $F_1$ $(F_2(3,$ 2),   $F_2(3,$ 2)+3) | $F_1$ $(F_2(4,$ 2),   $F_2(4,$ 2)+3) | $F_1$ $(F_2(5,$ 2),   $F_2(5,$ 2)+3) | $F_1$ $(F_2(6,$ 2),   $F_2(6,$ 2)+3) | $F_1$ $(F_2(7,$ 2),   $F_2(7,$ 2)+3) |
| 3 | $F_1(F_1(1,3),$   $F_1(1,3)+3)$ | $F_1(F_1(8,10),$   $F_1(8,10)+3)$ | $F_1(F_1(27,29),$   $F_1(27,29)+3)$ | $F_1(F_1(74,76),$   $F_1(74,76)+3)$ | $F_1(F_1(185,187),$   $F_1(185,187)+3)$ | $F_1(F_1(440,442),$   $F_1(440,442)+3)$ | $F_1(F_1(1015,1017),$   $F_1(1015,1017)+3)$ | $F_1(F_1(2294,2297),$   $F_1(2294,2297)+3)$ |
| 3 | $F_1(19,$ 22) | $F_1(10228,$ 10231) | $F_1(15569256417,$ 15569256420) | $F_1(≈6·10^{24},$ $≈6·10^{24})$ | $F_1(≈4·10^{58},$ $≈4·10^{58})$ | $F_1(≈5·10^{135},$ $≈5·10^{135})$ | $F_1(≈10^{309},$ $≈10^{309})$ | $F_1(≈3·10^{694},$ $≈3·10^{694})$ |
| 3 | 88080360 | ≈ 7,04 · $10^{3083}$ | ≈ 7,82 · $10^{4686813201}$ | ≈ $10^{1,72·1024}$ | ≈ $10^{1,10·1058}$ | ≈ $10^{1,51·10135}$ | ≈ $10^{4,30·10308}$ | ≈ $10^{1,01·10694}$ |
| längerer Ausdruck, fängt mit $2^{22x+1}$ an,  ≈ $10^{1010lg2·(x+1)+lg(x+2)}$ ||||||||
| 4 | $F_1$ $(F_2(0,$ 3),   $F_2(0,$ 3)+4) | $F_1$ $(F_2(1,$ 3),   $F_2(1,$ 3)+4) | $F_1$ $(F_2(2,$ 3),   $F_2(2,$ 3)+4) | $F_1$ $(F_2(3,$ 3),   $F_2(3,$ 3)+4) | $F_1$ $(F_2(4,$ 3),   $F_2(4,$ 3)+4) | $F_1$ $(F_2(5,$ 3),   $F_2(5,$ 3)+4) | $F_1$ $(F_2(6,$ 3),   $F_2(6,$ 3)+4) | $F_1$ $(F_2(7,$ 3),   $F_2(7,$ 3)+4) |
| 4 | $F_1$ $(F_1(19,$ 22),   $F_1(19,$ 22)+4) | $F_1$ $(F_1(10228,$  10231),   $F_1(10228,$  10231)+4) | $F_1$ $(F_1(15569256417,$  15569256420),   $F_1(15569256417,$  15569256420)+4) | $F_1$ $(F_1(≈5,74·10^{24},$ $≈5,74·10^{24}),$ $F_1(≈5,74·10^{24},$ $≈5,74·10^{24}))$ | $F_1$ $(F_1(≈3,67·10^{58},$ $≈3,67·10^{58}),$ $F_1(≈3,67·10^{58},$ $≈3,67·10^{58}))$ | $F_1$ $(F_1(≈5,02·10^{135},$ $≈5,02·10^{135}),$ $F_1(≈5,02·10^{135},$ $≈5,02·10^{135}))$ | $F_1$ $(F_1(≈1,43·10^{309},$ $≈1,43·10^{309}),$ $F_1(≈1,43·10^{309},$ $≈1,43·10^{309}))$ | $F_1$ $(F_1(≈3,36·10^{694},$ $≈3,36·10^{694}),$ $F_1(≈3,36·10^{694},$ $≈3,36·10^{694}))$ |
| 4 | $F_1(88080360,$ 88080364) | $F_1(10230·2^{10231}−10233,$ $10230·2^{10231}−10229)$ | | | | | | |
| 4 | ≈ 3,5 · $10^{26514839}$ | | | | | | | |
| noch längerer Ausdruck, fängt mit $2^{222x+1}$ an,  ≈ $10^{101010lg2·(x+1)+lg(x+2)}$ ||||||||

### Werte von $F_3$

$F_3$ lässt sich nicht mehr geschlossen darstellen.

| $_y$ \ $^x$ | 0 | 1 | 2 | 3 | 4 |
| - | - | - | - | - | - |
| 0 | 0 | 1 | 2 | 3 | 4 |
| x |||||
| 1 | $F_2$ $(F_3(0,$ 0),   $F_3(0,$ 0)+1) | $F_2$ $(F_3(1,$ 0),   $F_3(1,$ 0)+1) | $F_2$ $(F_3(2,$ 0),   $F_3(2,$ 0)+1) | $F_2$ $(F_3(3,$ 0),   $F_3(3,$ 0)+1) | $F_2$ $(F_3(4,$ 0),   $F_3(4,$ 0)+1) |
| 1 | $F_2(0,$ 1) | $F_2(1,$ 2) | $F_2(2,$ 3) | $F_2(3,$ 4) | $F_2(4,$ 5) |
| 1 | 1 | 10228 | ≈ 7,82 · $10^{4686813201}$ | | |
| keine geschlossenen Ausdrücke im Rahmen normaler mathematischer Notation möglich |||||
| 2 | $F_3$ $(F_4(0,$ 1),   $F_4(0,$ 1)+2) | $F_3$ $(F_4(1,$ 1),   $F_4(1,$ 1)+2) | $F_3$ $(F_4(2,$ 1),   $F_4(2,$ 1)+2) | $F_3$ $(F_4(3,$ 1),   $F_4(3,$ 1)+2) | $F_3$ $(F_4(4,$ 1),   $F_4(4,$ 1)+2) |
| 2 | $F_3$ (1, 3) | $F_3$ (10228, 10230) | $F_3$ $(≈10^{4686813201},$  $≈10^{4686813201})$ | | |
| keine geschlossenen Ausdrücke im Rahmen normaler mathematischer Notation möglich |||||
