SICP七日目　〜問題1.10

順番的に言えばコードリーディングの更新をするべきときですが深追いしすぎて戻ってこれていないので、先にSICPを更新してしまいます。ぷよクエでやらなければいけないイベントもありませんし、のんびり取り組めました。

問題1.10

実行してみないことには

問題を見る。アッカーマン関数と書いてあるからにはアッカーマン関数について調べてもバチは当たるまい。…とりあえず関数Aは自分自身を定義に含めずに定義できないことは把握した。
とりあえずプログラムを実行してみる。
これをこうして、

(use slib)
(require 'trace)

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

(trace A)

こうじゃ。

gosh> (A 2 1)
CALL A 2 1
RETN A 2
2

(A 3 2)を実行すると、

gosh> (A 2 2)
CALL A 2 2
  CALL A 2 1
  RETN A 2
  CALL A 1 2
    CALL A 1 1
    RETN A 2
    CALL A 0 2
    RETN A 4
  RETN A 4
RETN A 4
4

こうじゃ。
(A 3 3)はな、

gosh>(A 2 3)
CALL A 2 3
  CALL A 2 2
    CALL A 2 1
    RETN A 2
    CALL A 1 2
      CALL A 1 1
      RETN A 2
      CALL A 0 2
      RETN A 4
    RETN A 4
  RETN A 4
  CALL A 1 4
    CALL A 1 3
      CALL A 1 2
        CALL A 1 1
        RETN A 2
        CALL A 0 2
        RETN A 4
      RETN A 4
      CALL A 0 4
      RETN A 8
    RETN A 8
    CALL A 0 8
    RETN A 16
  RETN A 16
RETN A 16
16

こうなるんじゃ。
それでA(2 4)は

(A 2 4)
CALL A 2 4
  CALL A 2 3
    CALL A 2 2
      CALL A 2 1
      RETN A 2
      CALL A 1 2
        CALL A 1 1
        RETN A 2
        CALL A 0 2
        RETN A 4
      RETN A 4
    RETN A 4
    CALL A 1 4
      CALL A 1 3
        CALL A 1 2
        RETN A 4
        CALL A 0 4
        RETN A 8
      RETN A 8
      CALL A 0 8
      RETN A 16
    RETN A 16
  RETN A 16
  CALL A 1 16
    CALL A 1 15
      CALL A 1 14
        CALL A 1 13
        RETN A 8192
        CALL A 0 8192
        RETN A 16384
      RETN A 16384
      CALL A 0 16384
      RETN A 32768
    RETN A 32768
    CALL A 0 32768
    RETN A 65536
  RETN A 65536
RETN A 65536
65536

A(2 1)→2、A(2 2)→4、A(2 3)→16、A(2 4)→65536です。計算過程を見てみるとA(2 n)はA(2 n-1)の計算過程を再帰的に呼び返しているので、まあそんな感じなんだなと。単にこの4つの数字だけを見てパズル的に法則性を解いてしまうと、A(2 1)は $2$ 、A(2 2)は( $2^2$ ）、A(2 3)は $2^{2^2}$ 、A(2 4)は $2^{2^{2^2}}$ だよなーとなります。(今、texってここまで指数部書けるのかのすげえって思った)　では、A(2 5)は $2^{2^{2^{2^2}}}$ ですかね。

答え

(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$ 　
(define (h n) (A 2 n))→ $2^{2^{...^{2}}}$ 　←n-1個分右上に指数部が並ぶ。「関数の簡潔な数学的定義を述べよ」だからこんな答えでいいでしょうか…。だめかもしらん。