内容紹介

■コンピュータと数学の限界に答えを出す！
　イギリスの数学者アラン・チューリングは1936年に、「計算可能数とその決定問題への応用」という論文を発表しました。後に「チューリング機械」と呼ばれる想像上のコンピュータが初めて示された論文です。チューリング機械は有限個の状態をとれる機械がテープのマス目を読み書きするだけのたいへん単純な機械です。それは計算することの原理的な仕組みと限界を明らかにするための機械でした。

　驚くべきことに、あらゆるチューリング機械は一つの整数で表すことができます。そのことは、計算可能な数の全体が可算無限個であり、連続体をなす実数全体のうちのほんの一部でしかないということを意味しているのです。

　さらにチューリングは、テープ上の記号の複写や消去といったチューリング機械の動作のいわばサブルーチンを組み合わせて、あらゆるチューリング機械の動作を模倣できる「万能機械」を構成しました。万能機械は今日のコンピュータの原型のようなものです。この観点から見ると、一切のデジタルコンピュータはチューリング機械の実用版なのです。

　チュリーングはこの論文で、「機械がいつかゼロを印字するかどうかを決定する一般的な方法はない」ことを示します。そして、ヒルベルトが提示した「決定問題」という数学的な問題をこの問題に帰着させました。すなわち、ヒルベルトの提起した決定問題は解けないということです。チューリングの結論は「解けない問題はない」という当時の数学者たちの信念を打ち砕き、（当時はまだ存在していなかった）コンピュータと数学の限界を示すものでした。チューリングの定理はコンピュータサイエンスの金字塔として今も燦然と輝いています。

　本書はチューリングの「計算可能数とその決定問題への応用」の原論文を楽しむためのガイドブックです。原論文をゆっくりと、逐一注釈していきます。原論文を理解するために必要な数学的な準備や、戦争の時代を生きたチューリングの波乱の生涯にもたっぷりとページを割いて話を進めていきます。



チャールス・ペゾルド（Charles Petzold）
『CODE コードから見たコンピュータのからくり』（日経BP社）などプログラミング分野の書籍を多数執筆。