Función de Sudán
# 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. Parámetro desconocido |doi-access= ignorado (ayuda)
* 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 ».
