アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

8.1

 厳然たる事実

257

いずれにせよ、これは「チャーチ

-

チューリングのテーゼ」であって「チャーチ

-

チューリング

の定理」ではありません。これは証明可能な数学的表明ではなく、非形式的な主張にすぎな

いためです。純粋に数学的言語で表現できないので、数学的証明を組み立てるすべがありま

せん。とはいえ、この主張は、計算の本質に関する私たちの直感とアルゴリズムができること

の証拠に一致しているので、正しいはずだと広く信じられています。しかし、いまだに「テー

ゼ」と呼ばれているという事実は、ピタゴラスの定理のような証明されたものとは違うことを

思い出させてくれます。

このチャーチ- チューリングのテーゼが示唆しているのは、チューリングマシンはその単純さにもか

かわらず、人間が単純な命令によって原理的に可能なあらゆる計算を実行できるだけの能力を備えて

いるということです。多くの人がさらに踏み込んで、「アルゴリズムをコード化する試みはすべて、

チューリングマシンと能力的に等価な万能システムに行き着くため、これ以上のことをするのは不可能

だ。現実世界のコンピュータやプログラミング言語は、どれもチューリングマシンと同等のことができ

るだけで、それ以上のことはできない」と主張しています。チューリングマシンよりも強力な機械（未

知の物理法則を使うことができ、想像の域を越えたタスクを「アルゴリズム」として実行してしまうよ

うな機械）を果たして構築できるのか、はっきりとはわかりませんが、今のところ、そのような方法が

わかっていな