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

究極の機械

135

5

章

究極の機械

３章と４章では、単純な計算モデルの能力について調べました。複雑さをほとんど取り除いた基本

的な機械を使って、複雑な文字列を認識する方法、正規表現にマッチさせる方法、プログラミング言

語をパースする方法について見てきました。

一方、有限オートマトンやプッシュダウン・オートマトンといった機械には、実用的な計算モデルと

しての有用性を損なう、大きな制限があることも見ました。こうした制限を取り除き、普通のコン

ピュータで可能なことを全部できるようにするためには、このおもちゃレベルのシステムにどれだけの

能力が必要になるのでしょうか。RAMやハードディスク、適切な出力の仕組みといった振る舞いをモ

デル化するには、どれくらいの複雑さが必要になるのでしょうか。常にハードコードされた1つのタス

クを実行するのではなく、実際にプログラムを実行できる機械を設計するためには、何が必要なので

しょうか。

1930年代に、アラン・チュ

ーリング（Alan Turing）はこの本質的な問題に取り組みました。その当

時、「コンピュータ」という言葉は「計算する人」（通常は女性）を意味していました。彼女の仕事は、

一連の骨の折れる演算を手作業で繰り返すことにより、長々とした計算を実行することでした。チュー

リングは人間による「コンピュータ」の操作を理解し、その特性を明らかにする方法を追い求めまし

た。その結果、彼は同じタスクを完全に機械で実行可能にしたのです。この章では、チューリングの

革命的なアイデア、手作業に ...