Función de Ackermann

format_list_bulleted Contenido keyboard_arrow_down
ImprimirCitar
Función de crecimiento rápido

En la teoría de la computabilidad, la función de Ackermann, llamada así por Wilhelm Ackermann, es uno de los ejemplos más simples y descubiertos más temprano de una función computable total que no es recursiva primitiva. Todas las funciones recursivas primitivas son totales y computables, pero la función de Ackermann ilustra que no todas las funciones computables totales son recursivas primitivas. Después de la publicación de Ackermann de su función (que tenía tres argumentos enteros no negativos), muchos autores la modificaron para adaptarse a varios propósitos, de modo que hoy en día "la función de Ackermann" puede referirse a cualquiera de las numerosas variantes de la función original. Una versión común, la función Ackermann-Péter de dos argumentos, se define de la siguiente manera para los enteros no negativos m y n:

A⁡ ⁡ ()0,n)=n+1A⁡ ⁡ ()m+1,0)=A⁡ ⁡ ()m,1)A⁡ ⁡ ()m+1,n+1)=A⁡ ⁡ ()m,A⁡ ⁡ ()m+1,n)){displaystyle {begin{array}{lcl}operatorname {A} (0,n) {A} (m+1,0) {A} (m,1)\fnMiembro {A} (m+1,n+1)

Su valor crece rápidamente, incluso para pequeñas entradas. Por ejemplo, A(4, 2) es un número entero de 19 729 dígitos decimales (equivalente a 265536−3, o 22222−3).

Historia

A finales de la década de 1920, los matemáticos Gabriel Sudán y Wilhelm Ackermann, estudiantes de David Hilbert, estaban estudiando las bases de la computación. Tanto Sudán como Ackermann se acreditan con el descubrimiento de funciones computables totales (terminadas simplemente "recursivas" en algunas referencias) que no son recursivas primitivas. Sudán publicó la función menos conocida del Sudán, después de poco tiempo e independientemente, en 1928, Ackermann publicó su función φ φ {displaystyle varphi } (la carta griega phi). La función de tres brazos de Ackermann, φ φ ()m,n,p){displaystyle varphi (m,n,p)}, se define de tal manera que p=0,1,2{displaystyle p=0,1,2}, reproduce las operaciones básicas de adición, multiplicación y exponenciación como

φ φ ()m,n,0)=m+nφ φ ()m,n,1)=m× × nφ φ ()m,n,2)=mn{displaystyle {begin{aligned}varphi (m,n,0) {=m+n\\varphi (m,n,1) limit=mtimes n\\varphi (m,n,2) limit=m^{n}end{aligned}}}}}}}}}

y para p > 2 extiende estas operaciones básicas de una manera que puede compararse con las hiperoperaciones:

3end{aligned}}}" xmlns="http://www.w3.org/1998/Math/MathML">φ φ ()m,n,3)=m[4]()n+1)φ φ ()m,n,p)⪆ ⪆ m[p+1]()n+1)parap■3{displaystyle {begin{aligned}varphi (m,n,3) limit=m[4](n+1)\varphi (m,n,p) conllevagtrapprox m[p+1](n+1) limitándose{text{for ¿Qué?3end{aligned}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/55d4772652d7289170cc00951d017f5ae1c25d5b" style="vertical-align: -2.505ex; width:43.007ex; height:6.176ex;"/>

(Además de su papel histórico como una función recursiva totalmente computable pero no primitiva, se considera que la función original de Ackermann extiende las operaciones aritméticas básicas más allá de la exponenciación, aunque no tan perfectamente como lo hacen las variantes de función de Ackermann que están diseñadas específicamente para ese propósito, como la secuencia de hiperoperación de Goodstein).

En Sobre el infinito, David Hilbert planteó la hipótesis de que la función de Ackermann no era recursiva primitiva, pero fue Ackermann, el secretario personal y antiguo alumno de Hilbert, quien demostró la hipótesis en su artículo Sobre la construcción de los números reales de Hilbert.

Rózsa Péter y Raphael Robinson desarrollaron más tarde una versión de dos variables de la función de Ackermann que se volvió preferida por casi todos los autores.

La secuencia generalizada de hiperoperación, por ejemplo. G()m,a,b)=a[m]b{displaystyle G(m,a,b)=a[m]b}, es una versión de la función Ackermann también.

En 1963 R.C. Buck basó una variante intuitiva de dos variables F{displaystyle operatorname {F} en la secuencia de hiperoperación:

F⁡ ⁡ ()m,n)=2[m]n.{displaystyle operatorname {F} (m,n)=2[m]n.}

En comparación con la mayoría de las otras versiones, la función de Buck no tiene compensaciones no esenciales:

F⁡ ⁡ ()0,n)=2[0]n=n+1F⁡ ⁡ ()1,n)=2[1]n=2+nF⁡ ⁡ ()2,n)=2[2]n=2× × nF⁡ ⁡ ()3,n)=2[3]n=2nF⁡ ⁡ ()4,n)=2[4]n=222...2⋮ ⋮ {displaystyle {begin{aligned}operatorname ################################################################################################################################################################################################################################################################ {F} (2,n) sentimiento=2[2]n=2times n\\\\f} (3,n) paciente=2[3]n=2^ {n}\\\\fnMicrosoft Sans {fnMicrosoft Sans Serif}}\\fnMicrosoft Sans Serif}\fnMicrosoft Sans Serif}}}\\\\fnMicrosoft Sans Serif} vdots end{aligned}}

Se han investigado muchas otras versiones de la función de Ackermann.

Definición

Definición: como función m-aria

Función original de tres brazos de Ackermann φ φ ()m,n,p){displaystyle varphi (m,n,p)} se define recursivamente como sigue para los enteros no negativos m,n,{displaystyle m,n,} y p{displaystyle p}:

2\varphi (m,n,p)&=varphi (m,varphi (m,n-1,p),p-1)&&{text{for }}n,p>0end{aligned}}}" xmlns="http://www.w3.org/1998/Math/MathML">φ φ ()m,n,0)=m+nφ φ ()m,0,1)=0φ φ ()m,0,2)=1φ φ ()m,0,p)=mparap■2φ φ ()m,n,p)=φ φ ()m,φ φ ()m,n− − 1,p),p− − 1)paran,p■0{displaystyle {begin{aligned}varphi (m,n,0) Sent=m+n\\varphi (m,0,1) limit=0\\varphi (m,0,2) limit=1\varphi (m,0,p) }p confía2\varphi (m,n,p) limitada=varphi (m,varphi (m,n-1,p),p-1) }n,p confía0end{aligned}}2\varphi (m,n,p)&=varphi (m,varphi (m,n-1,p),p-1)&&{text{for }}n,p>0end{aligned}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6855f9ddb1eb08206260d704b921e4a459da030" style="vertical-align: -7.171ex; width:56.337ex; height:15.509ex;"/>

De las diferentes versiones de dos águlos, la desarrollada por Péter y Robinson (llamada "la" función Ackermann por la mayoría de los autores) se define para los enteros no negativos m{displaystyle m} y n{displaystyle n} como sigue:

