昔々
あるところに、アラン・チューリングという少年がいました。
チューリング少年は、数学の授業で、「決定問題」という未解決問題に出会いました。
これこそが、今我々が見ているコンピュータが生まれるきっかけとなったのです。
決定問題とは
「証明可能か不可能かを機械的な手順で計算できるか」です。
チューリング少年は、機械的な手順で厳密に解けない問題が存在することを直感的に感じました。
つまり、決定問題を否定できると思ったんですね。
そう、この命題を否定するために生まれたのが、チューリングマシンであり、我々が今見ているコンピュータであります。
チューリングマシンとは
「機械的な計算手順を表す理論的な計算モデル」です。
チューリングマシンは空想上の概念であり、それをハードウェアで実現できることを示したのが、フォン・ノイマンという人です。
チューニングはいかにして決定問題を否定したのか？
命題を否定するためには、
「証明可能か不可能かを機械的な手順で計算できない」問題を一つでも見つければいいわけです。
そこでチューニングが目を付けたのは、
【機械的な手順で「計算手順が止まるか」or「永遠に動き続けるか」知ることができるか】という問題です。
ややこしいですね。
これ即ち停止性問題です
【「計算手順が止まるか」or「永遠に動き続けるか」知ることができる計算手順】をAとします。
Aは
①「停止する計算手順」を入力するとAは「停止する」と出力します。
②「停止しない計算手順」を入力するとAは「停止しない」と出力します。
背理法でAがないことを証明しましょう。
Aを改造します
Aを改造した計算手順をBとします。
Bは
①「停止する計算手順」を入力するとBは何も出力せず「停止しない処理」に入ります。
②「停止しない計算手順」を入力するとBは「停止しない」と出力します。
Bに計算手順を入力した時、
「Bが停止していない状態」->①の結果か②の途中かわからない
「Bが停止した状態」->入力は停止しない②で確定
ということになります。
ただ、②は有限時間で終了するので、有限時間後に
「Bが停止していない状態」->入力は①停止するで確定
「Bが停止した状態」->入力は②停止しないで確定
しますね。
BにBを入力したらどうなるか？
Bは立派な計算手順です。つまり、BにBを入力として渡すことも可能です。
ややこしくなるので入力するBは「入力B」、入力をもらうBは「計算B」と呼びましょう。
「計算B」に「入力B」を入力した時、有限時間後に
「計算Bが停止していない状態」->入力Bは①停止するで確定
「計算Bが停止した状態」->入力Bは②停止しないで確定
します。
矛盾
ここで矛盾が生じました。
計算Bが停止しない時、入力Bは停止して、
計算Bが停止する時、入力Bは停止しないのです。
計算Bと入力Bは呼称で区別しただけでしたよね。
ということは、全く同じ計算手順として書き表せるはずです。
つまり、最初の仮定が間違っていたことになります。
【「計算手順が止まるか」or「永遠に動き続けるか」知ることができる計算手順】は存在しないのです。
めでたしめでたし
いやぁー、ハッピーですね！見事に決定問題を否定できました。
ただ、僕は読者の方々に決定問題が否定できることを理解してもらいたかったのではありません。
ここからが本番です。
昔々
あるところに、僕がいました。
僕の通う大学に、こんなことを言う教授がいました。
「停止性問題から、コンピュータはコンピュータを理解できないということがわかった。つまり、人間は人間を理解できないのではないか。」
面白いことをおっしゃいますね。
確率的に結論を導く人間
機械的手順の対義語は確率的手順です。
人間の脳は確率的な挙動をします。
機械的手順では「計算手順が止まるか」or「永遠に動き続けるか」知ることができないとわかりました。しかし、人間はそれを容易に理解できます。
人間の判断は確率に基づいているから、「計算手順が止まるか」or「永遠に動き続けるか」という判断をできるんですね。正確にはできるのではなく、厳密性を無視することができるんです。
半導体に確率的な処理をさせるニューロフィックエンジニアリングという分野があるので、興味がある人はぜひ調べてみてください。
というわけで本稿の目的はニューロフィックエンジニアリングの宣伝でした。笑