Función de Ackermann versus n bucles anidados

Question

Estoy trabajando mi camino a través de un libro sobre computación (Minksy 1967) y estoy teniendo dificultades para relacionar una función recursiva con una función definida en términos de bucles. En concreto, pregunta para encontrar la relación entre dos funciones:

La función de Ackermann (todo el código en Python):

def a(n,m): 
    if n==0: 
     return m+1 
    if m==0: 
     return a(n-1,1) 
    return a(n-1,a(n,m-1)) 

y una función que calcula con n bucles anidados:

def p(n,m): 
    for i_1 in range(m): 
     for i_2 in range(m): 
      ... 
      for i_n in range(m): 
        m+=1 

Un forma recursiva de escribir esto (con un bucle) es:

def p(n,m): 
    if n==0: 
     return m+1 
    for i in range(m): 
     m=p(n-1,m) 
    return m 

O una repetición completa ive manera de escribirlo sería:

def p(n,m): 
    return P(n,m,m) 
def P(n,k,m): 
    if n==0: 
     return m+1 
    if k==1: 
     return P(n-1,m,m) 
    m=P(n,k-1,m) 
    return P(n-1,m,m) 

¿Hay alguna manera simple estas dos funciones están relacionadas? Siento que estoy arrastrándome en la niebla, cualquier idea que me puedas dar sobre cómo abordar este tipo de problemas sería muy apreciada. Además, ¿hay alguna manera de implementar la función de ciclo completamente recursiva sin la introducción de un tercer parámetro? Gracias.

Answer 1

Uhm ... No creo que esto te ayude demasiado, estoy un poco desconcertado también, pero aquí están mis pensamientos.

• Ackerman (0, m) == p (0, m)
• Ackerman (1, m + 1) == p (1, m)

editar - Esperar I creo que he copiado la función. Lo pensaré más tarde, ¡y si pienso en algo lo actualizaré!