新刊ピックアップ

チューリング機械からコンピュータの原理を学ぶ

この記事を読むのに必要な時間:およそ 2.5 分

現在のコンピュータ・サイエンスの源流をたどると,チューリング機械に行き当たります。チューリング機械から現在のコンピュータ・サイエンスの数多くの分野が生まれました。計算機の設計理論であるアーキテクチャー,自然言語解析,人工知能……などです。チューリングの創設した理論の概要をわかりやすく紹介します。

人工知能の誕生とアラン・チューリング

はじめてコンピュータの原理を考案したのは,イギリスの数学者アラン・チューリング(1912〜1954)でした。電卓さえもなかった時代にコンピュータの原型である⁠チューリング機械⁠は考案されたのです。

チューリングは,1936年の論文で仮想的な計算機を作り上げました。チューリングが考えた⁠チューリング機械⁠はとても単純な構造ながらも,誰も思いつかないような独創的な計算機モデルでした。この計算機モデルはコンピュータの仕組みの核となる原理をついており,それを深く知ることで現在のコンピュータの能力を理解することができます。さらに,コンピュータにはできないこと……つまり能力の限界をも知ることができるのです。

チューリング機械の驚嘆すべきところは,その極端なまでの単純さです。1本のテープと読み取りヘッドが1つあるだけです。そして出来ることは,ヘッドを右か左に1文字分移動することと,テープに文字を書き込むこと,そして文字を読み取ることのみです。これだけの機構で,アルゴリズムすべてが実現できるのです。

図1 チューリング機械の概念

図1 チューリング機械の概念

これほどまでに単純でほんの少しの操作しかできない機械でありながら,チューリング機械は現在のコンピュータが行う,どんな計算も模倣することができます。ここで注意していただきたいのは,この機械は機械と名はついていますが,⁠物理的な構造⁠はありません。ヘッドの素材は木だとか,テープの素材は紙だ,といった材料の概念は存在しません。どのように計算が行われるかを想定した,頭の中で作り上げた架空の装置です。

コンピュータは“不可能への挑戦”の副産物だった

チューリングがチューリング機械を考案した本来の目的は,⁠コンピュータを作るため⁠ではありませんでした。チューリングが計算機モデルの論文を発表したのは今から80年以上も前になりますが,その当時の多くの数学者に影響を与え,20世紀の数学研究の方向を示した数学者にダフィット・ヒルベルト(1862年〜1943年)という人物がいます。

ヒルベルトは数学というシステムを整えるべく「その数学が絶対に間違わないということを数学的に証明しよう」という運動を始めました。数学を厳密に公理化しようとするプログラムで,ヒルベルト・プログラムとして知られています。ヒルベルト・プログラムの究極の目的は,次のことを行なうことでした。

数学の命題を論理式として表す。その論理式が正しいかどうか,言い換えると,その論理式が定理かどうかを,数学的に論証するアルゴリズムを開発すること。

この問題を「決定問題」といいます。チューリングはこの問題を解くためにチューリング機械を発明したのです。

