Funkcja Ackermanna kontra n zagnieżdżonych pętli

Question

Pracuję na swój sposób w książce o obliczeniach (Minksy 1967) i mam trudność z powiązaniem funkcji rekursywnej z funkcją zdefiniowaną w kategoriach pętli. W szczególności pyta znalezienie relacji między dwie funkcje:

funkcyjnych Ackermann (cały kod w pytona):

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)) 

i funkcję, który oblicza się z n zagnieżdżonej pętli:

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

A rekursywny sposób zapisu tego (z jedną pętlą) to:

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

Lub w pełni powtarza Sposób pisania byłoby:

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) 

Czy istnieje prosty sposób na powiązanie tych dwóch funkcji? Czuję się jakbym się czołgał we mgle - wszelka wiedza, którą mógłbyś mi przekazać, aby podejść do tego rodzaju problemów, byłaby bardzo doceniona. Czy istnieje sposób na wdrożenie funkcji pętli w pełni rekurencyjnej bez wprowadzenia trzeciego parametru? Dzięki.

Answer 1

Uhm ... Nie sądzę, że to ci bardzo pomoże, jestem też trochę zboczony, ale tu są moje myśli.

• Ackerman (0, m) == P (0, m)
• Ackerman (1, M + 1) == s (1 m)

edycja - czekać I myślę, że wykręciłem funkcję. Dam to więcej myśli później i jeśli coś wymyślę, zaktualizuję!