A⁡ ⁡ ()0,n)=n+1A⁡ ⁡ ()m+1,0)=A⁡ ⁡ ()m,1)A⁡ ⁡ ()m+1,n+1)=A⁡ ⁡ ()m,A()m+1,n)){displaystyle {begin{array}{lcl}operatorname {A} (0,n) {A} (m+1,0) {A} (m,1)\\fnMiembro {A} (m+1,n+1)

La función de Ackermann también se ha expresado en relación con la secuencia de hiperoperación:

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">A()m,n)={}n+1m=02[m]()n+3)− − 3m■0{displaystyle A(m,n)={begin{cases}n+1 limitm=02[m](n+3)-3 implicam confianza0\end{cases}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d74a51ad59c098733b952a52eff92e6fc38ded13" style="vertical-align: -2.505ex; width:37.945ex; height:6.176ex;"/>
o, escrito en la notación de arriba de Knuth (extended to integer indices ≥ ≥ − − 2{displaystyle geq -2}):
0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">={}n+1m=02↑ ↑ m− − 2()n+3)− − 3m■0{displaystyle ={begin{cases}n+1 limitadam=02uparrow ^{m-2}(n+3)-3 implicam confianza0\end{cases}}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6d5eb19389f023dbd9efd2fa3ed9c0a69948aecc" style="vertical-align: -2.505ex; width:32.172ex; height:6.176ex;"/>
o, equivalentemente, en términos de la función F de Buck:
0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">={}n+1m=0F()m,n+3)− − 3m■0{displaystyle ={begin{cases}n+1 limitadam=0F(m,n+3)-3 Pulsón0\end{cases}}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/49184cb225696100ff333a9e9632716bb2bb4c18" style="vertical-align: -2.505ex; width:29.597ex; height:6.176ex;"/>

Definición: como función iterada 1-aria

Define fn{displaystyle f^{n} como n- el itinerario f{displaystyle f}:

f0()x)=xfn+1()x)=f()fn()x)){}paran≥ ≥ 1}{f}f}f},,,,,,,,\,\\\f},, ngngn}f}f}f}f}f}f}f}f}f}f}f}f}f}f}

La iteración es el proceso de componer una función con sí mismo un cierto número de veces. La composición de la función es una operación asociativa, por lo que f()fn()x))=fn()f()x)){displaystyle f(f^{n}(x)=f^{n}(f(x)}.

Concibiendo la función Ackermann como una secuencia de funciones no deseadas, se puede establecer Am⁡ ⁡ ()n)=A⁡ ⁡ ()m,n){displaystyle operatorname {A} _{m}(n)=operatorname {A} (m,n)}.

La función entonces se convierte en una secuencia A0,A1,A2,...{displaystyle operatorname {A} _{0},operatorname [A] _{1},operatorname {A} _{2},...} of unary functions, defined from iteration:

A0⁡ ⁡ ()n)=n+1Am+1⁡ ⁡ ()n)=Amn+1⁡ ⁡ ()1){displaystyle {begin{array}{lcl}operatorname ################################################################################################################################################################################################################################################################ {A} _{m+1}(n) {fn} {fn} {fn}\\fn}}}}

Cálculo

La definición recursiva de la función de Ackermann se puede transponer naturalmente a un sistema de reescritura de términos (TRS).

TRS, basado en la función biaria

La definición de la función 2-aria de Ackermann conduce a las reglas de reducción obvias

(r1)A()0,n)→ → S()n)(r2)A()S()m),0)→ → A()m,S()0))(r3)A()S()m),S()n))→ → A()m,A()S()m),n)){begin{lll}{text{(r1)} {,n) âTMa âTMa âTMarightarrow & s(n)\\\text{(r2)} {} {m]} âTMa} âTMa} âTMa} âTMa} âTMa} âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa} âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa âTMa

Ejemplo

Computación A()1,2)→ → Alternativa Alternativa 4{displaystyle A(1,2)rightarrow ¿Qué?

La secuencia de reducción es

La estrategia más externa (un solo paso):Estrategia más interna (un paso):
A()S()0),S()S()0)))¿Qué? ¿Qué? {displaystyle {compline {A(S(0),S(S(0)}}}A()S()0),S()S()0)))¿Qué? ¿Qué? {displaystyle {compline {A(S(0),S(S(0)}}}
→ → r3A()0,A()S()0),S()0))¿Qué? ¿Qué? ){displaystyle rightarrow _{r3}{underline {A(0,A(S(0),S(0)}}} }→ → r3A()0,A()S()0),S()0))¿Qué? ¿Qué? ){displaystyle rightarrow _{r3}A(0,{underline {A(S(0),S(0)}}) }
→ → r1S()A()S()0),S()0))¿Qué? ¿Qué? ){displaystyle rightarrow _{r1}S({underline {A(S(0),S(0)}}} }→ → r3A()0,A()0,A()S()0),0)¿Qué? ¿Qué? )){displaystyle rightarrow _{r3}A(0,A(0,{underline {A(S(0),0)}})}}}
→ → r3S()A()0,A()S0,0))¿Qué? ¿Qué? ){displaystyle rightarrow _{r3}S({underline {A(0,A(S0,0)}}}}→ → r2A()0,A()0,A()0,S()0))¿Qué? ¿Qué? )){displaystyle rightarrow _{r2}A(0,A(0,{underline {A(0,S(0)}})}}}
→ → r1S()S()A()S()0),0)¿Qué? ¿Qué? )){displaystyle rightarrow _{r1}S(S({underline {A(S(0),0)})}}→ → r1A()0,A()0,S()S()0)))¿Qué? ¿Qué? ){displaystyle rightarrow _{r1}A(0,{underline {A(0,S(0))}}}}}
→ → r2S()S()A()0,S()0))¿Qué? ¿Qué? )){displaystyle rightarrow _{r2}S(S({underline {A(0,S(0)})}}}→ → r1A()0,S()S()S()0))))¿Qué? ¿Qué? {displaystyle rightarrow _{r1}{underline {A(0,S(S(0)))}}}
→ → r1S()S()S()S()0)))){displaystyle rightarrow _{r1}S(S(S(0))}→ → r1S()S()S()S()0)))){displaystyle rightarrow _{r1}S(S(S(0))}

Para calcular A⁡ ⁡ ()m,n){displaystyle operatorname {A} (m,n)} se puede utilizar una pila, que inicialmente contiene los elementos .. m,n.. {displaystyle langle m,nrangle }.

Luego, repetidamente, los dos elementos superiores se reemplazan de acuerdo con las reglas

(r1)0,n→ → ()n+1)(r2)()m+1),0→ → m,1(r3)()m+1),()n+1)→ → m,()m+1),n{displaystyle {begin {array}{lll}{text{(r1)} {}} {]} {]}} {m+1)}}} {text{(r2)}} {m+1)} {m+1)} {mm}}} {mm}}}} {mm}}}} {m}}}}} {m}}}}}}}}}}}}}}}} {m}}}}}}}}}}}}} {m}}}}}}} {m}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {m}}}}}}} {m}}} {m}}}} {m}}}}}}}} {m}}}}}}}}}}} {m}}}}}}}}}}}}}}}}}}}}}}}}}}

Esquemáticamente, a partir de .. m,n.. {displaystyle langle m,nrangle }:

WHILE stackLength 1
{}
 POP 2 elementos;
 PUSH 1 o 2 o 3 elementos, aplicando las reglas r1, r2, r3
}

El pseudocódigo está publicado en Grossman & Zeitman (1988).

Por ejemplo, sobre la entrada .. 2,1.. {displaystyle langle 2,1rangle },

