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. Consulte esto para obtener más información.
Es una función con dos argumentos a cada uno de los cuales se le puede asignar cualquier número entero no negativo.
La función de Ackermann se define como:
Algoritmo de Ackermann:
Ackermann(m, n)
{next and goal are arrays indexed from 0 to m, initialized so that next[O]
through next[m] are 0, goal[O] through goal[m - l] are 1, and goal[m] is -1}
repeat
value <-- next[O] + 1
transferring <-- true
current <-- O
while transferring do begin
if next[current] = goal[current] then goal[current] <-- value
else transferring <-- false
next[current] <-- next[current]+l
current <-- current + 1
end while
until next[m] = n + 1
return value {the value of A(m, n)}
end Ackermann
Aquí está la explicación del algoritmo dado:
Permítanme explicar el algoritmo tomando el ejemplo A (1, 2) donde m = 1 y n = 2
Entonces, de acuerdo con el algoritmo inicialmente, el valor de siguiente, objetivo, valor y actual son:
Aunque next[current] != goal[current] , la declaración else se ejecutará y la transferencia se volverá falsa.
Así que ahora, el valor de siguiente, objetivo, valor y actual son:
De manera similar, al rastrear el algoritmo hasta el siguiente [m] = 3 , el valor del siguiente, el objetivo, el valor y el actual cambian en consecuencia. Aquí está la explicación de cómo los valores están cambiando,
Finalmente devolviendo el valor, por ejemplo, 4
Análisis de este algoritmo:
- La complejidad temporal de este algoritmo es: O(mA(m, n)) para calcular A(m, n)
- La complejidad espacial de este algoritmo es: O(m) para calcular A(m, n)
¡Entendamos la definición resolviendo un problema!
Resolver A(1, 2)?
Respuesta :
El problema dado es A(1, 2)
Aquí m = 1, n = 2, por ejemplo, m > 0 y n > 0
Por lo tanto, aplicando la tercera condición de la función de Ackermann
A(1, 2) = A(0, A(1, 1) )) ———- (1)
Ahora, encontremos A(1, 1) aplicando la tercera condición de la función de Ackermann
A(1, 1) = A(0, A(1, 0)) ———- (2 )
Ahora, encontremos A(1, 0) aplicando la segunda condición de la función de Ackermann
A(1, 0) = A(0, 1) ———- (3)
Ahora, encontremos A(0, 1) aplicando primera condición de la función de Ackermann
A(0, 1) = 1 + 1 = 2
Ahora ponga este valor en la ecuación 3
Por lo tanto A(1, 0) = 2
Ahora ponga este valor en la ecuación 2
A(1, 1) = A(0 , 2) ———- (4)
Ahora, busquemos A(0, 2) aplicando la primera condición de la función de Ackermann
A(0, 2) = 2 + 1 = 3
Ahora ponga este valor en la ecuación 4
Por lo tanto, A(1, 1) = 3
Ahora ponga este valor en ecuación 1
A(1, 2) = A(0, 3) ———- (5)
Ahora, encontremos A(0, 3) aplicando la primera condición de la función de Ackermann
A(0, 3) = 3 + 1 = 4
Ahora ponga este valor en la ecuación 5
Por lo tanto, A(1, 2) = 4
Entonces, A (1, 2) = 4
¡Resolvamos otras dos preguntas sobre esto por ti mismo!
Pregunta : ¿Resuelve A(2, 1)?
Respuesta : 5
Pregunta : ¿Resuelve A(2, 2)?
Respuesta : 7
Aquí está el código de función de recursión c y python más simple para generar la función de Ackermann
C++
// C++ program to illustrate Ackermann function
#include <iostream>
using namespace std;
int ack(int m, int n)
{
if (m == 0){
return n + 1;
}
else if((m > 0) && (n == 0)){
return ack(m - 1, 1);
}
else if((m > 0) && (n > 0)){
return ack(m - 1, ack(m, n - 1));
}
}
// Driver code
int main()
{
int A;
A = ack(1, 2);
cout << A << endl;
return 0;
}
// This code is contributed by SHUBHAMSINGH10
C
// C program to illustrate Ackermann function
#include <stdio.h>
int ack(int m, int n)
{
if (m == 0){
return n+1;
}
else if((m > 0) && (n == 0)){
return ack(m-1, 1);
}
else if((m > 0) && (n > 0)){
return ack(m-1, ack(m, n-1));
}
}
int main(){
int A;
A = ack(1, 2);
printf("%d", A);
return 0;
}
// This code is contributed by Amiya Rout
Java
// Java program to illustrate Ackermann function
class GFG
{
static int ack(int m, int n)
{
if (m == 0)
{
return n + 1;
}
else if((m > 0) && (n == 0))
{
return ack(m - 1, 1);
}
else if((m > 0) && (n > 0))
{
return ack(m - 1, ack(m, n - 1));
}else
return n + 1;
}
// Driver code
public static void main(String args[])
{
System.out.println(ack(1, 2));
}
}
// This code is contributed by AnkitRai01
Python3
# Python program to illustrate Ackermann function
def A(m, n, s ="% s"):
print(s % ("A(% d, % d)" % (m, n)))
if m == 0:
return n + 1
if n == 0:
return A(m - 1, 1, s)
n2 = A(m, n - 1, s % ("A(% d, %% s)" % (m - 1)))
return A(m - 1, n2, s)
print(A(1, 2))
# This code is contributed by Amiya Rout
C#
// C# program to illustrate Ackermann function
using System;
class GFG
{
static int ack(int m, int n)
{
if (m == 0)
{
return n + 1;
}
else if((m > 0) && (n == 0))
{
return ack(m - 1, 1);
}
else if((m > 0) && (n > 0))
{
return ack(m - 1, ack(m, n - 1));
}else
return n + 1;
}
// Driver code
public static void Main()
{
Console.WriteLine(ack(1, 2));
}
}
// This code is contributed by mohit kumar 29
Javascript
<script>
// Javascript program to illustrate Ackermann function
function ack(m,n)
{
if (m == 0)
{
return n + 1;
}
else if((m > 0) && (n == 0))
{
return ack(m - 1, 1);
}
else if((m > 0) && (n > 0))
{
return ack(m - 1, ack(m, n - 1));
}else
return n + 1;
}
// Driver code
document.write(ack(1, 2));
// This code is contributed by unknown2108
</script>
Si aún desea visualizar cómo se llega a este resultado, puede echar un vistazo a esta página , que anima el cálculo de cada paso de recurrencia.
Publicación traducida automáticamente
Artículo escrito por AmiyaRanjanRout y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA