「これまで作られなかった最も重要な機械」アラン・チューリングとチューリングマシン

コンピューティングは、私たちのほとんどが直感的に理解できる馴染みのある概念です。関数 f (x) = x + 3 を例に考えてみましょう。x が 3 のとき、 f (3) = 3 + 3 となります。答えは6です。とても簡単です。明らかに、この関数は計算可能です。しかし、一部の関数はそれほど単純ではなく、計算可能かどうかを判断するのは簡単ではありません。つまり、最終的な答えが得られない可能性があります。

1928 年、ドイツの数学者デイヴィッド・ヒルベルトとヴィルヘルム・アッカーマンは、「決定問題」と呼ばれる問題を提起しました。時が経つにつれ、彼らが投げかけた疑問は計算可能性の正式な定義につながり、数学者は多くの新しい疑問に答えられるようになり、理論計算機科学の基礎が築かれました。

この定義は、アラン・チューリングという名の当時 23 歳の大学院生によって提案されました。彼は 1936 年に画期的な論文を書き、コンピューティングの概念を形式化しただけでなく、数学の基本的な問題を証明し、電子コンピューターの発明の知的基礎を築きました。チューリングの偉大なビジョンは、抽象マシンの形で計算問題に対する具体的な答えを提供することであり、博士課程の指導教官であるアロンゾ・チャーチは後にそれをチューリングマシンと名付けました。

チューリング マシンは、実体のあるデバイスとして物理的に存在しない (存在できない) ため、抽象化されています。むしろ、これは計算の概念モデルです。つまり、このマシンが関数を計算できる場合、その関数は計算可能であるということです。

アラン・チューリングは 1936 年にチューリング マシンを発明し、現代のコンピューティングを生み出しました。

アラン・チューリングとチューリングマシン

仕組みは次のようになります。チューリング マシンは、ルール テーブルに従って、無限に長いテープ上の記号を読み取り、変更できます。テープは「セル」で構成されており、各セルには 1 つのシンボルのみを保存できます。チューリング マシンはテープ ヘッドを使用してセルの内容を読み取ったり書き換えたりします。ルール テーブル内の各ルールは、チューリング マシンの現在の状態と読み取っているシンボルに基づいて、チューリング マシンが実行すべき動作を決定します。チューリング マシンは、停止した場所に基づいて最終状態 (「受け入れ状態」または「拒否状態」) に移行することで、入力を受け入れるか拒否するかを決定できます。あるいは、チューリング マシンが無限ループに陥り、テープ読み取りが止まらなくなることもあります。