las configuraciones de pilareflejar la reducción
2,1¿Qué? ¿Qué? {displaystyle {compline {2,1}}}A()2,1)¿Qué? ¿Qué? {displaystyle {compline {A(2,1)}}}
→ → 1,2,0¿Qué? ¿Qué? {displaystyle rightarrow 1,{compline {2,0}}→ → r1A()1,A()2,0)¿Qué? ¿Qué? ){displaystyle rightarrow _{r1}A(1,{underline {A(2,0)}}}
→ → 1,1,1¿Qué? ¿Qué? {displaystyle rightarrow 1,{compline {1,1}}→ → r2A()1,A()1,1)¿Qué? ¿Qué? ){displaystyle rightarrow _{r2}A(1,{underline {A(1,1)}}}}
→ → 1,0,1,0¿Qué? ¿Qué? {displaystyle rightarrow 1.0,{underline {0}}→ → r3A()1,A()0,A()1,0)¿Qué? ¿Qué? )){displaystyle rightarrow _{r3}A(1,A(0,{underline {A(1,0)})}}
→ → 1,0,0,1¿Qué? ¿Qué? {displaystyle rightarrow 1.0,{underline {0,1}}}→ → r2A()1,A()0,A()0,1)¿Qué? ¿Qué? )){displaystyle rightarrow _{r2}A(1,A(0,{underline {A(0,1)})}}
→ → 1,0,2¿Qué? ¿Qué? {displaystyle rightarrow 1,{compline {0,2}}→ → r1A()1,A()0,2)¿Qué? ¿Qué? ){displaystyle rightarrow _{r1}A(1,{underline {A(0,2)}}}
→ → 1,3¿Qué? ¿Qué? {displaystyle rightarrow {compline {1,3}}}→ → r1A()1,3)¿Qué? ¿Qué? {displaystyle rightarrow _{r1}{compline {A(1,3)}}}
→ → 0,1,2¿Qué? ¿Qué? {displaystyle rightarrow 0,{compline {1,2}}→ → r3A()0,A()1,2)¿Qué? ¿Qué? ){displaystyle rightarrow _{r3}A(0,{underline {A(1,2)}}}
→ → 0,0,1,1¿Qué? ¿Qué? {displaystyle rightarrow 0,0,{compline {1,1}}→ → r3A()0,A()0,A()1,1)¿Qué? ¿Qué? )){displaystyle rightarrow _{r3}A(0,A(0,{underline {A(1,1)})}}
→ → 0,0,0,1,0¿Qué? ¿Qué? {displaystyle rightarrow 0,0,0,{compline {0}}→ → r3A()0,A()0,A()0,A()1,0)¿Qué? ¿Qué? ))){displaystyle rightarrow _{r3}A(0,A(0,A(0,{underline {A(1,0)}})})}}
→ → 0,0,0,0,1¿Qué? ¿Qué? {displaystyle rightarrow 0,0,0,{compline {0,1}}}→ → r2A()0,A()0,A()0,A()0,1)¿Qué? ¿Qué? ))){displaystyle rightarrow _{r2}A(0,A(0,A(0,{underline {A(0,1)})})}}
→ → 0,0,0,2¿Qué? ¿Qué? {displaystyle rightarrow 0,0,{compline {0,2}}→ → r1A()0,A()0,A()0,2)¿Qué? ¿Qué? )){displaystyle rightarrow _{r1}A(0,A(0,{underline {A(0,2)}})}
→ → 0,0,3¿Qué? ¿Qué? {displaystyle rightarrow 0,{compline {0,3}}→ → r1A()0,A()0,3)¿Qué? ¿Qué? ){displaystyle rightarrow _{r1}A(0,{underline {A(0,3)}}}
→ → 0,4¿Qué? ¿Qué? {displaystyle rightarrow {compline {0,4}}→ → r1A()0,4)¿Qué? ¿Qué? {displaystyle rightarrow _{r1}{compline {A(0,4)}}}
→ → 5{displaystyle rightarrow 5}→ → r15{displaystyle rightarrow _{r1}5}

Comentarios

  • La estrategia más interna de la izquierda se aplica en 225 idiomas informáticos en el Código Rosetta.
  • Para todos m,n{displaystyle m,n} la computación de A()m,n){displaystyle A(m,n)} no toma más que ()A()m,n)+1)m{displaystyle (A(m,n)+1)} pasos.
  • Grossman " Zeitman (1988) señaló que en el cálculo de A⁡ ⁡ ()m,n){displaystyle operatorname {A} (m,n)} la longitud máxima de la pila es A⁡ ⁡ ()m,n){displaystyle operatorname {A} (m,n)}, mientras 0}" xmlns="http://www.w3.org/1998/Math/MathML">m■0{displaystyle m confía0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/501173910e6da8425b4e9d44a4e8643620bc2464" style="vertical-align: -0.338ex; width:6.301ex; height:2.176ex;"/>.
Su propio algoritmo, inherentemente iterativo, calcula A⁡ ⁡ ()m,n){displaystyle operatorname {A} (m,n)} dentro O()mA⁡ ⁡ ()m,n)){displaystyle {mathcal}(moperatorname {A} (m,n)} tiempo y dentro O()m){displaystyle {mathcal}(m)} espacio.

TRS, basado en una función aria iterada

La definición de las funciones iteradas 1-aria de Ackermann conduce a diferentes reglas de reducción

(r4)A()S()0),0,n)→ → S()n)(r5)A()S()0),S()m),n)→ → A()S()n),m,S()0))(r6)A()S()S()x)),m,n)→ → A()S()0),m,A()S()x),m,n)){fnMicrosoft Sans Serif} {fnMicrosoft Sans Ser)} {fnMicrosoft Sans Serif} {fn]} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft ]} {fnMicrosoft ]

Como la composición de funciones es asociativa, en lugar de la regla r6 se puede definir

(r7)A()S()S()x)),m,n)→ → A()S()x),m,A()S()0),m,n)){displaystyle {begin{lll}{text{(r7)} {begin{begin{array}{lll}{text{(r7)}}} {splaystyle {begin{begin{array}{lll}{lll}{text{(r7}}}}}}}}}}}} {

Como en la sección anterior la computación de Am1⁡ ⁡ ()n){displaystyle operatorname {A} _{m} {1} n)} se puede implementar con una pila.

Inicialmente la pila contiene los tres elementos .. 1,m,n.. {displaystyle langle 1,m,nrangle }.

Luego, repetidamente, los tres elementos superiores se reemplazan de acuerdo con las reglas.

(r4)1,0,n→ → ()n+1)(r5)1,()m+1),n→ → ()n+1),m,1(r6)()x+2),m,n→ → 1,m,()x+1),m,n{displaystyle {begin{lll}{text{(r4)}} {cluyen]}} {clip}}} {m+1)}}} {m+1)} {cHFF}} {cHFF} {cH00}}} {cH00cH00}}}} {cH00}}}} {cH00}}}}}}}}

Esquemáticamente, a partir de .. 1,m,n.. {displaystyle langle 1,m,nrangle }:

WHILE stackLength 1
{}
 POP 3 elementos;
 PUSH 1 o 3 o 5 elementos, aplicando las reglas r4, r5, r6;
}

Ejemplo

Sobre la entrada .. 1,2,1.. {displaystyle langle 1,2,1rangle } las configuraciones de pilas sucesivas son

1,2,1¿Qué? ¿Qué? → → r52,1,1¿Qué? ¿Qué? → → r61,1,1,1,1¿Qué? ¿Qué? → → r51,1,2,0,1¿Qué? ¿Qué? → → r61,1,1,0,1,0,1¿Qué? ¿Qué? → → r41,1,1,0,2¿Qué? ¿Qué? → → r41,1,3¿Qué? ¿Qué? → → r54,0,1¿Qué? ¿Qué? → → r61,0,3,0,1¿Qué? ¿Qué? → → r61,0,1,0,2,0,1¿Qué? ¿Qué? → → r61,0,1,0,1,0,1,0,1¿Qué? ¿Qué? → → r41,0,1,0,1,0,2¿Qué? ¿Qué? → → r41,0,1,0,3¿Qué? ¿Qué? → → r41,0,4¿Qué? ¿Qué? → → r45{0} {0}} {0} {0}} {0} {0} {0} {0}} {0} {0} {0} {0} {0} {0} {0} {0}} {0} {0} {0} {0} {0} {0} {0}} {0}}} {0}} {0}=0}}} {0} {0}}}} {0}}}}}} {0}}}}}}}}}}} {0}}}}}}}}}} {0}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}} {0}}}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} _{r6}1,0,1,0,{underline {1,0,1}}rightarrow _{r4}1,0,1,0,{underline {1,0,2}}rightarrow _{r4}1,0,{compline {1,0,3}rightarrow _{r4}{underline {1,0,0,end4}rightarrow {{r4}} {}}}{}}}}}}{}{}}}}}}{}}}}}{r4} {}}}}}}}}{}}}}{}}}}}}}}}}}}}}}}}}}}}}}}{}{}{}}}{}{}}}} {}}}}}} {}{}}}}{}{}}}}}}}}}}{}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}{}}}}}}}}}}}}}}

Las igualdades correspondientes son

