日: 2014年1月31日

今度はアッカーマン関数だ。Wikipedia の解説を読んでもよくわからないんだけど、引数が大きくなると爆発的に計算量が大きくなるらしい。

(use mymodule)

(define A
  (lambda (n m)
    (cond
      ((zero? n) (add1 m))
      ((zero? m) (A (sub1 n) 1))
      (else (A (sub1 n) (A n (sub1 m)))))))

(print (A 1 0))
(print (A 1 1))
(print (A 2 2))

^o^ > gosh -I. A.scm
2
3
7

といっても、上の例ではすぐに計算が終わって値が返ってくる。ところが (A 4 3) を計算させてみたところ、一晩かかっても終わらなかった。問答では「現実的な問題として、答は得られないでしょう。」と書いてある。
それでもこれは全関数らしい。

こんな関数 C が出てきた。

(define C
  (lambda (n)
    (cond
      ((one? n) 1)
      (else
        ((even? n) (C (o/ n 2)))
        (else (C (add1 (o* 3 n))))))))

これはコラッツの問題だ。
問答の答には「0に対しては値を持ちませんが、それ以外の引数に対して全関数であるかどうかは誰も知りません。ありがとう、Lother Collatz（1910～1990）。」と書いてある。もしコラッツの予想が正しければ全関数だということになるけど、まだ証明されていない。Wikipedia によれば、3 × 2 の53乗までは反例がないことが確かめられているとのこと。