kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

Scheme手習い(15) 部分関数と全関数(2)

littleschemer

部分関数と全関数の話その２

コラッツの関数と呼ばれるやつ

  • 1なら終わり
  • 偶数なら2で割る
  • 奇数なら3を掛けて1を足す

たったこれだけの関数なのに、必ず終わるかどうか、つまり全関数かどうかは証明されていません
きっと全関数だろうとは思われてるみたい

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

終わるときはいつも1を返すんですけどさすがに面白くないので
何回再帰呼び出ししたかを返すようにしてみました

(define C2
  (lambda (n c)
    (cond ((one? n) c)
          (else (cond ((even? n) (C2 (/ n 2) (add1 c)))
                      (else (C2 (add1 (* 3 n)) (add1 c))))))))

(define C2list
  (lambda (n to)
    (display (format "~a " (C2 n 0)))
    (cond ((= (modulo n 10) 0) (newline)))
    (cond ((< n to) (C2list (add1 n) to)))))

1から100までの値を表示させてみました

0 1 7 2 5 8 16 3 19 6 
14 9 9 17 17 4 12 20 20 7 
7 15 15 10 23 10 111 18 18 18 
106 5 26 13 13 21 21 21 34 8 
109 8 29 16 16 16 104 11 24 24 
24 11 11 112 112 19 32 19 32 19 
19 107 107 6 27 27 27 14 14 14 
102 22 115 22 14 22 22 35 35 9 
22 110 110 9 9 30 30 17 30 17 
92 17 17 105 105 12 118 25 25 25

わかりません

突然100を超えることがあるんでコンピュータが計算してくれるのでなければ確かめる気がしません
n = 31で106になりますがその後そんなに増えていってる感じはしません
100000までやってみたら350が最高でした
コンピュータさまさまです
100000までの値で最大値を更新したところだけプロットしてみました

f:id:kb84tkhr:20160515130512p:plain

なんか対数っぽいのでX軸を対数目盛に

f:id:kb84tkhr:20160515130628p:plain

これはよく乗ってると言っていいんでしょうか
ガウスの素数定理みたいな？
まあでも素数と「3を掛けて1を足す」とかじゃ格が違う感じ

あと2回、3回と同じ数字が続くことが多いですね
これはかなり不思議
となりあった数のコラッツ数（って言うのかな）が同じになりやすい理由って特に思いつかないんですが

次
アッカーマン関数

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

今度は

Aは常に答えを返しますか。

はい、全関数です。

だそうなので安心して(？)ちょっと計算させて、一般項を予想してみました

(A 0 n) = n + 1
(A 1 n) = n + 2
(A 2 n) = 2n + 1
(A 3 n) = 2^(n+3) - 3

増え方の増え方が激しいです

(A 4 0) = 13 = 2^2 - 3
(A 4 1) = 65533 = 2^2^2^2 - 3

(A 4 2)は計算が終わらないのであきらめました

手がかりが少なすぎてわかりませんけれども2乗を2(n+1)回繰り返す、であっても大変
ヘタして2乗を2^(n+1)回繰り返す、だったらとんでもない増え方です
足す1と引く1と再帰呼び出ししか使ってないのに

(A 5 n)なんて想像するだに恐ろしい

アッカーマン関数はものすごい増え方をする関数ですが
巨大数マニアにとってはまだまだ入り口にすぎないようです
面白いかも？と思われた方はこちらをどうぞ

(A 4 3)は何ですか。

現実的な問題として、答えは得られないでしょう。

どういう意味ですか。

(A 4 3)の値が求まるずっと前に、今読んでいるページは朽ち果ててしまうでしょう。

全関数だからといって油断してると大変なことになるよというお話

そこで
ある関数が停止するかを判定してくれるwill-stop?という関数があるといいなあ
と話が続きますが残念ながらそうは問屋がおろしてくれません
関数自身を処理するプログラムなんてLispっぽいですけどね

  • will-stop?があると仮定する
  • 関数を引数に取り、will-stop?で判定して、真ならば無限ループ、偽ならば真を返して停止する関数last-tryを作る
  • last-tryにlast-try自身を渡すとどうなるか
  • last-tryが停止するとすると、will-stop?は真なので無限ループする。おかしい
  • last-tryが停止しないとすると、will-stop?は偽なので停止する。おかしい
  • そもそもwill-stop?があると仮定したのがおかしい

残念

これは異常なことですか。

はい。そうです。will-stop?は正確に記述できるけれども我々の言語では定義できない最初の関数です。

この問題に関してほかの方法はありますか。

いいえ。ありがとう Alan M. Turing(1912〜1954) と Kurt Godel(1906〜1978)。

Godelは有名な「ゲーデルの不完全定理」というやつでぱっと見は違うけれども
実は同じことを言ってます
上記はTuringがいわゆるチューリング・マシンを使って示したときのあらすじ
に違いないと想像
あとアロンゾ・チャーチという人もラムダ計算で同じ結果を出しています
たぶんそのはず

チューリングとゲーデルは一般向けの書籍もたくさん出てるんですが
チャーチに関する本は見かけたことがありません
業績としては負けてないような気がするんですが

チューリングとゲーデルみたいな波瀾万丈の人生じゃないんですかね
ブルーバックスくらいのレベルで出してくれるといいんですけど