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.^[1]​La función de Sudán fue la primera función con dicha propiedad en ser publicada.^[2]​

Fue descubierta y publicada en 1927 por Gabriel Sudán,^[3]​ 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:

${\displaystyle {\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₀

${\displaystyle F_{0}(x,y)=x y}$

Valores de F₁

${\displaystyle F_{1}(x,y)=2y\cdot (x 2)-y-2}$

Valores de F₂

Valores de F₃

Notas y referencias

Bibliografía

Enlaces externos

• OEIS: A260003, A260004