問題1.10

Ackermann関数について

そもそもAckermann関数ってなんだ？って話なので、Wikipediaで調べてみる。
アッカーマン関数 - Wikipedia

今ひとつ分からないので実際に書いて動かしてみる。

(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)
; 1024

(A 2 4)
; 65536

(A 3 3)
; 65536

各関数の数学定義については、実際に手でトレースしながら調べてみる。

(define (f n) (A 0 n))
; ==> 2n(これは関数定義を見れば自明なので、トレースする必要無し)

(define (g n) (A 1 n))
; ==> 2^n

; (f n)の解析で (A 0 n) == 2n が分かったので、
; それを利用しながらトレース

; (g 3)
; ==> (A 1 3)
; ==> (A 0 (A 3 2))
; ==> (A 0 (A 2 (A 3 1)))
; ==> (A 0 (A 2 2))
; ==> (A 0 (A 1 (A 2 1)))
; ==> (A 0 (A 1 2))
; ==> (A 0 (A 0 (A 1 1)))
; ==> (A 0 (A 0 2))
; ==> (A 0 4)
; ==> 8

(define (h n) (A 2 n))
; ==> 2^2^2^2^2^.. これをn回

; (g n)の解析で (A 0 n) == 2^n が分かったので、
; それを利用しながらトレース

; (h 2)
; ==> (A 2 2)
; ==> (A 1 (A 2 1))
; ==> (A 1 2)
; ==> 2^2
; ==> 4

; (h 3)
; ==> (A 2 3)
; ==> (A 1 (A 2 2))
; ==> (A 1 (A 1 (A 2 1)))
; ==> (A 1 (A 1 2))
; ==> (A 1 2^2)
; ==> (A 1 4)
; ==> 2^4
; ==> 16

; (h 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 2^2))
; ==> (A 1 (A 1 4))
; ==> (A 1 2^4)
; ==> (A 1 16)
; ==> 2^16
; ==> 65536

; (h 5)
; ==> (A 1 (A 1 (A 1 (A 1 2))))
; ==> (A 1 (A 1 (A 1 4)))
; ==> (A 1 (A 1 16))
; ==> (A 1 65536)
; ==> 2^65536

トレースすることで、おそらく上記の答えになるであろうことは分かったが、
正確に調べるにはどうすればよいか？

このサイトがとても参考になりました。
500 Internal Server Error

なるほど、f(n)を起点として考えればいいのか。

f(n) = 2n

g(n+1) = A(1, n+1) = A(0, A(1, n)) = 2*g(n)
↓
g(n) = 2^n

h(n+1) = A(2, n+1) = A(1, A(2, n)) = 2^h(n)
↓
h(n) = 2^2^2^2^....(n個)

とすると、

i(n) = A(3, n) とする。

i(n+1) = A(3, n+1) = A(2, A(3, n)) = 2^2^2^2^2^...(i(n)個)
↓
i(n) = 2^2^2^...(2^2^2^2^...(n個)個)

かな？(あってるのか？)

なるほど、これは爆発的に計算量が増加しそうだ。