Función de Sudán

En la teoría de la computación , la función Sudan es un ejemplo de función recursiva , pero no recursiva primitiva . Esto también es cierto en el caso de la función de Ackermann, más conocida .

En 1926, David Hilbert conjeturó que toda función computable era recursiva primitiva. Esto fue refutado por Gabriel Sudan y Wilhelm Ackermann —ambos estudiantes suyos— utilizando diferentes funciones que fueron publicadas en rápida sucesión: Sudan en 1927, ^[1] Ackermann en 1928. ^[2]

La función Sudán es el primer ejemplo publicado de una función recursiva que no es recursiva primitiva. ^[3]

Definición

${\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}}}$

La última ecuación se puede escribir de forma equivalente como

${\displaystyle {\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}}}$. ^[4]

Cálculo

Estas ecuaciones se pueden utilizar como reglas de un sistema de reescritura de términos (TRS) .

La función generalizada conduce a las reglas de reescritura. ${\displaystyle F(x,y,n){\stackrel {\mathrm {def} }{=}}F_{n}(x,y)}$

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

En cada paso de reducción se reescribe la ocurrencia más interna a la derecha de F, mediante la aplicación de una de las reglas (r1) - (r3).

Calude (1988) da un ejemplo : computar . ^[5] ${\displaystyle F(2,2,1)\rightarrow _{*}12}$

La secuencia de reducción es ^[6]

Tablas de valores

Valores de F0

F ₀ ( x ,  y ) = x + y

Valores de F1

F ₁ ( x ,  y ) = 2 ^y  · (x + 2) − y − 2

Valores de F2

Valores de F3

Notas y referencias

1. Sudán 1927.
2. Ackermann 1928.
3. Calude, Marcus y Tevy 1979.
4. Calude 1988, pág. 92.
5. Calude 1988, págs. 92–95.
6. Las ocurrencias más internas de F situadas más a la derecha están subrayadas.

Bibliografía

• Ackermann , Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Annalen Matemáticas . 99 : 118-133. doi :10.1007/BF01459088. JFM  54.0056.06. S2CID  123431274.

• Calude, Cristian ; Marcus, Solomon ; Tevy, Ionel (1979). "El primer ejemplo de una función recursiva que no es recursiva primitiva". Historia Mathematica . 6 (4): 380–384. doi : 10.1016/0315-0860(79)90024-7 .

• Calude, Cristian (1988). Teorías de la complejidad computacional. Ámsterdam: North-Holland . ISBN 978-0-444-70356-9.

• Sudán , Gabriel (1927). "Sur le nombre transfini ω ^ω ". Boletín matemático de la Société Roumaine des Sciences . 30 : 11–30. JFM  53.0171.01. JSTOR  43769875. Libro 53, 171

Enlaces externos

• Código Rosetta (23 de julio de 2024). «Función Sudán».

• Normas internacionales de la UE: A260003, A260004