チューリングマシンを理解する最も良い方法は、簡単な例について考えることです。与えられた入力が数字のゼロであるかどうかを判定するようにチューリング マシンが設計されていると想像してみましょう。スペース記号 (#) を付けて番号 0001 を入力します。これは、「#0001#」がテープ内の関連部分であることを意味します。

チューリング マシンは初期状態 (q0 と呼ぶ) から開始し、テープの左端のセルを読み取り、空きスペースを見つけます。ルールによれば、状態 q0 のときに、シンボルが # の場合はそのままにして、1 セル右に移動し、マシン状態を q1 に変更します。このステップの後、マ​​シンは状態 q1 になり、ヘッドは 2 番目のシンボル 0 を読み取ります。

ここで、これらの条件に適用されるルールを探します。 「状態 q1 のまま、ヘッドを 1 セル右に移動する」というルールが見つかりました。これにより、同じ位置 (状態 q1、読み取りはまだ 0) になるので、ヘッドが最終的に別の数字 1 を読み取るまで右に移動し続けます。

ルール テーブルを再度調べると、新しいルールが見つかります。「1 に遭遇した場合は、拒否状態である q2 に遷移します。」チューリング マシンは実行を停止し、元の質問「0001 はゼロですか?」に対して「いいえ」と答えます。

逆に、入力が「#0000#」の場合、チューリング マシンはすべてのゼロの後に # を検出します。ルールの表を調べると、マシンが状態 q3、つまり「受け入れ」状態になることを意味するというルールが見つかります。これで、「'0000' はゼロですか?」という質問に対する機械の答えは「はい」になります。

アラン・チューリングは、コンピューティング、アルゴリズム、チューリング マシンの定義に貢献しました。

抽象機械で判断的な質問に答える

チューリングは抽象マシンを使用して、Entscheidungsproblem に答える計算モデルを構築しました。これは、数学的な公理のセットが与えられた場合、与えられたステートメントが真であるかどうかを常に判断できる機械的な手順 (つまり、今日ではアルゴリズムと呼ばれる一連の命令) が存在するかどうかを正式に尋ねる問題です。

特定のチェスの位置が実行可能かどうかを教えてくれるアルゴリズムを見つけたいとします。この場合、公理とは正当なチェスの動きを規定するルールです。段階的なプロセスの有限シーケンスに従うことでそこに到達できるでしょうか?チェスの位置によっては、分析に私たちの一生よりも長い時間がかかる場合もありますが、チェスのゲームには、すべての可能な位置を生成し、それらを入力と 1 つずつ比較できるアルゴリズムが存在します。したがって、チェスは「決定可能」であると言えます。

しかし、1936 年にアメリカの数学者チャーチとチューリングはそれぞれ異なる方法を使用して、「決定問題のあらゆる例を解くための一般的な方法は存在しない」ことを別々に証明しました。たとえば、ジョン・コンウェイのライフ ゲームなどの一部のゲームは決定不可能です。つまり、特定のパターンが初期パターンから出現するかどうかを決定できるアルゴリズムは存在しません。

チューリングは、目的のタスクを実行できるアルゴリズムが存在する場合、関数は計算可能であることを示しました。同時に、アルゴリズムはチューリングマシンを使用して定義できるプロセスであることも示しました。したがって、計算可能関数とは、チューリング マシンによって計算できる関数です。これは計算可能性を定義する回りくどい方法のように思えるかもしれませんが、これが最善の方法です。

「他の方法で定義できるわけではない」とMITの理論計算機科学者マイケル・シプサーは言う。「チャーチ＝チューリングのテーゼは、アルゴリズムの非公式な概念は、あらゆる合理的な計算モデルで実行できるものである、というのが広く受け入れられていると思います」。他の数学者も、表面的には異なるものの、実際には同じである計算モデルを提案している。つまり、チューリングマシンで実行できるあらゆる計算を実行でき、その逆も成り立つのだ。

哲学者、論理学者、数学者のクルト・ゲーデルが数学が不完全であることを証明してからわずか数年後、チャーチとチューリングもこの研究で、数学の特定の問題は決定不可能であることを示しました。アルゴリズムがどれだけ洗練されていても、答えが「はい」か「いいえ」かはわかりません。どちらの出来事も、数学が単純で理想的な答えを提供してくれることを期待していたヒルベルトにとって壊滅的な打撃となった。しかし、それは悪いことではありません。もし、Entscheidungsproblem に一般的な解決策があれば、数学のすべての問題が単純な機械計算に還元されることになります。

普遍的かつ確率的なチューリングマシン

チューリング マシンは、これらの基本的な質問に答えるだけでなく、ユニバーサル チューリング マシンと呼ばれる変種を通じて現代のコンピューターの開発にも直接影響を与えました。これは、他のチューリング マシンへの任意の入力をシミュレートできる特殊な種類のチューリング マシンです。今日のコンピュータがあらゆるプログラムを読み取って実行できるのと同じように、このマシンは他のチューリング マシンの説明 (およびルールと入力テープ) を読み取り、その動作を自身の入力テープ上でシミュレートして、シミュレートされたマシンと同じ出力を生成することができました。

1945 年、ハンガリー系アメリカ人の数学者、コンピュータ科学者、物理学者であるジョン・フォン・ノイマンは、汎用チューリング マシンの概念を実際のマシンに変換できるコンピュータ アーキテクチャ、フォン・ノイマン アーキテクチャを提案しました。

プリンストン大学の理論計算機科学者サンジーヴ・アローラ氏は、この概念を教える際、より広い哲学的観点を強調する。彼はこう言いました。「ユニバーサルには 2 つの概念があります。1 つは、他のチューリング マシンを実行できるということです。しかし、もう 1 つのより大きな概念は、宇宙で思いつくあらゆる計算を実行できるということです。」古典物理学の世界では、あらゆる物理プロセスはアルゴリズムを使用してモデル化またはシミュレートでき、そのアルゴリズムはチューリング マシンによってシミュレートできます。

もう一つの興味深く、ますます有用になっている変種は、確率的チューリング マシンです。すべての入力に対して明確に定義された応答を持つ通常のチューリング マシンとは異なり、確率的チューリング マシンは確率に基づいて複数の応答を持つことができます。つまり、異なる時点で同じ入力に対して異なる結果が生成される可能性があるということです。また驚くべきことに、いくつかの問題では、この確率的戦略は純粋に決定論的な方法よりも効果的です。確率的チューリングマシンの概念は、最適化や機械学習などの分野で非常に有用であることが証明されています。

これらの抽象マシンは、根本的な疑問を投げかけることが科学者ができる最も有益なことの一つであることを示す、これまでで最も優れた証拠であると言えるでしょう。