1900年8月,ヒルベルトはパリで開催された国際数学者会議で,20世紀の数学者に向けて23題の未解決問題を提示しました。その中の第10問題は「ディオファントス方程式を解くアルゴリズムを見つけよ」というものでした。23題の未解決問題は次々に解かれていきましたが,第10問題は長きにわたり未解決のままで,多くの数学者が第10問題に魅了されその問題の解決に取り組みました。そしてついに提示から70年後にロシアの数学者ユーリ・マチャセビッチによって「ディオファントス方程式を解くアルゴリズムはない(計算不能だ⁠⁠」という否定的な結論が出されました。その結論が導き出されたのは,紛れもなくチューリング機械とチューリングが定義した『計算不能』という概念があったからです。ディオファントス方程式は古代ギリシア時代からある有名な整数係数の方程式で,その問題にアルゴリズムがないなどとは誰も信じられない結果でした。

チューリングがチューリング機械で示したのは,⁠ヒルベルト・プログラムの決定問題を解くアルゴリズムは存在しない」ということでした。この結論はヒルベルト・プログラムを破綻に導いたとか機械の蹉跌とよく言われていますが,果たしてそうでしょうか。チューリング機械や『計算不能』という概念が,第10問題の解決に繋がっていったように,コンピュータ・サイエンスは衰えるどころか現在のコンピュータの原理を生み出し,コンピュータ・サイエンスの発展に繋がっていきました。自身の業績がもとになり,現代のようなコンピュータの世界になっていくとは,チューリング自身も想像していなかったでしょう。

プログラム内蔵方式

当時の機械は,ある特定の目的のために作られており,異なるプログラムで動く機械は異なる機械としてそのつど構成していました。チューリングはこの意味で,何種類ものチューリング機械を考案しています。中でも特に素晴らしく画期的で優れた機械は,万能チューリング機械だと言えるでしょう。万能チューリング機械の素晴らしさはその汎用性にあります。万能チューリング機械1つあれば,全ての目的を実行することができるのです。

万能チューリング機械はプログラム「P」を入力データ「x」と共に受け取ります。プログラム「P」を入力値と一緒に受け取ることで,異なるプログラムを実行する時に新しく機械を構成する必要がなくなります。この万能チューリング機械は,現在ではプログラム内蔵方式と呼ばれ,実際のコンピュータの誕生の大きな礎となりました。

コンピュータ学界の大御所であり実際のコンピュータの開発を数多く手掛けた巨人にフォン・ノイマンという数学者がいます。彼は万能チューリング機械を高く評価しており,コンピュータの父と称えられたとき,⁠私はただの助産師にすぎない」と答えていたそうです。チューリング機械は,当時の数学界を牽引する人々に高く評価されていたのです。

さらに注目すべき点として,万能チューリング機械は現在のコンピュータと同等の能力を持っているといえます。等価性については明確な定義や議論が必要となりますが,ここでは万能チューリング機械は現在のコンピュータができる全ての計算をシミュレートできると考えてください。そして驚くべきことに,現在のコンピュータの能力だけでなく,未来に出てくるであろう全てのコンピュータの能力とも等価であるとされています。

この議論においてはコンピュータの処理速度やメモリ容量などは含みません。現在のコンピュータ開発においては外すことができない観点ではありますが,コンピュータの能力の本質を知るために,ここでは商業的な条件は削ぎ落とし,学術的・原理的な観点から考えています。

コンピュータにも計算できない問題がある

ヒルベルトの「決定問題」を解くためにチューリング機械は考案されましたが,チューリングが導き出した答えは『決定問題を解くアルゴリズムは存在しない』という否定的ともとれる結果でした。アルゴリズムがないということは,コンピュータで計算できないと言い換えることができます。これはコンピュータの能力の限界をも指し示すものであり,当時はとてもショッキングな結論でした。しかし,その結果は『アルゴリズムとはなにか』⁠計算とはなにか』という数学の基本原理の追及に繋がっていきました。

例えば,アルゴリズムをどのように表現するかという問題は,プログラミング言語の研究に発展していきます。また,チューリング機械をモデルとしてオートマトン理論と呼ばれる脳のモデルの研究へも繋がっていきます。不思議なことに数学というのは,あるいは科学一般に言えることかもしれませんが,⁠できない』という否定的な結果が,多くのものを生み出すきっかけになることが多いように思われます。

チューリングが論文を発表した1936年,アロンゾ・チャーチはすでにこの問題を解いていました。チャーチは「アルゴリズムとはなにか」という点で,チューリングとは違う考えを持っていましたが,⁠決定問題は計算できない」という同じ結論に達していました。当時のチューリングの指導教官の優れたところは,同じ結論を導き出したチューリングの論文の素晴らしさを認め,この論文をチャーチに紹介したところです。チャーチもすぐにこの論文の素晴らしさを認めています。これが「チャーチ=チューリングの定立」と呼ばれているものです。

チューリングは問う「機械は考えることができるだろうか?」

チューリングが行なったテストは次のようなものでした。⁠人間が機械に対して質問をします。機械から返事がかえってきます。対話相手がコンピュータであると判断できなければ,コンピュータには知性があるとします。」これはチューリングテストと呼ばれ,現在でも議論の対象となっています。チューリングは人工知能の概念も研究を進め「考えるとはなにか」⁠知性とはなにか」といった議論を展開していきました。

近年,ニュースや新聞などで人工知能という言葉をよく耳にします。ある一面において最先端の技術とも取られがちですが,それは今に始まったことではなく,チューリングの時代から研究されていました。実際,チューリングは1950年に「計算機と知能」という記事の中でこのチューリングテストについて言及しています。

チューリングは計算する機械を生みだし,脳はコンピュータかということにまで研究を広げていきました。コンピュータの世界は日進月歩ですが,未来に出てくるであろう,どんな機械よりも強力な計算機モデルは80年以上も前に誕生しました。人工知能の概念もまた,フォン・ノイマンやチューリングの時代からすでに研究されています。古い時代のコンピュータ・サイエンスの世界を読み解くことで,新しい見地が得られるかもしれません。

著者プロフィール

阿部彩芽(あべあやめ)

グラフィックデザイナー・イラストレーター・webデザイナー
大阪大学工学部を卒業後,同大学大学院に進学。創造社デザイン専門学校にて広告デザインを学ぶ。その後,東京の広告制作会社にてグラフィックデザイナーとして勤務。現在は独立し,フリーランスとして活動。