A2()1)=A12()1)=A1()A1()1))=A1()A02()1))=A1()A0()A0()1)))=A1()A0()2))=A1()3)=A04()1)=A0()A03()1))=A0()A0()A02()1)))=A0()A0()A0()A0()1))))=A0()A0()A0()2)))=A0()A0()3))=A0()4)=5{0}{0}{0} {0}=0} {0} {0} {0}} {0} {0}} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0}=0}}} {0} {0}=0} {0}=0} {0}}}=0} {0} {0} {0}}} {0} {0} {0} {0}=0}}}}}}} {0} {0} {0} {0} {0} {0}} {0} {0} {0} {0}}} {0}=0}} {0} {0}} {0} {0} {0} {0}}}} {0} {0} {0} {0}}}}} {0}}}}}}}}}}}}}}}

Cuando se usa la regla de reducción r7 en lugar de la regla r6, los reemplazos en la pila seguirán

(r7)()x+2),m,n→ → ()x+1),m,1,m,n{displaystyle {begin{lllllllll}{text{(r7)} {begin{begin{array}{lllllllllll}{text{(r7)}} {begin{begin{rray}{lllllllllllllllllll}{text{(r7)}}}}}}}}} {displaystyle {begin {begin{begin{begin{begin{begin{begin{begin{begin{begin{begin{begin{begin{begin{begin{begin{begin{begin{begin{begin{llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

Las sucesivas configuraciones de pila serán entonces

1,2,1¿Qué? ¿Qué? → → r52,1,1¿Qué? ¿Qué? → → r71,1,1,1,1¿Qué? ¿Qué? → → r51,1,2,0,1¿Qué? ¿Qué? → → r71,1,1,0,1,0,1¿Qué? ¿Qué? → → r41,1,1,0,2¿Qué? ¿Qué? → → r41,1,3¿Qué? ¿Qué? → → r54,0,1¿Qué? ¿Qué? → → r73,0,1,0,1¿Qué? ¿Qué? → → r43,0,2¿Qué? ¿Qué? → → r72,0,1,0,2¿Qué? ¿Qué? → → r42,0,3¿Qué? ¿Qué? → → r71,0,1,0,3¿Qué? ¿Qué? → → r41,0,4¿Qué? ¿Qué? → → r45################################################################################################################################################################################################################################################################

Las igualdades correspondientes son

A2()1)=A12()1)=A1()A1()1))=A1()A02()1))=A1()A0()A0()1)))=A1()A0()2))=A1()3)=A04()1)=A03()A0()1))=A03()2)=A02()A0()2))=A02()3)=A0()A0()3))=A0()4)=5{0}{0}{0} {0}=0} {0} {0}=0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0}=0} {0} {0} {0}=0} {0}=0} {0} {0}} {0} {0}=0}=0}} {0}=0} {0} {0} {0} {0} {0}} {0}}}}}}}}}}}}} {0} {0} {0}} {0}}}} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0}}}}}}} {0} {0} {0}}}} {0}}}}}}}} {0}}}}}} =A_{0}{2}(A_{0}(2))=A_{0} {2}=A_{0}(A_{0}(3)=A_{0}(4)=5end{aligned}}

Comentarios

  • En cualquier entrada dada, los TRS presentados hasta ahora convergen en el mismo número de pasos. También utilizan las mismas reglas de reducción (en esta comparación las reglas r1, r2, r3 se consideran "lo mismo que" las reglas r4, r5, r6/r7 respectivamente). Por ejemplo, la reducción de A()2,1){displaystyle A(2,1)} converge en 14 pasos: 6 × r1, 3 × r2, 5 × r3. Reducción de A2()1){displaystyle A_{2}(1)} converge en los mismos 14 pasos: 6 × r4, 3 × r5, 5 × r6/r7. Los TRS difieren en el orden en que se aplican las reglas de reducción.
  • Cuando Ai()n){displaystyle A_{i}(n)} se calcula siguiendo las reglas {r4, r5, r6}, la longitud máxima de la pila se queda abajo 2× × A()i,n){displaystyle 2times A(i,n)}. Cuando la regla de reducción r7 se utiliza en lugar de regla r6, la longitud máxima de la pila es sólo 2()i+2){displaystyle 2(i+2)}. La longitud de la pila refleja la profundidad de la recursión. Dado que la reducción según las reglas {r4, r5, r7} implica una menor profundidad máxima de recurrencia, este cálculo es más eficiente en ese sentido.

TRS, basado en hiperoperadores

Como Sundblad (1971), o Porto & Matos (1980) — mostró explícitamente que la función de Ackermann se puede expresar en términos de la secuencia de hiperoperación:

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">A()m,n)={}n+1m=02[m]()n+3)− − 3m■0{displaystyle A(m,n)={begin{cases}n+1 limitm=02[m](n+3)-3 implicam confianza0\end{cases}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d74a51ad59c098733b952a52eff92e6fc38ded13" style="vertical-align: -2.505ex; width:37.945ex; height:6.176ex;"/>

o, después de eliminar la constante 2 de la lista de parámetros, en términos de la función de Buck

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">={}n+1m=0F()m,n+3)− − 3m■0{displaystyle ={begin{cases}n+1 limitadam=0F(m,n+3)-3 Pulsón0\end{cases}}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/49184cb225696100ff333a9e9632716bb2bb4c18" style="vertical-align: -2.505ex; width:29.597ex; height:6.176ex;"/>

Función de Buck F⁡ ⁡ ()m,n)=2[m]n{displaystyle operatorname {F} (m,n)=2[m]n}, una variante de la función Ackermann por sí misma, se puede computar con las siguientes reglas de reducción:

b1)F()S()0),0,n)→ → S()n)b2)F()S()0),S()0),0)→ → S()S()0))b3)F()S()0),S()S()0)),0)→ → 0b4)F()S()0),S()S()S()m))),0)→ → S()0)b5)F()S()0),S()m),S()n))→ → F()S()n),m,F()S()0),S()m),0))(b6)F()S()S()x)),m,n)→ → F()S()0),m,F()S()x),m,n)){fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {cH0} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Ser)} {cH0} {fnMicrosoft Sans Serif}

En lugar de la regla b6, se puede definir la regla

b7)F()S()S()x)),m,n)→ → F()S()x),m,F()S()0),m,n)){displaystyle {begin{lll}{text{(b7)} {f(S(x)),m,n) limitrightarrow &F(S(x),m,F(S(0),m,n)end{array}}}}}}

Para calcular la función de Ackermann es suficiente agregar tres reglas de reducción

(r8)A()0,n)→ → S()n)(r9)A()S()m),n)→ → P()F()S()0),S()m),S()S()S()n)))))(r10)P()S()S()S()m))))→ → m{fnMicrosoft Sans Ser)} {fnMicrosoft Sans Serif} {fn)} {fn]} {fn]} {fn]} {fn]} {fn]} {fn]} {fnun}}fnun} {f}fnMis)} {fnun}fnun}fnun}fnun}

Estas reglas se encargan del caso base A(0,n), la alineación (n+3) y el error (-3).

Ejemplo

