決して造られなかった最も重要な機械

計算は、私たちのほとんどが直感的に理解しているよく知られた概念です。 関数を取る f(x）= x + 3. いつ x XNUMXつです、 f(3) = 3 + 3。XNUMX。 簡単。 この関数が計算可能であることは明らかです。 しかし、一部の関数はそれほど単純ではなく、それらが計算できるかどうかを判断するのはそれほど簡単ではありません。つまり、最終的な答えが得られない可能性があります。

1928 年、ドイツの数学者デイヴィッド ヒルベルトとヴィルヘルム アッカーマンは、 設計上の問題 （「決定問題」）。 やがて、彼らの疑問は計算可能性の正式な定義につながり、数学者は多くの新しい問題に答え、理論的コンピューター サイエンスの基礎を築くことができるようになりました。

この定義は、23 年に次のように書いたアラン チューリングという 1936 歳の大学院生によるものです。 独創的な論文 それは計算の概念を形式化しただけでなく、数学における根本的な疑問を証明し、電子コンピューター発明の知的基盤を生み出しました。 チューリングの優れた洞察力は、抽象マシンの形で計算の問題に対する具体的な答えを提供したことであり、後に彼の博士顧問であるアロンゾ チャーチによってチューリング マシンと名付けられました。 これは、有形のデバイスとして物理的に存在しない（存在できない）ため、抽象的です。 代わりに、これは計算の概念モデルです。マシンが関数を計算できる場合、その関数は計算可能です。

仕組みは次のとおりです。 チューリング マシンは、規則表の指示に従って、無限に長いテープ上のシンボルを読み取り、変更できます。 テープは「セル」で構成されており、各セルには XNUMX つのシンボルを正確に保存でき、マシンはテープ ヘッドでセルの内容を読み取り、書き換えます。 テーブル内の各ルールは、現在の状態と読み取っているシンボルの両方に基づいてマシンが何をすべきかを決定します。 マシンは最終状態 (「受け入れ状態」または「拒否状態」) に入り、入力を受け入れたり拒否したりして停止します。 または、無限ループに陥り、テープを永遠に読み続けます。

チューリング マシンを理解する最良の方法は、簡単な例を考えることです。 与えられた入力が数値のゼロかどうかを知らせるように設計されたものを想像してみましょう。 空白記号 (#) を伴う入力番号 0001 を使用するので、「#0001#」がテープの関連部分になります。

マシンは初期状態 (q0 と呼ぶ) で起動します。 テープの左端のセルを読み取り、空白スペースを見つけます。 ルールは、「状態 q0 のとき、記号が # の場合はそのままにし、右に 1 セル移動して、マシンの状態を q1 に変更する」というものです。 このステップの後、マ​​シンは状態 q0 になり、そのヘッドは XNUMX 番目のシンボル XNUMX を読み取ります。

次に、これらの条件に適用されるルールを探します。 「状態 q1 に留まり、先頭を 1 セル右に移動する」というものを見つけます。 これにより、同じ位置 (状態 q0 で「1」を読み取る) が残るため、ヘッドが最終的に別の数値 XNUMX を読み取るまで右に移動し続けます。

もう一度テーブルを参照すると、「1 に遭遇した場合は、『拒否』状態である q2 に移行する」という新しいルールが見つかります。 マシンは停止し、最初の質問「'0001' はゼロですか?」に対して「いいえ」と答えます。

入力が「#0000#」の場合、マシンはすべてのゼロの後に # を検出します。 テーブルを参照すると、これはマシンが状態 q3 (「受け入れ」状態) に入ることを意味するというルールが見つかります。 ここで、マシンは「'0000' はゼロですか?」という質問に「はい」と答えます。

チューリングは抽象機械を使って、Entscheidungsproblem に答えるための計算モデルを確立しました。この問題は、形式的には次のような問いかけをします。一連の数学公理が与えられた場合、常に実行できる機械的プロセス (今日ではアルゴリズムと呼ばれる一連の命令) は存在するかというものです。与えられたステートメントが真実かどうかを判断しますか?

チェスの特定の局面が可能かどうかを教えてくれるアルゴリズムを見つけたいとします。 ここで、公理とは、合法的な手を管理するチェスのルールです。 その位置に到達するために、有限の段階的な手順に従うことができるでしょうか? 一部の局面の分析には私たちの生涯よりも長い時間がかかる場合がありますが、アルゴリズムはすべての可能な局面を生成し、それぞれを入力と比較する可能性がありますが、チェスのゲームにはそのようなアルゴリズムが存在します。 その結果、チェスは「決定可能」であると言われます。

しかし、1936 年に、チャーチとチューリングは、異なる方法を使用して、Entscheidungs 問題のすべての事例を解決する一般的な方法はないことを個別に証明しました。 たとえば、ジョン コンウェイのライフ ゲームなど、一部のゲームは決定不可能です。どのアルゴリズムも、初期パターンから特定のパターンが現れるかどうかを決定できません。

チューリングは、目的のタスクを実行できるアルゴリズムが存在する場合、関数は計算可能であることを示しました。 同時に、彼はアルゴリズムがチューリングマシンによって定義できるプロセスであることを示しました。 したがって、計算可能な関数とは、チューリング マシンを使用して計算できる関数のことです。 これは計算可能性を定義する回りくどい方法のように思えるかもしれませんが、これが私たちが知ることができる最善の方法です。 「それを別の方法で定義するという選択肢があるわけではありません」と彼は言った マイケル・シプサー、マサチューセッツ工科大学の理論コンピューター科学者。 「チャーチ＝チューリングの論文では、アルゴリズムの非公式な概念は、あらゆる『合理的な』計算モデルが実行できることに対応していると述べていることが一般的に受け入れられていると思います。」 他の数学者は、表面的にはまったく異なって見えるが、実際には同等のさまざまな計算モデルを考案しました。彼らは、チューリング マシンが実行できるあらゆる計算を実行でき、その逆も同様です。

クルト・ゲーデルが数学が 不完全, チャーチとチューリングはこの研究で、数学における一部の問題は決定不可能であることを示しました。アルゴリズムがどれほど洗練されていても、答えがイエスかノーかを教えてくれるわけではありません。 どちらも、数学がきちんとした理想的な答えを持っていることを望んでいたヒルベルトにとって、壊滅的な打撃でした。 しかし、それはおそらく同じくらい良いでしょう。もし Entscheidungsproblem に対する一般的な解決策が存在するなら、それは数学におけるすべての問題が単純な機械的計算に還元されることを意味するでしょう。

チューリング マシンは、これらの基本的な質問に答えるだけでなく、万能チューリング マシンとして知られる改良型を通じて、現代のコンピューターの開発にも直接つながりました。 これは、任意の入力で他のチューリング マシンをシミュレートできる特別な種類のチューリング マシンです。 他のチューリング マシンの記述 (ルールと入力テープ) を読み取り、その動作を独自の入力テープでシミュレートし、シミュレートされたマシンが生成するのと同じ出力を生成します。これは、今日のコンピューターが任意のプログラムを読み取って実行できるのと同じです。 1945 年、ジョン フォン ノイマンは、現実のマシンで普遍的なチューリング マシンの概念を可能にした、フォン ノイマン アーキテクチャと呼ばれるコンピュータ アーキテクチャを提案しました。

日時 Sanjeevアローラプリンストン大学の理論コンピューター科学者である彼は、この概念を教えており、より広範な哲学的全体像を強調しています。 「『ユニバーサル』にはXNUMXつの概念があります」と彼は言う。 「ユニバーサルの概念の XNUMX つは、他のチューリング マシンを実行できるということです。 しかし、「ユニバーサル」のもう XNUMX つのより大きな概念は、宇宙で思いつくあらゆる計算を実行できるということです。」 古典物理学の世界では、アルゴリズムを使用してあらゆる物理プロセスをモデル化またはシミュレートでき、さらにそのアルゴリズムをチューリング マシンでシミュレートできます。

もう XNUMX つの注目すべき、ますます便利になっている変種は、確率的チューリング マシンです。 すべての入力に対して明確に定義された反応を持つ通常のチューリング マシンとは異なり、確率チューリング マシンは確率に基づいて複数の反応を持つことができます。 これは、同じ入力に対して異なる時点で異なる結果が得られる可能性があることを意味します。 驚くべきことに、このような 確率的戦略 特定の問題については、純粋に決定論的なアプローチよりも効率的です。 確率論的チューリング マシンからのアイデアは、暗号化、最適化、機械学習などの分野で実際に役立つことが示されています。

これらの抽象的な機械は、おそらく、基本的な質問をすることが科学者ができる最も有用なことのXNUMXつであることを示す最良の証拠です.