ISEGORIA / 数学百科事典
論理と計算可能性：何が計算できるか
チューリング機械・停止問題の背後にある対角線論法・ゲーデル数を扱います。
前提知識: 集合論と離散数学
予想してから操作し、計算例と問いで理解を確かめてください。グラフは数式の図示であり、証明ではありません。
1. チューリング機械を一歩ずつ
ヘッドがマスを一つ読み、有限の表を参照し、書き込み、一マス動き、状態を変えます。それだけです。機械を選んで実行の過程をたどってください。下の時空図はすべての時刻のテープを積み重ねるので、計算全体を一度に見られます。
計算例. 4 状態のビジービーバーは空白のテープから始めて 107 ステップで停止し、13 個の 1 を残します。停止する 4 状態 2 記号の機械が残せる最大数です。
注意点. ここでの表はどれも固定された有限のものです。このモデルを万能にするのは、ある固定された機械が別の機械の表をテープから読み取って模倣できることです。
なぜ一般にはビジービーバー関数を計算できないのですか？
それを計算するプログラムがあれば、停止するすべての実行の長さを抑えられ、停止問題を判定できてしまうからです。
2. 対角線論法
あるプログラム H が、すべてのプログラム i と入力 j について i が j で停止するかどうかを判定できると仮定します。そこで D を作ります。D は入力 i に対して、表が示すプログラム i の i での振る舞いと逆のことをします。D は対角線上ですべての行と異なるので表に含まれません。しかし表はすべてのプログラムを並べたはずでした。マスをクリックして表を変えてください。どう選んでも矛盾は残ります。
計算例. \(D\) がプログラム番号 \(d\) なら、成分 \(H(d,d)\) は自分自身の逆と等しくなければなりません。
注意点. 表示している表は仮想的なものです。成分は計算ではなく、あなたか乱数の種が決めています。論証はどんな表にも当てはまり、それこそが要点です。
この矛盾はどの仮定を否定しますか？
H が常に停止して正しい答えを返すプログラムとして存在するという仮定です。
3. ゲーデル数
各記号に番号を与え、式を一つの数に変えます。k 番目の素数を k 番目の記号の番号乗したものを掛け合わせるのです。素因数分解の一意性によりこの数は復号できるので、式についての命題が数についての命題になります。パレットから自分の式を作ってみてください。
計算例. 表の番号では \(\ulcorner 0=0\urcorner=2^{6}\cdot3^{5}\cdot5^{6}=243{,}000{,}000\) です。
注意点. 個々の番号の付け方は約束事にすぎません。重要なのは符号化と復号が機械的に行えることで、それにより証明可能性が算術的な性質になります。
なぜ番号を並べて書くだけでなく素数を使うのですか？
積は算術が扱える一つの自然数であり、素因数分解の一意性がそれをただ一つの記号列に復号できることを保証するからです。