Función de Sudán

En la teoría de la computación , la función Sudan es un ejemplo de una función recursiva , pero no recursiva primitiva . Esto también se aplica a la función 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 se publicaron en rápida sucesión: Sudan en 1927, ^{[ 1 ]} Ackermann en 1928. ^{[ 2 ]}

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

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

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 ]}

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

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

${\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, la ocurrencia más interna más a la derecha de F se reescribe mediante la aplicación de una de las reglas (r1) - (r3).

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

La secuencia de reducción es ^{[ 6 ]}

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

• OEIS: A260003 , A260004