# Función de Sudán

En la teoría de la computación, la función de Sudán es un ejemplo de una función recursiva que no es recursiva primitiva, la misma categoría a la cual pertenece la más conocida función de Ackermann.La función de Sudán fue la primera función con dicha propiedad en ser publicada.
Fue descubierta y publicada en 1927 por Gabriel Sudán, un matemático rumano que fue alumno del matemático David Hilbert.

## Definición

La función de Sudán puede definirse de la siguiente manera:
    ${\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}}$

## Tabla de valores
### Valores de 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 |

### Valores de F$_1$

$F_{1}(x,y)=2y\cdot (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 |

### Valores de 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}$ |
| expresión más larga, comienza con 2$^{22x+1}$ , ≈ 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}$ | | | | | | | |
| expresión mucho más larga, comienza con 2$^{222x+1}$ ≈ 10$^{101010lg2·(x+1)+lg(x+2)}$ ||||||||

### Valores de F$_3$

| $_y$ \ $^X$ | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 1 | 2 | 3 | 4 |
| X |||||
| 1 | F $_2$ (F $_3$ (0, 0), </br>F $_3$ (0, 0)+1) | F $_2$ (F $_3$ (1, 0), </br>F $_3$ (1, 0)+1) | F $_2$ (F $_3$ (2, 0), </br>F $_3$ (2, 0)+1) | F $_2$ (F $_3$ (3, 0), </br>F $_3$ (3, 0)+1) | F $_2$ (F $_3$ (4, 0), </br>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 es posible usar expresiones cerradas usando notación matemática normal. |||||
| 2 | F $_3$ (F $_4$ (0, 1), </br>F $_4$ (0, 1)+2) | F $_3$ (F $_4$ (1, 1), </br>F $_4$ (1, 1)+2) | F $_3$ (F $_4$ (2, 1), </br>F $_4$ (2, 1)+2) | F $_3$ (F $_4$ (3, 1), </br>F $_4$ (3, 1)+2) | F $_3$ (F $_4$ (4, 1), </br>F $_4$ (4, 1)+2) |
| 2 | F $_3$ (1, 3) | F $_3$ (10228, 10230) | F $_3$ (≈10 $^{4686813201}$ , </br>≈10 $^{4686813201}$ ) | | |
| No es posible usar expresiones cerradas usando notación matemática normal. |||||

## Notas y referencias

* ↑ Ackermann, 1928.
* ↑ Calude, Marcus y Tevy, 1979.
* ↑ Sudan, 1927.

## Bibliografía

* Ackermann, Wilhelm (1928). «Zum Hilbertschen Aufbau der reellen Zahlen». Mathematische Annalen 99: 118-133. JFM 54.0056.06. S2CID 123431274. doi:10.1007/BF01459088.
* Calude, Cristian; Marcus, Solomon; Tevy, Ionel (1979). «The first example of a recursive function which is not primitive recursive». Historia Mathematica 6 (4): 380-384. doi:10.1016/0315-0860(79)90024-7.
* Sudan, Gabriel (1927). «Sur le nombre transfini ω$^ω$». Bulletin mathématique de la Société Roumaine des Sciences 30: 11-30. JFM 53.0171.01. JSTOR 43769875. «Jbuch 53, 171».