Geek Answers Handbook

Ackerman function against n nested loops

I am working on a book on computation (Minksy 1967), and it is difficult for me to reduce a recursive function to a function defined in terms of loops. In particular, he asked for a connection between two functions:

Ackermann function (all code in 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))

And a function that computes with n nested loops:

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 recursive way to write this (with one loop):

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

Or a fully recursive way to write:

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)

Is there a simple way in which these two functions are connected? I feel like I'm crawling in a fog - any understanding that you could tell me about how to approach these problems would be very useful. Also, is there a way to implement a fully recursive loop function without introducing a third parameter? Thank.

+5
1

... , , , .

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

edit - wait , . , -, !

+1

More articles:


All Articles