「決して作られなかった最も重要なマシン」アラン・チューリングとチューリング・マシン

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

1928 年、ドイツの数学者デイビッド ヒルベルトとヴィルヘルム アッカーマンは、Entscheidungsproblem (つまり、「決定論的問題」。質問) と呼ばれる方法を提案しました。時間が経つにつれて、彼らが尋ねた質問は計算可能性の正式な定義につながり、その定義により数学者は多くの新しい質問に答え、理論的なコンピューターサイエンスの基礎を築くことができます。

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

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

##アラン・チューリングが 1936 年にチューリング マシンを発明したとき、現代のコンピューティングも作成されました。 アラン チューリングと彼のチューリング マシン

その動作原理は次のとおりです: チューリング マシンはルール テーブルのルールに従うことができます。読み取りと変更が可能です。無限に長いテープ上のシンボル。テープは「セル」で構成されており、各セルには 1 つのシンボルのみを格納できます。チューリング マシンはテープ ヘッドを使用してセルの内容を読み取り、書き換えます。ルール テーブル内の各ルールは、現在の状態と読み取っているシンボルに基づいてチューリング マシンが何をすべきかを決定します。チューリング マシンは、停止した場所に基づいて最終状態 (「受け入れ状態」または「拒否状態」) に入り、入力を受け入れるか拒否するかを決定します。あるいは、チューリング マシンが無限ループにはまり、テープの読み取りを停止しません。

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

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

次に、これらの条件に適用されるルールを探します。 「状態 q1 を維持し、先頭を 1 セル右に移動する」というルールが見つかりました。これにより、同じ位置が保たれるため (状態 q1 では読み取り値は 0 のままです)、先頭まで右に移動し続けます。最後に別の数値 1 が読み取られます。

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

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

#

アラン チューリングは、計算、アルゴリズム、チューリング マシンの定義に貢献しました。

抽象マシンによる判断的質問への回答

チューリングは抽象マシンを使用して、エンシャイドゥングスの質問に答えるための計算モデルを構築しました。質問: 一連の数学的公理が与えられた場合、与えられたステートメントが真であるかどうかを常に判断できる機械的なプロセス (つまり、一連の命令、今日ではアルゴリズムと呼ばれます) は存在しますか?

特定のチェスのゲームにおける駒の位置が実現可能かどうかを知らせるアルゴリズムを見つけたいとします。この中で、公理はチェスの合理的な手を管理する規則です。段階的なプロセスの有限な順序に従ってそこに到達できるでしょうか?チェスの局面によっては分析に私たちの生涯よりも長い時間がかかる場合がありますが、アルゴリズムはすべての可能な局面を生成し、それらを 1 つずつ入力と比較する可能性があり、そのようなアルゴリズムはチェスのゲームに存在します。したがって、チェスは「決定可能」であると言います。

しかし、1936 年に、アメリカの数学者チャーチとチューリングは、「エントシャイドゥングス問題のすべてのインスタンスを解決できる一般的な方法はない」ことを証明するために、異なる方法を使用しました。 , ジョン コンウェイのライフ ゲームなど、一部のゲームは決定不可能です。初期パターンから特定のパターンが現れるかどうかをアルゴリズムで判断することはできません。

チューリングは、必要なタスクを実行できるアルゴリズムがあれば、関数が計算可能であることを示しました。同時に、アルゴリズムがチューリングマシンで定義できるプロセスであることも示した。したがって、計算可能関数とは、チューリング マシンで計算できる関数のことです。これは計算可能性を定義する遠回りな方法のように思えますが、これが私たちが持っている最善の方法です。

「それを他の方法で定義することを選択できるというわけではありません」と、MIT の理論コンピューター科学者であるマイケル シプサー氏は述べています。論文では、アルゴリズムの非公式な概念は、合理的な計算モデルで実行できるあらゆるものであると提案しています。」 他の数学者は、表面的には非常に異なっているように見えても、実際には同じであるさまざまな計算モデルを提案しています。チューリングマシンでもできますし、その逆も同様です。

哲学者、論理学者、数学者のクルト・ゲーデルが数学が不完全であることを証明してからわずか数年後、チャーチとチューリングもこのワークシートに合格しました。これは、数学におけるいくつかの問題が決定不可能であることを示しています。アルゴリズムがどれほど複雑であっても、答えがイエスかノーかを判断することはできません。どちらの出来事も、数学が単純で理想的な答えを提供してくれることを期待していたヒルベルトにとって、壊滅的な打撃となった。しかし、それは悪いことではありません。Entscheidungsproblem に対する一般的な解決策があれば、数学のすべての問題が単純な機械的計算に還元されることを意味します。

汎用チューリング マシンと確率論的チューリング マシン

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

1945 年、ハンガリー系アメリカ人の数学者、コンピューター科学者、物理学者のジョン フォン ノイマンは、コンピューター アーキテクチャ、つまりフォン ノイマン アーキテクチャを提案しました。機械を現実の機械に変える。

プリンストン大学の理論コンピューター科学者サンジーブ・アローラは、この概念を教える際、より広い哲学的全体像を強調します。彼は、「ユニバーサルには 2 つの概念があります。1 つは、他のチューリング マシンを実行できるということですが、もう 1 つは、宇宙で思いつくあらゆる計算を実行できるということです。」と述べました。 、アルゴリズムを使用してあらゆる物理プロセスをモデル化またはシミュレートでき、アルゴリズムはチューリング マシンでシミュレートできます。

もう 1 つの注目すべき、ますます便利になっている亜種は、確率的チューリング マシンです。各入力に対して明確に定義された応答を持つ従来のチューリング マシンとは異なり、確率チューリング マシンは確率に基づいて複数の応答を作成できます。これは、同じ入力に対して異なる時点で異なる結果が生成される可能性があることを意味します。また、一部の問題では、この確率論的な戦略が純粋に決定論的なアプローチよりも効果的であることも驚くべきことです。確率的チューリング マシンの概念は、最適化や機械学習などの分野で非常に役立つことが証明されています。

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

以上が「決して作られなかった最も重要なマシン」アラン・チューリングとチューリング・マシンの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。