読者です 読者をやめる 読者になる 読者になる

アッカーマン関数


アッカーマン関数(アッケルマン関数・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を操作するのではなく、

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


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

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



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

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



あとで調べてみよう。

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