# Sudan function

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.
In 1926, David Hilbert conjectured that every computable function was primitive recursive. This was refuted by Gabriel Sudan and Wilhelm Ackermann — both his students — using different functions that were published in quick succession: Sudan in 1927, Ackermann in 1928.
The Sudan function is the earliest published example of a recursive function that is not primitive recursive.

## Definition

    ${\begin{array}{lll}F_{0}(x,y)&=x+y\\F_{n+1}(x,0)&=x&{\text{if }}n\geq 0\\F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)&{\text{if }}n\geq 0\\\end{array}}$
The last equation can be equivalently written as
    ${\begin{array}{lll}F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{0}(F_{n+1}(x,y),y+1))\\\end{array}}$.

## Computation

These equations can be used as rules of a term rewriting system (TRS).
The generalized function $F(x,y,n){\stackrel {\mathrm {def} }{=}}F_{n}(x,y)$ leads to the rewrite rules
    ${\begin{array}{lll}{\text{(r1)}}&F(x,y,0)&\rightarrow x+y\\{\text{(r2)}}&F(x,0,n+1)&\rightarrow x\\{\text{(r3)}}&F(x,y+1,n+1)&\rightarrow F(F(x,y,n+1),F(F(x,y,n+1),y+1,0),n)\\\end{array}}$
At each reduction step the rightmost innermost occurrence of F is rewritten, by application of one of the rules (r1) - (r3).
Calude (1988) gives an example: compute $F(2,2,1)\rightarrow _{*}12$.
The reduction sequence is
    ${\underline {F(2,2,1)}}$  $\rightarrow _{r3}F(F(2,1,1),F({\underline {F(2,1,1)}},2,0),0)$  $\rightarrow _{r3}F(F(2,1,1),F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),2,0),0)$  $\rightarrow _{r2}F(F(2,1,1),F(F(F(2,0,1),{\underline {F(2,1,0)}},0),2,0),0)$  $\rightarrow _{r1}F(F(2,1,1),F(F({\underline {F(2,0,1)}},3,0),2,0),0)$  $\rightarrow _{r2}F(F(2,1,1),F({\underline {F(2,3,0)}},2,0),0)$  $\rightarrow _{r1}F(F(2,1,1),{\underline {F(5,2,0)}},0)$  $\rightarrow _{r1}F({\underline {F(2,1,1)}},7,0)$  $\rightarrow _{r3}F(F(F(2,0,1),F({\underline {F(2,0,1)}},1,0),0),7,0)$  $\rightarrow _{r2}F(F(F(2,0,1),{\underline {F(2,1,0)}},0),7,0)$  $\rightarrow _{r1}F(F({\underline {F(2,0,1)}},3,0),7,0)$  $\rightarrow _{r2}F({\underline {F(2,3,0)}},7,0)$  $\rightarrow _{r1}{\underline {F(5,7,0)}}$  $\rightarrow _{r1}12$

## Value tables
### Values of F$_0$

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 |

### Values of F$_1$

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 |

### Values of F$_2$

| $_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 | 2294 |
| 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}$ |
| longer expression, starts with 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}$ | | | | | | | |
| much longer expression, starts with 2$^{222x+1}$ an, ≈ 10$^{101010lg2·(x+1)+lg(x+2)}$ ||||||||

### Values of F$_3$

| $_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}$ | | |
| No closed expressions possible within the framework of normal mathematical notation |||||
| 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}$) | | |
| No closed expressions possible within the framework of normal mathematical notation |||||