西尾泰和のブログ

アッカーマン関数を素直に再帰で書いてみました。

>>> def ack(m, n, indent = 0):
	print "  " * indent + "ack(%d, %d)を計算…" % (m, n)
	if m == 0:
		result = n + 1
	elif n == 0:
		result = ack(m - 1, 1, indent + 1)
	else:
		result = ack(m - 1, ack(m, n - 1, indent + 1), indent + 1)
	print "  " * indent + "ack(%d, %d)は%d。" % (m, n, result)
	return result

>>> ack(2, 2)
ack(2, 2)を計算…
  ack(2, 1)を計算…
    ack(2, 0)を計算…
      ack(1, 1)を計算…
        ack(1, 0)を計算…
          ack(0, 1)を計算…
          ack(0, 1)は2。
        ack(1, 0)は2。
        ack(0, 2)を計算…
        ack(0, 2)は3。
      ack(1, 1)は3。
    ack(2, 0)は3。
    ack(1, 3)を計算…
      ack(1, 2)を計算…
        ack(1, 1)を計算…
          ack(1, 0)を計算…
            ack(0, 1)を計算…
            ack(0, 1)は2。
          ack(1, 0)は2。
          ack(0, 2)を計算…
          ack(0, 2)は3。
        ack(1, 1)は3。
        ack(0, 3)を計算…
        ack(0, 3)は4。
      ack(1, 2)は4。
      ack(0, 4)を計算…
      ack(0, 4)は5。
    ack(1, 3)は5。
  ack(2, 1)は5。
  ack(1, 5)を計算…
    ack(1, 4)を計算…
      ack(1, 3)を計算…
        ack(1, 2)を計算…
          ack(1, 1)を計算…
            ack(1, 0)を計算…
              ack(0, 1)を計算…
              ack(0, 1)は2。
            ack(1, 0)は2。
            ack(0, 2)を計算…
            ack(0, 2)は3。
          ack(1, 1)は3。
          ack(0, 3)を計算…
          ack(0, 3)は4。
        ack(1, 2)は4。
        ack(0, 4)を計算…
        ack(0, 4)は5。
      ack(1, 3)は5。
      ack(0, 5)を計算…
      ack(0, 5)は6。
    ack(1, 4)は6。
    ack(0, 6)を計算…
    ack(0, 6)は7。
  ack(1, 5)は7。
ack(2, 2)は7。
7

うひゃあ。たかが(2, 2)でこんなことになるのか…。すさまじいなぁ。

__

横軸m、縦軸nで原点を左上隅にして値を表示してみました。

      2   3   5  13
  2   3   5  13    
  3   4   7  29    
  4   5   9  61    
  5   6  11 125    
  6   7  13 253    
>>> 61 - 29
32
>>> 125 - 61
64
>>> 253 - 125
128

つまりack(m, n)は

	if m == 0:
		result = n + 1
	if m == 1:
		result = n + 2
	if m == 2:
		result = 3 + n * 2
	if m == 3:
		result = 8 * (2 ** n) - 3

ということみたいです。なおack(4, 0)は13で、ack(4, 1)は65533(これは2 ** 16 - 3)、ack(4, 2)は

>>> from math import log
>>> log(ack(4, 2))
45426.093625176574
>>> log(ack(4, 2) + 3) / log(2)
65536.0

というものすごく大きな数です。2万桁弱。アッカーマン関数がとんでもない関数だということがよくわかりました。

__ m = 0 の時 (n + 1)、m = 1 の時 (n + 1) + 1、m = 2 の時 (n + 1) * 2 + 1、と整理すると m = 3 の時 4 * (2 ** (n + 1) - 1) + 1 になって美しくない。 整理の仕方を間違えていたようです。まず記号を定義しないといけなさそうです。2 * n は 2 を n回足したもの、つまり + という演算をn回繰り返したものです。これを 2 +*n と書くことにします。次に、2 ** n は2をn回掛け合わせた物です。つまり+*という演算をn回繰り返したものなので、2 +**nと書くことにします。最後に、+**という演算をn回繰り返すことは+***nと書くことにします。そうするとアッカーマン関数は

m = 1のとき (2 +(n + 3)) - 3
m = 2のとき (2 +*(n + 3)) - 3
m = 3のとき (2 +**(n + 3)) - 3
m = 4のとき (2 +***(n + 3)) - 3

になる、と書けます。美しい。なお誤解を避けるために書いておきますと、数字の並びから推測してこうなりそうだと言っているだけで証明はしていません。

__ あれ？違う？

ああ、そうか、単に「n回繰り返す」と言っちゃダメなんですね。掛け算までは対称だからそれでも問題は起きないのだけども、累乗は対称ではないので(2 ** (2 ** (2 ** 2)))と(((2 ** 2) ** 2) ** 2)が一致しないわけです。正しいのは前者。