ビジービーバー関数と神託

チューリングマシンは習ったと思う。
無限の長さのテープの上を動く、記憶を持った、テープを書き換えられる機械。
わからない人はwikipediaを読むと良いと思う。多分わからなくなる。

神託機械とは、
神託（オラクル、ある種類の問題を1ステップで解く概念上の装置）を持つチューリングマシンである。

例えば巡回セールスマン問題のようなNP困難クラスに属する問題も、「巡回セールスマン問題を解くオラクル」を持つ神託機械にかかれば1ステップで解決される。

実際には今のところそんな便利なものはないので、巡回セールスマン問題は定数時間どころか多項式時間で求めることは不可能だし、近似解を求めるので人類は精一杯である。

ビジービーバー関数のような、計算不能関数でさえ、神託としては仮定できる。

ビジービーバー関数とは、計算不能関数である。
nを入力として持つビジービーバー関数はΣ(n)と書かれることが多く、
Σ(0)=0、Σ(1)=1、Σ(2)=4、Σ(3)=6、Σ(4)=13、…である。

ビジービーバー関数とは、
・0と1をテープを使って読み書き可能な、
・n個の状態を持つことができるチューリングマシンが
・有限個の1をテープに書き
・有限時間内に終了状態になるときの
・1の個数Σ(n)（もしくはそれまでのステップ数S(n)）
である。

つまり、全て（[4(n+1)]^2n個）のチューリングマシンをシミュレーションして、上の条件をみたす1の個数を求めればいい。¹

だから、Σ(0)=0、Σ(1)=1、Σ(2)=4、Σ(3)=6、Σ(4)=13が知られている。
それならば、ビジービーバー関数を与えてくれる神託機械があれば何ができるか。

S(n)のビジービーバー関数は停止するまでの最大ステップ数を与える。
そしてビジービーバー関数はその定義から有限である。
そして「実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、『計算機で原理上解ける問題』は『チューリング機械で解ける問題』と同じであるといわれている。」出典:Wikipedia

これを使って、フェルマーの最終定理を証明する。
反例を1つ見つけることで証明できるフェルマーの最終定理などは、フェルマーの最終定理を検証するプログラムを書き、それをチューリングマシンに実装する。
もしもフェルマーの最終定理の反例を見つけたら止まるプログラムを実装した場合、（反例を見つけ）有限ステップで終了するか、（フェルマーの最終定理は正しいため反例を見つけず）無限ステップ実行され続けるかである（排中律）。

今までだと、フェルマーの最終定理の反例はどこにあるか全く見当がついていない。
だからフェルマーの最終定理の反例が見つからなかったとしても、もしかしたら1ステップ後に見つかるかもしれないと、待ち続ける。
でも、ビジービーバー関数は有限の値を持つ。
ビジービーバー関数の値が有限だということは、ビジービーバー関数の値よりも多いステップ数を実行してなお停止していない「フェルマーの最終定理の反例を見つけるプログラム」は無限ステップ実行され続ける。
だから、ビジービーバー関数だけのステップを計算して、「フェルマーの最終定理の反例を見つけるプログラム」が停止すれば反例を見つけ、停止しなければフェルマーの最終定理が正しいという結果が得られる（なお、n=6で7.4×10^36534ステップ以上である）出典。

ビジービーバー関数は便利。

神託は便利。

みなさんも神託を使いましょう。

ここからは、便利な神託の使い方の話。

Gott würfelt nicht.

数年前、進路を迷っていた。
サイコロを振ったら3が出たので、進路を東京大学に決めた。

その話をすると、「なんで自分で考えて決めなかったの？」といわれる。
考えなかったわけじゃない。考えた末、サイコロで決めることに決めているのだから。

東京大学に進学したくなかったし、他の大学に進学したいとも思わなかった。もちろん働きたくもなかったし、働かずに将来の不安に怯えることもしたくなかった。
しかも、進路なんて最適解が計算できるわけじゃない。
東京大学に行ったほうが平均年収は高いかもしれないが、優秀な人がいる環境に行ったら比べられてつらいに決まってる。少なくともそういう人はいる。

こんな難しい問題に対して、確信を持って選ぶことができるわけがない。
ネガティブで根に持つタイプは、
迷った末に自分で決めて、不幸になったら、その時の自分を恨むだろう。
他人に相談して決めてもらって不幸になったら、その人を恨むだろう。

だから、サイコロに進路を委ねた。
サイコロと投げることによって出目が決まる過程は美しい。
何を考慮するかとか、いつまでに決めようとか、そんな悩みを全てを圧倒する決定力がある。
誰にも左右できない力によって決められる美しさを思い出しながら、大学生活を送ることができる。

神託としてサイコロを使うとき、偶然に委ねるのは、文字通り神に委ねるのに似ている。
自分の命や進路を自分で管理するなんて恐れ多い。
サイコロは神（託）だ。

サイコロの目に従い不幸になったとしても、少なくともそれにより誰かを恨むことはない。
むしろ、違う選択肢を選んだ場合、もっと不幸になったかもしれないと思う。
サイコロを振った瞬間、選択を委ねたのだから、
Schreiben Sie Gott nicht vor, was er zu tun hat.

1. このように計算可能と思われるが、[4(n+1)]^2n個のチューリングマシンをシミュレーションして、それが有限個の1をテープに書いて、「停止する」かを判断できる基準がない(停止性問題)ので、実は「計算可能」ではない。
   はい。
   お疲れ様でした。
   ビジービーバー関数の値がわかりました。 ↩