アッカーマン関数

アッカーマン関数（アッケルマン関数・Ackermann function）という関数があります。

def ack(m, n):
    """アッカーマン関数"""
    if m == 0:
        return n + 1
    elif n == 0:
        return ack(m - 1, 1)
    else:
        return ack(m - 1, ack(m, n - 1))

一見、ちょっと奇妙なだけの関数ですが、実は原始再帰的でない関数

つまり、ループを使って書き直せない関数なのです！

たとえば、Nの階乗は、原始再帰的関数です（つまりループで書けます）。
ちなみに、
こちら
で、原始再帰的関数の定義が、Pythonで解説されています。

def fact(n):
    """数学的定義に近い階乗関数"""
    if 0 < n:
        return n * fact(n - 1)
    else:
        return 1

def fact(n):
    """ループを使って書いた階乗関数"""
    v = 1
    while 0 < n:
        v = v * n
        n = n - 1
    return v

しかし、アッカーマン関数は、どうやってもループには直せない事が証明されています。

どんなふうに？それは勉強中（^　^）。

「でも、アッカーマン関数も、ループ＋スタックになら書き直せるよ。」

って、Pythonメーリングリストの優しいお兄さん達が教えてくれました。

こうします。

def ack(m, n):
    """ループとスタックで書き直したアッカーマン関数"""
    stack = []
    while True:
        if m == 0:
            n += 1
            if stack:
                m = stack.pop()
            else:
                return n
        elif n == 0:
            m -= 1
            n = 1
        else:
            stack.append(m-1)
            n -= 1

これ、何をやっているのか、考えてみました。

ackで、m > 0 and n > 0の場合、

ack(m, n) = ack(m - 1, ack(m, n - 1))

さらにn - 1 > 0 の場合、右辺の右側、ack(m, n - 1)を展開し、

ack(m, n) = ack(m - 1, ack(m - 1, ack(m, n - 2)))

右辺の、ackの引数の部分だけ書くと、こんな感じのツリーになります。

   ------------------------- n - 2
  |        |        |
m - 1    m - 1      m

ackをドンドン展開していくと、このツリーはドンドン伸びてゆく

   ------------------------------(中略) --------- 0
  |        |        |        |              |
m - 1    m - 1    m - 1    m - 1            m

   ------------------------------(中略) --------- 1
  |        |        |        |              |
m - 1    m - 1    m - 1    m - 1          m - 1

伸びきると、さらに伸びるか縮みだすかは、mの値によって変わりますが

ともかくこのツリー、

いきなり真ん中が抜け落ちたり、

左端が延びたりという事は、

絶対ありません！

変化は常に、右端で起こります。

つまり、これは、スタックで表せるということです。

上のループ＋スタックで書き直したackの関数定義内のstackは、

            ------------------------------(中略) --------- 1
           |        |        |        |              |
ココ ->  m - 1    m - 1    m - 1    m - 1          m - 1  <- ココ

ツリーの下に伸びた枝の値（m - 1, m - 1, m - 1, ・・・）を表現しているのです。

そして、ループの中で、直接自然数m, nを操作するのではなく、

このツリーを操作する事で、アッカーマン関数を計算するのです。

って、事は一般に再帰的関数は、

呼び出しを表すツリーを操作するループとして表現できるということかしら？

ツリーがスタックで表現できるかはわからないけども、

ポインタがあれば、ツリーは作れるわけで・・・

あとで調べてみよう。

でも基礎論の本って少ないんだよなぁ・・・