計算機プログラムの構造と解釈 問題1.10

次の手続きはAckermann関数という数学関数を計算する。

(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))

次の式の値は何か。
(A 1 10)

(A 1 10)
(A 0 (A 1 9))
(A 0 (A (0 A(1 8))
中略
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
1024

(A 2 4)

(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)
中略：先ほどの問題より、2^16になることが解る。
65536

(A 3 3)

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)
中略：先ほどと同じ問題なので65536
65536

Aを上で定義した手続きとして、次の手続きを考える。
(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))
正の整数nに対して手続きf,gおよびhが計算する関数の簡潔な数学的定義を述べよ。
例えば(k n)は
5n^2を計算する。

(A 0 n) は2*n
(A 1 n) は2^n
(A 2 n) は・・・・・なんだ・・・・あー・・・プロセスの4行目、ここだ。
(A 1 (A 1 (A 1 (A 2 1))))
y=1 だから次のプロセスは
(A 1 (A 1 (A 1 2)))となって、(A 1 n)は2^nだから、
(A 1 (A 1 2^2))
(A 1 2^2^2)
2^2^2^2


つまり、(A 2 n)は2^2^2^2^…^2 =
テトレーション (tetration)

アッカーマン関数
テトレーションでもなかなか表現できないくらい大きな数を生成する関数。
性能測定などに使われる。あんま興味なし。