Computación A()2,1)→ → Alternativa Alternativa 5{displaystyle A(2,1)rightarrow ¿Qué?

utilizando reglas de reducción b7{displaystyle {text{b7}}:utilizando reglas de reducción b6{displaystyle {text{b6}}}:
A()2,1)¿Qué? ¿Qué? {displaystyle {compline {A(2,1)}}}A()2,1)¿Qué? ¿Qué? {displaystyle {compline {A(2,1)}}}
→ → r9P()F()1,2,4)¿Qué? ¿Qué? ){displaystyle rightarrow _{r9}P({underline {F(1,2,4)}}}→ → r9P()F()1,2,4)¿Qué? ¿Qué? ){displaystyle rightarrow _{r9}P({underline {F(1,2,4)}}}
→ → b5P()F()4,1,F()1,2,0)¿Qué? ¿Qué? )){displaystyle rightarrow _{b5}P(F(4,1,{underline {F(1,2,0)}})}→ → b5P()F()4,1,F()1,2,0)¿Qué? ¿Qué? )){displaystyle rightarrow _{b5}P(F(4,1,{underline {F(1,2,0)}})}
→ → b3P()F()4,1,0)¿Qué? ¿Qué? ){displaystyle rightarrow _{b3}P({underline {F(4,1,0}}}}→ → b3P()F()4,1,0)¿Qué? ¿Qué? ){displaystyle rightarrow _{b3}P({underline {F(4,1,0}}}}
→ → b7P()F()3,1,F()1,1,0)¿Qué? ¿Qué? )){displaystyle rightarrow _{b7}P(F(3,1,{underline {F(1,1,0)})}}→ → b6P()F()1,1,F()3,1,0)¿Qué? ¿Qué? )){displaystyle rightarrow _{b6}P(F(1,1,{underline {F(3,1,0)}})}
→ → b2P()F()3,1,2)¿Qué? ¿Qué? ){displaystyle rightarrow _{b2}P({underline {F(3,1,2)}}}→ → b6P()F()1,1,F()1,1,F()2,1,0)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b6}P(F(1,F(1,1,{underline {F(2,1,0)})})}}
→ → b7P()F()2,1,F()1,1,2)¿Qué? ¿Qué? )){displaystyle rightarrow _{b7}P(F(2,1,{underline {F(1,1,2)})}}→ → b6P()F()1,1,F()1,1,F()1,1,F()1,1,0)¿Qué? ¿Qué? )))){displaystyle rightarrow _{b6}P(F(1,F(1,F(1,1,F(1,1,1,{underline {F(1,0)})})})}
→ → b5P()F()2,1,F()2,0,F()1,1,0)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b5}P(F(2,1,F(2,0,{underline {F(1,1,0)})})}}→ → b2P()F()1,1,F()1,1,F()1,1,2)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b2}P(F(1,F(1,1,{underline {F(1,1,1,2)})})}}
→ → b2P()F()2,1,F()2,0,2)¿Qué? ¿Qué? )){displaystyle rightarrow _{b2}P(F(2,1,{underline {F(2,0,2)})}}→ → b5P()F()1,1,F()1,1,F()2,0,F()1,1,0)¿Qué? ¿Qué? )))){displaystyle rightarrow _{b5}P(F(1,F(1,F(2,0,{underline {F(1,1,0)})})}}
→ → b7P()F()2,1,F()1,0,F()1,0,2)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b7}P(F(2,1,F(1,0,{underline {F(1,0,2)})})}}→ → b2P()F()1,1,F()1,1,F()2,0,2)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b2}P(F(1,F(1,1,{underline {F(2,0,2)})})}}
→ → b1P()F()2,1,F()1,0,3)¿Qué? ¿Qué? )){displaystyle rightarrow _{b1}P(F(2,1,{underline {F(1,0,3)})}}→ → b6P()F()1,1,F()1,1,F()1,0,F()1,0,2)¿Qué? ¿Qué? )))){displaystyle rightarrow _{b6}P(F(1,1,F(1,F(1,0,{underline {F(1,0,2)})})}}
→ → b1P()F()2,1,4)¿Qué? ¿Qué? ){displaystyle rightarrow _{b1}P({underline {F(2,1,4)}}}→ → b1P()F()1,1,F()1,1,F()1,0,3)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b1}P(F(1,F(1,1,{underline {F(1,0,3)}})})}}
→ → b7P()F()1,1,F()1,1,4)¿Qué? ¿Qué? )){displaystyle rightarrow _{b7}P(F(1,1,{underline {F(1,1,4)})}→ → b1P()F()1,1,F()1,1,4)¿Qué? ¿Qué? )){displaystyle rightarrow _{b1}P(F(1,1,{underline {F(1,1,4)})}
→ → b5P()F()1,1,F()4,0,F()1,1,0)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b5}P(F(1,1,F(4,0,{underline {F(1,1,0)}})})}}→ → b5P()F()1,1,F()4,0,F()1,1,0)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b5}P(F(1,1,F(4,0,{underline {F(1,1,0)}})})}}
→ → b2P()F()1,1,F()4,0,2)¿Qué? ¿Qué? )){displaystyle rightarrow _{b2}P(F(1,1,{underline {F(4,0,2)})}}→ → b2P()F()1,1,F()4,0,2)¿Qué? ¿Qué? )){displaystyle rightarrow _{b2}P(F(1,1,{underline {F(4,0,2)})}}
→ → b7P()F()1,1,F()3,0,F()1,0,2)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b7}P(F(1,1,F(3,0,{underline {F(1,0,2)})})}}→ → b6P()F()1,1,F()1,0,F()3,0,2)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b6}P(F(1,F(1,0,{underline {F(3,0,2)})})}}
→ → b1P()F()1,1,F()3,0,3)¿Qué? ¿Qué? )){displaystyle rightarrow _{b1}P(F(1,1,{underline {F(3,0,3)}})}→ → b6P()F()1,1,F()1,0,F()1,0,F()2,0,2)¿Qué? ¿Qué? )))){displaystyle rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,{underline {F(2,0,2)})})}}
→ → b7P()F()1,1,F()2,0,F()1,0,3)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b7}P(F(1,1,F(2,0,{underline {F(1,0,3)}})})}}→ → b6P()F()1,1,F()1,0,F()1,0,F()1,0,F()1,0,2)¿Qué? ¿Qué? ))))){displaystyle rightarrow _{b6}P(F(1,F(1,0,F(1,0,F(1,0,{underline {F(1,0,2)})})})}
→ → b1P()F()1,1,F()2,0,4)¿Qué? ¿Qué? )){displaystyle rightarrow _{b1}P(F(1,1,{underline {F(2,0,4)})}→ → b1P()F()1,1,F()1,0,F()1,0,F()1,0,3)¿Qué? ¿Qué? )))){displaystyle rightarrow _{b1}P(F(1,1,F(1,0,F(1,0,{underline {F(1,0,3)})})}}
→ → b7P()F()1,1,F()1,0,F()1,0,4)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b7}P(F(1,1,F(1,0,{underline {F(1,0,4)})})}}→ → b1P()F()1,1,F()1,0,F()1,0,4)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b1}P(F(1,F(1,0,{underline {F(1,0,4)})})}}
→ → b1P()F()1,1,F()1,0,5)¿Qué? ¿Qué? )){displaystyle rightarrow _{b1}P(F(1,1,{underline {F(1,0,5)}})}→ → b1P()F()1,1,F()1,0,5)¿Qué? ¿Qué? )){displaystyle rightarrow _{b1}P(F(1,1,{underline {F(1,0,5)}})}
→ → b1P()F()1,1,6)¿Qué? ¿Qué? ){displaystyle rightarrow _{b1}P({underline {F(1,1,6)}}}→ → b1P()F()1,1,6)¿Qué? ¿Qué? ){displaystyle rightarrow _{b1}P({underline {F(1,1,6)}}}
→ → b5P()F()6,0,F()1,1,0)¿Qué? ¿Qué? )){displaystyle rightarrow _{b5}P(F(6,0,{underline {F(1,1,0)}})}}→ → b5P()F()6,0,F()1,1,0)¿Qué? ¿Qué? )){displaystyle rightarrow _{b5}P(F(6,0,{underline {F(1,1,0)}})}}
→ → b2P()F()6,0,2)¿Qué? ¿Qué? ){displaystyle rightarrow _{b2}P({underline {F(6,0,2)}}}→ → b2P()F()6,0,2)¿Qué? ¿Qué? ){displaystyle rightarrow _{b2}P({underline {F(6,0,2)}}}
→ → b7P()F()5,0,F()1,0,2)¿Qué? ¿Qué? )){displaystyle rightarrow _{b7}P(F(5,0,{underline {F(1,0,2)}})}→ → b6P()F()1,0,F()5,0,2)¿Qué? ¿Qué? )){displaystyle rightarrow _{b6}P(F(1,0,{underline {F(5,0,2)}})}
→ → b1P()F()5,0,3)¿Qué? ¿Qué? ){displaystyle rightarrow _{b1}P({underline {F(5,0,3)}}}→ → b6P()F()1,0,F()1,0,F()4,0,2)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b6}P(F(1,0,F(1,0,{underline {F(4,0,2)})})}}
→ → b7P()F()4,0,F()1,0,3)¿Qué? ¿Qué? )){displaystyle rightarrow _{b7}P(F(4,0,{underline {F(1,0,3)}})}}→ → b6P()F()1,0,F()1,0,F()1,0,F()3,0,2)¿Qué? ¿Qué? )))){displaystyle rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,{underline {F(3,0,2)})})}
→ → b1P()F()4,0,4)¿Qué? ¿Qué? ){displaystyle rightarrow _{b1}P({underline {F(4,0,4)}}}→ → b6P()F()1,0,F()1,0,F()1,0,F()1,0,F()2,0,2)¿Qué? ¿Qué? ))))){displaystyle rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,{underline {F(2,0,2)})})})}
→ → b7P()F()3,0,F()1,0,4)¿Qué? ¿Qué? )){displaystyle rightarrow _{b7}P(F(3,0,{underline {F(1,0,4)}})}→ → b6P()F()1,0,F()1,0,F()1,0,F()1,0,F()1,0,F()1,0,2)¿Qué? ¿Qué? )))))){displaystyle rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,F(1,0,{underline {F(1,0,2)}))})})}
→ → b1P()F()3,0,5)¿Qué? ¿Qué? ){displaystyle rightarrow _{b1}P({underline {F(3,0,5)}}}→ → b1P()F()1,0,F()1,0,F()1,0,F()1,0,F()1,0,3)¿Qué? ¿Qué? ))))){displaystyle rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,F(1,0,{underline {F(1,0,3)})})})}
→ → b7P()F()2,0,F()1,0,5)¿Qué? ¿Qué? )){displaystyle rightarrow _{b7}P(F(2,0,{underline {F(1,0,5)}})}}→ → b1P()F()1,0,F()1,0,F()1,0,F()1,0,4)¿Qué? ¿Qué? )))){displaystyle rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,{underline {F(1,0,4)})})}}
→ → b1P()F()2,0,6)¿Qué? ¿Qué? ){displaystyle rightarrow _{b1}P({underline {F(2,0,6)}}}→ → b1P()F()1,0,F()1,0,F()1,0,5)¿Qué? ¿Qué? ))){displaystyle rightarrow _{b1}P(F(1,0,F(1,0,{underline {F(1,0,5)}})})}}
→ → b7P()F()1,0,F()1,0,6)¿Qué? ¿Qué? )){displaystyle rightarrow _{b7}P(F(1,0,{underline {F(1,0,6)}}})}→ → b1P()F()1,0,F()1,0,6)¿Qué? ¿Qué? )){displaystyle rightarrow _{b1}P(F(1,0,{underline {F(1,0,6)}})}}
→ → b1P()F()1,0,7)¿Qué? ¿Qué? ){displaystyle rightarrow _{b1}P({underline {F(1,0,7}}}}→ → b1P()F()1,0,7)¿Qué? ¿Qué? ){displaystyle rightarrow _{b1}P({underline {F(1,0,7}}}}
→ → b1P()8)¿Qué? ¿Qué? {displaystyle rightarrow _{b1}{underline {P(8)}}→ → b1P()8)¿Qué? ¿Qué? {displaystyle rightarrow _{b1}{underline {P(8)}}
→ → r105{displaystyle rightarrow _{r10}5}→ → r105{displaystyle rightarrow _{r10}5}

Las igualdades coincidentes son

  • cuando el TRS con la regla de reducción b6{displaystyle {text{b6}}} se aplica:
A()2,1)+3=F()2,4)=⋯ ⋯ =F6()0,2)=F()0,F5()0,2))=F()0,F()0,F4()0,2)))=F()0,F()0,F()0,F3()0,2))))=F()0,F()0,F()0,F()0,F2()0,2)))))=F()0,F()0,F()0,F()0,F()0,F()0,2))))))=F()0,F()0,F()0,F()0,F()0,3)))))=F()0,F()0,F()0,F()0,4))))=F()0,F()0,F()0,5)))=F()0,F()0,6))=F()0,7)=8{0,0}(0)}(0)
  • cuando el TRS con la regla de reducción b7{displaystyle {text{b7}} se aplica:
A()2,1)+3=F()2,4)=⋯ ⋯ =F6()0,2)=F5()0,F()0,2))=F5()0,3)=F4()0,F()0,3))=F4()0,4)=F3()0,F()0,4))=F3()0,5)=F2()0,F()0,5))=F2()0,6)=F()0,F()0,6))=F()0,7)=8{0}}(0,4)}(0,3)}(0,0})=F}(0,0}(0,4)}(0,)=F^=0}(0,3)

