6.3  計算機

証明の可能性と計算の可能性

　何が証明できるか、どのような数が計算できるかに関する議論は、さらに深まった。証明できる、あるいは計算できるとは、有限回の手続きで解をうる手順（Feynmanのいうeffective procedure）が存在しなければならない。これについてKleene, Post, Churchなどにより、さまざま計算体系を仮定した計算の可能性に関する議論がなされた。この問題に関して、チューリングA. Turingは、今日の計算機の時代を先取りするような視点から、アプローチした。

抽象化された計算機Turing Machine

Gödelの不完全性定理に刺激を受けたチューリングは、1937年に、On Computable numbersという論文を発表し、この中で後にチューリング・マシンTuring Machineと呼ばれるようになった仮想的な計算機械を記述した。この機械は区切りがつけられた枡をもつ（無限に）長いテープと、そのテープに数字などの記号を書いたり消去したりできるヘッドと、有限の内部状態をもつ機械から構成されている。内部状態は、テープから読み出された情報によって、推移し、ヘッドのなすべき操作を出力する。この部分は、今日では有限オートマトンと呼ばれる仮想的な機械である。テープの部分は、今日のコンピュータのプログラムに相当する。このプログラムを適当に書くことにより、チューリング・マシンは、どんな特別な目的をもったチューリング・マシンの真似をさせることもできる。この意味で、チューリング・マシンにあらゆる仲間の機械の機能を真似させられるという意味で、万能性をもたせることができる。この仮想的な機械は、万能チューリング・マシンUniversal Turing Machine (UTM) と呼ばれる。

この仮想的な機械を利用して、チューリングは、

「計算できるあるいは証明できる問題は万能チューリング・マシンで証明あるいは計算可能である」

という考えを述べた。今日、彼のこの提唱は正しいと受け入れられている。今日まで、チューリング・マシンを原理的に越える機械は提唱されていない。残る問題は効率だけである。例えば、現在話題になっている量子コンピュータのモデルである量子チューリング・マシンが原理的にできることも、古典的なチューリング・マシンと同じである。