コンピュータの基礎講座�A　チューリング・マシン

　矛盾を含んだ論理体系では、正しくないことも証明可能となる。したがって、純粋に論理的思考から構築された数学はその内部に矛盾を含んでいてはならない。しかし、その極めて当たり前の前提が証明できずに、二十世紀前半の数学界は大揺れに揺れていた。“数学の危機”である。そしてそれは、衝撃的な結果をもって幕を閉じる。１９３１年、チェコスロバキアの若き数学者クルト・フリードリヒ・ゲーデル（１９０６〜１９７７）によって『無矛盾性が証明できないこと』が証明されたのである。『不完全性定理』と呼ばれるその定理は、世の中に完全な理論など存在し得ないことを示し、理性の限界を明確にするものとして、数学界のみならず一般社会にも大きな影響を与えた。今世紀最大の発見の一つである。

−　不完全性定理　−

第一定理『数学の定理の中には、それを証明することも否定することもできないものが存在する』

第二定理『数学が無矛盾である限り、数学は自分自身の無矛盾性を証明することはできない』

　わかりやすく言えば、矛盾が起きなければ、今いる世界が夢なのか現実なのか、私たち自身には判断できないということである。

矛盾のない世界では、本当に矛盾がないのか、それとも矛盾はあるのだけれど、ただ単にまだ見つかっていないだけなのか、その世界にいる人たちには認識できないのである。そしてもっとも重要なことは、この驚くべき事実が、哲学的思想などからではなく、極度に学問的で厳密な数学的証明から得られた結果だということである。

　それは今世紀に誕生したコンピュータ科学にも大きな影響を与えることとなった。当時ケンブリッチ大学の学生だったチューリングは、不完全性定理に刺激を受け、『理性とは何か？知性とは何か？』という問いを突き詰めていった。そして生まれたのがチューリング・マシンである。

　私たちは何かを計算する（または考える）時、頭で考えては黒板に途中結果を書き出し、それを使ってまた頭で計算し…ということをよく行う。チューリング・マシンの動作はそれとよく似ている。チューリング・マシンでは、ヘッドがテープからデータを読みとり、それに従ってある記号操作を行い、その結果をテープに書き込んでいく。その繰り返しを行う。チューリングは思考を細かな要素と手順に分解し、それをもっとも単純な形で表現したのである。チューリングはこの簡潔なモデルでありとあらゆる記号操作が可能であることを示し、衝撃を与えた。神秘の領域であった『思考』が初めて科学の言葉で語られたのである。

　チューリング・マシンによって解決できる問題はアルゴリズムのある問題といい、解決できない問題はアルゴリズムのない問題という。アルゴリズムとは、簡単に言えば、解を求めるための手順である。チューリングはチューリング・マシンを使ってアルゴリズムのない問題、つまり、肯定も否定もできない問題が存在することを示した。それは不完全性定理の別の表現でもあった。もちろん、アルゴリズムのない問題は、人間の頭脳をもってしても解決できない。

　人間の知的活動を代替する機械がコンピュータであるとすれば、チューリング・マシンはコンピュータの理論そのものである。人間の知的活動のうち、記号によって完全に記述できる部分は、チューリング・マシンによっても必ずシミュレート（模倣）できることが証明されている。現在のコンピュータが、基本的な構造は同じなのに、多種多様な用途をこなしているのはそのためである。現在あるコンピュータはすべてチューリング・マシンであり、将来現れるかもしれないコンピュータもすべてチューリング・マシンとみなすことができるのである。これほどまでに完成された理論が、本格的なコンピュータの出現する十年も前に誕生していたとは驚くべきことである。

　それではチューリング・マシンは知能となりうるのか？チューリング・マシンの出現により、人工知能の研究が隆盛する。しかし問題はそれほど単純ではなかった。チューリング・マシンが頭脳を完全にシミュレートできるかどうか、まだわかっていない。最近では否定的な見解が多いようである。人間には閃きとか感情、創造性といった能力が備わっている。それはどのような仕組みで働いているのか？チューリング・マシンはアルゴリズムさえ与えられれば思考を始める。与えているのは私たち人間である。では私たちは誰からアルゴリズムを与えられているのだろうか？わずか千五百グラム程度の脳だが、その世界はまだまだ深遠なようである。

　チューリング賞は現在、自然科学のノーベル賞、数学のフィールズ賞に匹敵するコンピュータ科学最高の栄誉となっている。ノーベル賞・フィールズ賞ともに日本から受賞者が出ているが、チューリング賞を受賞した日本人はまだいない。

[戻る]