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個)個)
かな？(あってるのか？)
なるほど、これは爆発的に計算量が増加しそうだ。
