Ackermann Función Comprensión

Question

Tengo dificultades para comprender cómo funciona la Función Ackermann. Creo que mi comprensión de la recursión es defectuosa.

Este es el código en Python:

def naive_ackermann(m, n): 
    global calls 
    calls += 1 
    if m == 0: 
     return n + 1 
    elif n == 0: 
     return naive_ackermann(m - 1, 1) 
    else: 
     return naive_ackermann(m - 1, naive_ackermann(m, n - 1)) 

Si hago la llamada de función de naive_ackermann (3,4), ¿cómo y por qué acaban obteniendo 125?

Los comentarios serán apreciados.

Gracias

Answer 1

El cálculo de A (3,4) no es tan fácil o corto como podría parecer al principio de los pequeños valores del argumento nts. La complejidad (número de pasos de iteración) de la función de Ackermann crece muy rápidamente con sus argumentos, al igual que el resultado calculado.

Aquí es la definición de la función de Ackermann de Wikipedia:

Como se puede ver, en cada iteración, el valor de m disminuye hasta que alcanza en lo que será el último paso, en cuyo punto el valor final de n (+1) le da la respuesta. Entonces, para la respuesta, solo necesita rastrear cómo cambia n a medida que avanza por las iteraciones recursivas. Para saber por qué la función de Ackermann crece tan rápido, puede echar un vistazo a la subsección this de la wiki.

Como Joran Beasley ya ha mencionado, A (3,4) es de hecho 125, como está escrito en Wikipedia. Sin embargo, el proceso para llegar a este resultado no es muy corto. De hecho, como descubrí, es necesario calcular por recursión valores de funciones de Ackermann para obtener A (3,4), el número de iteraciones requeridas es aproximadamente proporcional a eso.

Si aún desea visualizar cómo se llega a este resultado, puede echar un vistazo a this page, que anima el cálculo de cada paso de recursión. Tenga en cuenta, sin embargo, que A (3,4) demorará una eternidad para terminar de animar aquí, pero al menos es posible que tenga una idea del proceso con argumentos más pequeños.

Answer 2

ackerman(3,4) 

=ackerman(2,ackerman(3,3)) = ackerman(2,61) #ackerman(3,3) = 61 ... 
=ackerman(1,ackerman(2,60)) = ackerman (1,123) #ackerman(2,60) = 123... 
=ackerman(0,ackerman(1,122)) = ackerman (0,124) #ackerman(1,122) = 124... 
= 124+1 = 125 

ver http://goo.gl/jDDEA aquí para visualizar ackerman(2,3) (que era demasiado largo para visualizar 3,4)

Answer 3

Aquí es una muy buena descripción de lo que es, para qué sirve y su lugar en la teoría de la computación http://en.wikipedia.org/wiki/Ackermann_function

Answer 4

Aquí hay una versión que imprime una explicación:

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(2,2) 

Con argumentos 2,2 la salida es esto.(Con 3,4 se hace ya un poco demasiado)

A(2,2) 
A(1,A(2,1)) 
A(1,A(1,A(2,0))) 
A(1,A(1,A(1,1))) 
A(1,A(1,A(0,A(1,0)))) 
A(1,A(1,A(0,A(0,1)))) 
A(1,A(1,A(0,2))) 
A(1,A(1,3)) 
A(1,A(0,A(1,2))) 
A(1,A(0,A(0,A(1,1)))) 
A(1,A(0,A(0,A(0,A(1,0))))) 
A(1,A(0,A(0,A(0,A(0,1))))) 
A(1,A(0,A(0,A(0,2)))) 
A(1,A(0,A(0,3))) 
A(1,A(0,4)) 
A(1,5) 
A(0,A(1,4)) 
A(0,A(0,A(1,3))) 
A(0,A(0,A(0,A(1,2)))) 
A(0,A(0,A(0,A(0,A(1,1))))) 
A(0,A(0,A(0,A(0,A(0,A(1,0)))))) 
A(0,A(0,A(0,A(0,A(0,A(0,1)))))) 
A(0,A(0,A(0,A(0,A(0,2))))) 
A(0,A(0,A(0,A(0,3)))) 
A(0,A(0,A(0,4))) 
A(0,A(0,5)) 
A(0,6) 
7 

Answer 5

Aquí es una implementación de Java:

/* 
* To change this template, choose Tools | Templates 
* and open the template in the editor. 
*/ 

package ackerman; 
import java.util.Vector; 

    /** 
    * 
    * @author LajosArpad 
    */ 

    public class Main { 
     public static String status = "ackerman(3, 4)"; 
    public static int ackerman(int m, int n) 
    { 
     String temp = status.substring(status.lastIndexOf("ackerman")); 
     while (temp.indexOf("))") >= 0) 
     { 
      temp = temp.substring(0, temp.length() - 2); 
     } 
     boolean foo = status.indexOf(")") == status.lastIndexOf(")"); 
     String t1 = foo ? "" : status.substring(0, status.lastIndexOf("ackerman") - 1); 
     String t2 = foo ? "" : status.substring(status.lastIndexOf("ackerman")); 
     if (t2.length() > 0) 
     { 
      t2 = t2.substring(t2.indexOf(")") + 1); 
     } 
     if (m == 0) 
     { 
      status = t1 + (n + 1) + t2; 
      System.out.println(" = " + status); 
      return n + 1; 
     } 
     else if (n == 0) 
     { 
      status = t1 + "ackerman(" + (m - 1) + ", 1)" + t2; 
      System.out.println(" = " + status); 
      return ackerman(m - 1, 1); 
     } 
     else 
     { 
      status = t1 + " ackerman(" + (m - 1) + ", ackerman(" + m + ", " + (n - 1) + "))" + t2; 
      System.out.println(" = " + status); 
      return ackerman(m - 1, ackerman(m, n - 1)); 
     } 
    } 

     /** 
     * @param args the command line arguments 
     */ 
     public static void main(String[] args) { 
      System.out.println(Main.ackerman(3, 4)); 
      // TODO code application logic here 
     } 

    } 

Sólo tiene que ejecutar el código y sabrá cómo funciona Ackerman. No domino Python, pero espero que eso no sea un problema.

Answer 6

def ackermann(m,n): 
    """computes the value of the Ackermann function for the input integers m and n. 
     the Ackermann function being: 
     A(m,n)=n+1    if m=0 
      =A(m-1,1)   if m>0 and n=1 
      =A(m-1,A(m,n-1) if m>0 and n>0""" 
    if m==0: 
     print (n+1) 
     return n+1 
    elif m>0 and n==0: 
     print ("ackermann(",m-1,",",1,")")           #just 2 chk intrmdt val. and no. of steps invlvd.can be dltd if necessary 
     return ackermann(m-1,1) 
    elif m>0 and n>0: 
     print ("Ackermann(",m-1,",","Ackermann(",m,",",n-1,")",")")     #just 2 chk intrmdt val. and no. of steps invlvd.can be dltd if necessary 
     return ackermann(m-1,ackermann(m,n-1)) 

Simplemente haga una simple modificación en su código para que el programa imprima cada paso en lugar de solo el resultado. El código debe parecerse algo a lo que está al final de esta página. Ejecútelo (puede tardar unos segundos) y luego podrá apreciar cómo se calcula una función de Ackermann.