Comentarios

  • La computación de Ai⁡ ⁡ ()n){displaystyle operatorname {A} _{i}(n)} según las reglas {b1 - b5, b6, r8 - r10} es profundamente recursivo. La profundidad máxima de anidado F{displaystyle F}s A()i,n)+1{displaystyle A(i,n)+1}. El culpable es la orden en la que se ejecuta la iteración: Fn+1()x)=F()Fn()x)){displaystyle F^{n+1}(x)=F(F^{n}(x)}. La primera F{displaystyle F} desaparece sólo después de que toda la secuencia se desarrolle.
  • El cálculo según las reglas {b1 - b5, b7, r8 - r10} es más eficiente en ese sentido. La iteración Fn+1()x)=Fn()F()x)){displaystyle F^{n+1}(x)=F^{n}(F(x)} simula el bucle repetido sobre un bloque de código. El anidaje se limita a ()i+1){displaystyle (i+1)}, un nivel de recursión por función iterada. Meyer & Ritchie (1967) mostró esta correspondencia.
  • Estas consideraciones se refieren únicamente a la profundidad de recursión. Cualquier forma de iteración conduce al mismo número de pasos de reducción, que implican las mismas reglas (cuando las reglas b6 y b7 se consideran "el mismo"). Reducción de A()2,1){displaystyle A(2,1)} por ejemplo converge en 35 pasos: 12 × b1, 4 × b2, 1 × b3, 4 × b5, 12 × b6/b7, 1 × r9, 1 × r10. El modus iterandi sólo afecta el orden en que se aplican las reglas de reducción.
  • Una ganancia real del tiempo de ejecución sólo puede lograrse no recalculando los subresultos una y otra vez. La memoización es una técnica de optimización donde los resultados de las llamadas de función son caché y devueltos cuando las mismas entradas ocurren de nuevo. Véase por ejemplo Ward (1993). Grossman " Zeitman (1988) publicó un algoritmo astuto que compute A()i,n){displaystyle A(i,n)} dentro O()iA()i,n)){displaystyle {mathcal}(iA(i,n)} tiempo y dentro O()i){displaystyle {Mathcal}(i)} espacio.

Números enormes

Para demostrar cómo la computación A()4,3){displaystyle A(4,3)} resultados en muchos pasos y en un gran número:

A()4,3)→ → A()3,A()4,2))→ → A()3,A()3,A()4,1)))→ → A()3,A()3,A()3,A()4,0))))→ → A()3,A()3,A()3,A()3,1))))→ → A()3,A()3,A()3,A()2,A()3,0)))))→ → A()3,A()3,A()3,A()2,A()2,1)))))→ → A()3,A()3,A()3,A()2,A()1,A()2,0))))))→ → A()3,A()3,A()3,A()2,A()1,A()1,1))))))→ → A()3,A()3,A()3,A()2,A()1,A()0,A()1,0)))))))→ → A()3,A()3,A()3,A()2,A()1,A()0,A()0,1)))))))→ → A()3,A()3,A()3,A()2,A()1,A()0,2))))))→ → A()3,A()3,A()3,A()2,A()1,3)))))→ → A()3,A()3,A()3,A()2,A()0,A()1,2))))))→ → A()3,A()3,A()3,A()2,A()0,A()0,A()1,1)))))))→ → A()3,A()3,A()3,A()2,A()0,A()0,A()0,A()1,0))))))))→ → A()3,A()3,A()3,A()2,A()0,A()0,A()0,A()0,1))))))))→ → A()3,A()3,A()3,A()2,A()0,A()0,A()0,2)))))))→ → A()3,A()3,A()3,A()2,A()0,A()0,3))))))→ → A()3,A()3,A()3,A()2,A()0,4)))))→ → A()3,A()3,A()3,A()2,5))))⋮ ⋮ → → A()3,A()3,A()3,13)))⋮ ⋮ → → A()3,A()3,65533))⋮ ⋮ → → A()3,265536− − 3)⋮ ⋮ → → 2265536− − 3.A(arrow)(3,A)

