今年はアラン・チューリングの生誕100周年にあたります。チューリングは1912年6月23日にロンドンで生まれ、1954年6月7日に41歳の若さで亡くなりました。青酸カリを使った不幸な最後でした。しかしその業績は並はずれています。彼の名前はコンピュータサイエンスの分野の最も権威ある賞である「チューリング賞」に、今も残っています。戦争の時代を生き、第二次世界大戦でドイツの暗号エニグマを解読するのに大きな貢献をしたことでも知られています。

　チューリングという名前を聞くと、「チューリングマシン」を連想する人が多いのではないでしょうか。チューリングマシンとは、有限個の状態をとれる想像上の機械です。ヘッドがテープの右や左に移動して、テープのマス目を読み書きすることしかできません。チューリングマシンは今日のコンピュータの原型であるとされています。

　筆者にもその程度の表面的な知識はあったのですが、チューリングマシンの意義というか、面白さというものがどうもよくわかりませんでした。昔、チューリングの定理がゲーデルの不完全性定理の別な表現になっていると聞いたときには、びっくりしたものです。

　本書『チューリングを読む』は、チューリングが1936年に発表した「計算可能数とその決定問題への応用」という論文を一般向けに解説したガイドブックです。著者のペゾルドはチューリングの論文に逐一注釈を付けています。とはいえ本書は堅苦しい本ではなく、読み物に近い語り口で読者を楽しませてくれます。

　最初の3章はこの論文を読むのに必要な数学的な準備にあてられています。古代アレクサンドリアの碑文に刻まれたディオファントスの謎々の話から始まり、無限集合の可算濃度と連続体濃度の区別、カントールの対角線論法、数学的体系の完全性や決定可能性といった話をゆっくりと、わかりやすく語っています。

　筆者はペゾルドの力を借りて、この論文を初めて読み通しました。筆者の能力ですいすい理解できるような論文ではないものの、チューリングの創造性に何度も驚嘆しました。

　論文の冒頭でチューリングは「計算可能数」というものを定義しています。計算可能な数とは何でしょうか。どこまでも高い精度で求めることができる数のことでしょうか。そうではありません。チューリングは、「小数表現が有限の手段で計算できる」数を計算可能数と呼んでいます。

　この定義からしてすでに、深く本質的なのです。そのわけは後でわかります。計算可能数とそうでないものとの区別から、後に驚くべき結論が導かれるのです。ここでチューリングがいう「有限の手段」とは、「有限の情報に基づいた方法」という意味です。例えば円周率πは無限小数で表現されますが、円周率πを計算する数式は有限の情報で表現できるので、定義上計算可能数です。計算の手順そのものは無限に続いて構いません。一方、純粋な乱数は無限の桁の情報を与えないと表現できないので、計算可能数ではありません。

　続いてチューリングはある機械について述べます。その機械で小数表現を書き出せる数が、計算可能数です。その機械は後にチューリングマシンと呼ばれ、デジタルコンピュータの原型となるのですが、チューリングが考えていたのは便利な計算機のようなものではありません。チューリングが考えていたのは、本当は「計算する人」のことでした。チューリングは人間の計算する能力を機械に還元し、それが何であるかを明らかにしようと試みたようなのです。いってみれば人間機械論です。

　チューリングは例として数列010101…を計算する機械を組み立てて見せて、機械を四つの列からなる表で表す方法を示します（ここでいう「計算する」とはテープに印字するという意味です）。その四つとはおおまかにいうと、

（1）もとの機械の状態、
（2）読み込むマス目の記号、
（3）左右のマス目への移動とそこに印字する記号、
（4）移動後の機械の状態、

です。チューリングマシンは無限に長いテープのマス目を1マス読み、左右に1マス移動し、印字し、状態を変えることしかしません。テープのマス目にアドレスという概念はありません。

　少しだけ、チューリングの論文に立ち入って説明したいと思います。チューリングは計算機械を記述する表の表現方法を少しずつ変形してゆきます。まず、表の1行をA、C、D、L、R、N、；という7種類の記号の組み合わせに置き換えます。セミコロン（；）は表の各行を区切る記号として使います。そして7種類の記号を今度は1、2、3、4、5、6、7という数字に置き換えます。表の各行を横に並べると一つの整数ができます。この整数を機械の記述数と呼びます。

　表の各行の順番に意味はないので、一つの計算機械の記述数は複数個あります。しかし、どの計算機械も記述数を持ち、一つの記述数にはただ一つの機械が対応します。すると何がいえるでしょうか？　整数の全体は可算集合なので、計算可能数の全体も可算無限個しかないということが導かれます。可算集合というのは、集合の要素すべてに1番目、2番目、3番目というふうに番号を付けて数え上げることができる集合のことです。ペゾルドは次のように述べています。

「数学の式を一意な数に変換するという、ゲーデルが不完全性定理の証明に使った手法に、チューリングが影響を受けているのは明らかである」

　ゲーデルが論理学の命題を素数の積で表現したように、チューリングはあらゆる計算機械に整数を対応させました。筆者はどちらも天才のひらめきだと思います。