Ackermann Function Understanding

Question

Mi risulta difficile capire come funziona la funzione Ackermann. Penso che la mia comprensione della ricorsione sia difettosa?

Ecco il codice in 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)) 

Se faccio la chiamata di funzione di naive_ackermann (3,4), come e perché faccio finire per ottenere 125?

I commenti saranno apprezzati.

Grazie

Answer 1

Il calcolo di A (3,4) non è così facile o breve come potrebbe sembrare a prima vista dai piccoli valori dell'argume nti. La complessità (numero di passaggi di iterazione) della funzione di Ackermann cresce molto rapidamente con i suoi argomenti, così come il risultato calcolato.

Qui è la definizione della funzione Ackermann Wikipedia:

Come si può vedere, ad ogni iterazione, il valore di m diminuisce fino a raggiungere in quello che sarà l'ultimo passaggio, a quel punto il valore finale di n (+1) ti dà la risposta. Quindi, per la risposta, è sufficiente tenere traccia di come n cambia mentre si passa attraverso le iterazioni ricorsive. Perchè la funzione di Ackermann cresce così rapidamente, puoi dare un'occhiata alla sottosezione this del wiki.

Come Joran Beasley ha già menzionato, A (3,4) è in effetti 125, come scritto in Wikipedia. Tuttavia, il processo per arrivare a questo risultato non è molto breve. Infatti, come ho scoperto, è necessario calcolare per ricorsione i valori delle funzioni di Ackermann per ottenere A (3,4), il numero di iterazioni richieste è approssimativamente proporzionale a quello.

Se si desidera visualizzare ancora il modo in cui questo risultato è arrivato, è possibile dare un'occhiata a this page, che anima il calcolo di ogni passo di ricorsione. Attenzione, però, che A (3,4) impiegherà un'eternità per terminare l'animazione qui, ma almeno potresti avere un'idea del processo con argomenti più piccoli.

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 

vedere http://goo.gl/jDDEA qui per visualizzare ackerman(2,3) (che era troppo lungo per visualizzare i 3,4)

Answer 3

Ecco una buona descrizione di cosa si tratta, cosa serve e il suo posto nella teoria della computabilità http://en.wikipedia.org/wiki/Ackermann_function

Answer 4

Ecco una versione che consente di stampare una spiegazione:

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 argomenti 2,2 l'output è questo.(Con 3,4 diventa già un po 'troppo)

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

Ecco un'implementazione 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 
     } 

    } 

basta eseguire questo codice e si sa come funziona Ackerman. Non parlo correntemente Python, ma spero che non sia 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)) 

Basta apportare una semplice modifica al codice in modo che il programma stampi ogni passaggio anziché solo il risultato. Il codice dovrebbe somigliare a quello che si trova alla fine di questa pagina. Eseguilo, (potrebbe richiedere qualche secondo) e quindi puoi apprezzare come viene calcolata una funzione di Ackermann.