Tabla de valores

El cálculo de la función de Ackermann se puede reformular en términos de una tabla infinita. Primero, coloca los números naturales a lo largo de la fila superior. Para determinar un número en la tabla, tome el número inmediatamente a la izquierda. Luego use ese número para buscar el número requerido en la columna dada por ese número y una fila hacia arriba. Si no hay un número a su izquierda, simplemente mire la columna encabezada "1" en la fila anterior. Aquí hay una pequeña parte superior izquierda de la tabla:

Valores de A()m,n)
n
m
0 1 2 3 4 n
0 12345n+1{displaystyle n+1}
1 23456n+2=2+()n+3)− − 3{displaystyle n+2=2+(n+3)-3}
2 3579112n+3=2⋅ ⋅ ()n+3)− − 3{displaystyle 2n+3=2cdot (n+3)-3}
3 51329611252()n+3)− − 3{displaystyle 2^{(n+3)}-3}
4 13

=222− − 3{displaystyle ={2^{2^{2}}-3}
=2↑ ↑ ↑ ↑ 3− − 3{displaystyle =2uparrow uparrow 3-3}
65533

=2222− − 3{displaystyle = {2^{2^{2}}}-3}
=2↑ ↑ ↑ ↑ 4− − 3{displaystyle =2uparrow uparrow 4-3}
2655363 - 3

=22222− − 3{displaystyle {2}}3}
=2↑ ↑ ↑ ↑ 5− − 3{displaystyle =2uparrow uparrow 5-3}
2265536− − 3{displaystyle {2^{2^{65536}}-3}

=222222− − 3{displaystyle - ¿Sí?
=2↑ ↑ ↑ ↑ 6− − 3{displaystyle =2uparrow uparrow 6-3}
22265536− − 3{displaystyle {2^{2}}-3}

=2222222− − 3{displaystyle ={2^{2^{2^{2^{2^{2}}}}}-3}
=2↑ ↑ ↑ ↑ 7− − 3{displaystyle =2uparrow uparrow 7-3}
22⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 2⏟ ⏟ n+3− − 3{displaystyle {begin{Matrix}underbrace {cdot} {cdot} {cdot} {cdot}} {cdot }}}}}}}}} {cdot} {cdot}} {cdot}} {cdot}}}} {cdot}} {cdot}}} {cdot}}}}}}}}}}} {cdot}}}}}}}} {cdot} {cdot}}}}}} {cdot} {cdot}}} {cdot}}}}}}}}}}}}}}}}}}}}}}}}}} {cdot} {cdot}}} {cdot} {cdot}} {cdot} {cdot} {cdot}} {cdot}} {cdot} {cdot}}}}}}}}}}}}}}}}} - ¿Qué?

=2↑ ↑ ↑ ↑ ()n+3)− − 3{displaystyle =2uparrow uparrow (n+3)-3}
5 65533
=2↑ ↑ ↑ ↑ ()2↑ ↑ ↑ ↑ 2)− − 3{displaystyle =2uparrow uparrow (2uparrow uparrow 2)-3}
=2↑ ↑ ↑ ↑ ↑ ↑ 3− − 3{displaystyle =2uparrow uparrow 3-3}
2↑ ↑ ↑ ↑ ↑ ↑ 4− − 3{displaystyle 2uparrow uparrow 4-3}2↑ ↑ ↑ ↑ ↑ ↑ 5− − 3{displaystyle 2uparrow uparrow 5-3}2↑ ↑ ↑ ↑ ↑ ↑ 6− − 3{displaystyle 2uparrow uparrow 6-3}2↑ ↑ ↑ ↑ ↑ ↑ 7− − 3{displaystyle 2uparrow uparrow 7-3}2↑ ↑ ↑ ↑ ↑ ↑ ()n+3)− − 3{displaystyle 2uparrow uparrow (n+3)-3}
6 2↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 3− − 3{displaystyle 2uparrow uparrow uparrow 3-3}2↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 4− − 3{displaystyle 2uparrow uparrow uparrow 4-3}2↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 5− − 3{displaystyle 2uparrow uparrow uparrow 5-3}2↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 6− − 3{displaystyle 2uparrow uparrow uparrow 6-3}2↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 7− − 3{displaystyle 2uparrow uparrow uparrow 7-3}2↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ()n+3)− − 3{displaystyle 2uparrow uparrow uparrow (n+3)-3}
m()2→ → 3→ → ()m− − 2))− − 3{displaystyle (2to 3to (m-2)-3}()2→ → 4→ → ()m− − 2))− − 3{displaystyle (2to 4to (m-2)-3}()2→ → 5→ → ()m− − 2))− − 3{displaystyle (2to 5to (m-2)-3}()2→ → 6→ → ()m− − 2))− − 3{displaystyle (2to 6to (m-2)-3}()2→ → 7→ → ()m− − 2))− − 3{displaystyle (2to 7to (m-2)-3}()2→ → ()n+3)→ → ()m− − 2))− − 3{displaystyle (2to (n+3)to (m-2)-3}

Los números aquí que solo se expresan con exponenciación recursiva o flechas de Knuth son muy grandes y ocuparían demasiado espacio para anotarlos en dígitos decimales simples.

A pesar de los grandes valores que aparecen en esta primera sección de la tabla, se han definido algunos números aún más grandes, como el número de Graham, que no se puede escribir con una pequeña cantidad de flechas de Knuth. Este número se construye con una técnica similar a aplicar la función de Ackermann a sí mismo recursivamente.

Esta es una repetición de la tabla anterior, pero con los valores reemplazados por la expresión relevante de la definición de la función para mostrar el patrón claramente:

Valores de A()m,n)
n
m
0 1 2 3 4 n
0 0+11+12+13+14+1n + 1
1 A(0, 1)A(0, A(1, 0))
= A(0, 2)
A(0, A(1, 1))
= A(0, 3)
A(0, A(1, 2))
= A(0, 4)
A(0, A(1, 3))
= A(0, 5)
A(0, A(1, n−1))
2 A(1, 1)A(1, A(2, 0))
= A(1, 3)
A(1, A(2, 1))
= A(1, 5)
A(1, A(2, 2))
= A(1, 7)
A(1, A(2, 3))
= A(1, 9)
A(1, A(2, n−1))
3 A(2, 1)A(2, A(3, 0))
= A(2, 5)
A(2, A(3, 1))
= A(2, 13)
A(2, A(3, 2))
= A(2, 29)
A(2, A(3, 3))
= A(2, 61)
A(2, A(3, n−1))
4 A(3, 1)A(3, A(4, 0)))
= A(3, 13)
A(3, A(4, 1))
= A(3, 65533)
A(3, A(4, 2))A(3, A(4, 3))A(3, A(4, n−1))
5 A(4, 1)A(4, A(5, 0))A(4, A(5, 1))A(4, A(5, 2))A(4, A(5, 3))A(4, A(5, n−1))
6 A(5, 1)A(5, A(6, 0))A(5, A(6, 1))A(5, A(6, 2))A(5, A(6, 3))A(5, A(6, n−1))

Propiedades

Observaciones generales

  • Puede que no sea inmediatamente obvio que la evaluación A()m,n){displaystyle A(m,n)} siempre termina. Sin embargo, la recursión está ligada porque en cada aplicación recursiva ya sea m{displaystyle m} disminuciones, o m{displaystyle m} sigue siendo el mismo n{displaystyle n} disminuciones. Cada vez que n{displaystyle n} alcanza cero, m{displaystyle m} disminuciones, por lo tanto m{displaystyle m} eventualmente llega a cero también. (Expresado más técnicamente, en cada caso el par ()m,n){displaystyle (m,n)} disminuciones en el orden lexicográfico sobre pares, que es un bien ordenado, al igual que el orden de enteros no negativos individuales; esto significa que no se puede bajar en el orden infinitamente muchas veces en sucesión.) Sin embargo, cuando m{displaystyle m} disminuciones no hay límite superior en cuánto n{displaystyle n} puede aumentar — y a menudo aumentará enormemente.
  • Para valores pequeños de m como 1, 2, o 3, la función Ackermann crece relativamente lentamente con respecto a n (a lo más exponencial). Para m≥ ≥ 4{displaystyle mgeq 4}, sin embargo, crece mucho más rápidamente; incluso A()4,2){displaystyle A(4,2)} es alrededor de 2×1019728, y la expansión decimal A()4,3){displaystyle A(4,3)} es muy grande por cualquier medida típica.
  • Un aspecto interesante es que la única operación aritmética que utiliza es la adición de 1. Su poder de crecimiento rápido se basa únicamente en la recursión anida. Esto también implica que su tiempo de funcionamiento es al menos proporcional a su producción, y también es extremadamente enorme. En la actualidad, para la mayoría de los casos el tiempo de funcionamiento es mucho mayor que la salida; véase arriba.
  • Una versión de un solo grupo f()n)=A()n,n){displaystyle f(n)=A(n,n)} que aumenta ambos m{displaystyle m} y n{displaystyle n} al mismo tiempo enana cada función recursiva primitiva, incluyendo funciones de crecimiento muy rápido como la función exponencial, la función factorial, funciones multi- y superfactoriales, e incluso funciones definidas usando la notación de Knuth (excepto cuando se utiliza la flecha indizada). Se puede ver que f()n){displaystyle f(n)} es aproximadamente comparable a f⋅ ⋅ ()n){displaystyle f_{omega }(n)} en la jerarquía de rápido crecimiento. Este crecimiento extremo puede ser explotado para demostrar que f{displaystyle f} que es obviamente computable en una máquina con memoria infinita como una máquina de Turing y así es una función computable, crece más rápido que cualquier función recursiva primitiva y por lo tanto no es recursiva primitiva.

No primitivo recursivo

La función Ackermann crece más rápido que cualquier función recursiva primitiva y por lo tanto no es en sí misma la recursiva primitiva. El boceto de la prueba es éste: una función recursiva primitiva definida usando recursiones de hasta k debe crecer más lento que la fk+1()n){displaystyle f_{k+1}(n)}, la función (k+1)-th en la jerarquía de crecimiento rápido, pero la función Ackermann crece al menos tan rápido como f⋅ ⋅ ()n){displaystyle f_{omega }(n)}.

Específicamente, se muestra que a cada función recursiva primitiva f()x1,...... ,xn){displaystyle f(x_{1},ldotsx_{n}} existe un entero no negativo t{displaystyle t} tal que para todos los enteros no negativos x1,...... ,xn{displaystyle x_{1},ldotsx_{n},

<math alttext="{displaystyle f(x_{1},ldotsx_{n})f()x1,...... ,xn).A()t,maxixi).{displaystyle f(x_{1},ldotsx_{n}) Se hizo(t,max _{i}x_{i}).}<img alt="{displaystyle f(x_{1},ldotsx_{n})

Una vez establecido esto, sigue que A{displaystyle A} en sí mismo no es recursivo primitivo, ya que de otra manera poner x1=x2=t{displaystyle x_{1}=x_{2}=t} conduciría a la contradicción <math alttext="{displaystyle A(t,t)A()t,t).A()t,t).{displaystyle A(t,t) }<img alt="{displaystyle A(t,t)

La prueba procede de la siguiente manera: definir la clase A{displaystyle {fnMithcal}} de todas las funciones que crecen más lento que la función Ackermann

<math alttext="{displaystyle {mathcal {A}}=left{f,{bigg |},exists t forall x_{1}cdots forall x_{n}: f(x_{1},ldotsx_{n})A={}fSilencio∃ ∃ tО О x1⋯ ⋯ О О xn:f()x1,...... ,xn).A()t,maxixi)}{\fnMicrosoft Sans Serif}cdots forall x_{n}: f(x_{1},ldotsx_{n})} {cdots forall x_{n}: f(x_{1},ldotsx_{n}) {m} {i}} {f}}}f}}}f}f})f}f}<img alt="{displaystyle {mathcal {A}}=left{f,{bigg |},exists t forall x_{1}cdots forall x_{n}: f(x_{1},ldotsx_{n})

y mostrar eso A{displaystyle {fnMithcal}} contiene todas las funciones recursivas primitivas. Este último se logra demostrando que A{displaystyle {fnMithcal}} contiene las funciones constantes, la función sucesora, las funciones de proyección y que se cierra bajo las operaciones de la composición de la función y la recursión primitiva.

Inverso

Desde la función f()n) A()n, n) considerado arriba crece muy rápidamente, su función inversa, f−1, crece muy lentamente. Esto inversa función Ackermann f−1 es generalmente denotado por α. De hecho, α()n) es menos de 5 para cualquier tamaño de entrada práctico n, desde A(4, 4) está en el orden 222216{displaystyle 2^{2^{2^{2}}}}.

Este inverso aparece en la complejidad temporal de algunos algoritmos, como la estructura de datos de conjunto disjunto y el algoritmo de Chazelle para árboles de expansión mínimos. A veces, la función original de Ackermann u otras variaciones se utilizan en estas configuraciones, pero todas crecen a tasas igualmente altas. En particular, algunas funciones modificadas simplifican la expresión eliminando el −3 y términos similares.

Una variación de dos parámetros de la función inversa Ackermann se puede definir como sigue, donde ⌊ ⌊ x⌋ ⌋ {displaystyle lfloor xrfloor } es la función del suelo:

α α ()m,n)=min{}i≥ ≥ 1:A()i,⌊ ⌊ m/n⌋ ⌋ )≥ ≥ log2⁡ ⁡ n}.{displaystyle alpha (m,n)=min{igeq 1:A(i,lfloor m/nrfloor)geq log - ¿Qué?

Esta función surge en análisis más precisos de los algoritmos mencionados anteriormente y brinda un límite de tiempo más refinado. En la estructura de datos de conjunto disjunto, m representa el número de operaciones mientras que n representa el número de elementos; en el algoritmo del árbol de expansión mínimo, m representa el número de aristas mientras que n representa el número de vértices. Existen varias definiciones ligeramente diferentes de α(m, n); por ejemplo, log2 n a veces se reemplaza por n, y la función de piso es a veces reemplazado por un techo.

Otros estudios podrían definir una función inversa de uno donde m se establece en una constante, de modo que el inverso se aplica a una fila en particular.

La función inversa de Ackermann es recursiva primitiva.

Usar como punto de referencia

La función de Ackermann, debido a su definición en términos de recursividad extremadamente profunda, se puede utilizar como punto de referencia de la capacidad de un compilador para optimizar la recursividad. El primer uso publicado de la función de Ackermann de esta manera fue en 1970 por Dragoș Vaida y, casi simultáneamente, en 1971, por Yngve Sundblad.

El artículo fundamental de Sundblad fue retomado por Brian Wichmann (coautor del índice de referencia Whetstone) en una trilogía de artículos escritos entre 1975 y 1982.

Contenido relacionado

Arte fractal

Arte fractal es una forma de arte algorítmico creada mediante el cálculo de objetos fractales y la representación de los resultados del cálculo como...

Desigualdad triangular

En matemáticas, la desigualdad del triángulo establece que para cualquier triángulo, la suma de las longitudes de dos lados cualesquiera debe ser mayor o...

Distancia de hamming

En la teoría de la información, la distancia de Hamming entre dos cadenas de igual longitud es el número de posiciones en las que los símbolos...
Más resultados...
Tamaño del texto:
undoredo
format_boldformat_italicformat_underlinedstrikethrough_ssuperscriptsubscriptlink
save