チューリングマシンとは何ですか? -マソリティ

有名なチューリングマシンは、アルゴリズムを使用して数学的演算を解決する性質を備えた、堅牢で自己完結型の数学的構造に基づいています。この定義は非常に複雑ですが、実際はそうではありません。

簡単に言うと、この機械は1936年に製造された、コンピューターのデータを無限に計算する装置です。疑いもなく、その開発はコンピューティングの歴史において重要な出来事を記録します。実際、私たちが今日存在しているコンピューターはこのマシンのおかげだと考えることができます。

簡単に言えば、チューリングマシンは複雑ではありません。それどころか、その最も重要な特性の 1 つはまさにその簡単なパフォーマンスです。さまざまなプロセスに従うテープ上の記号表現を使用するだけです。ただし、シンプルだからといって役に立たないわけではありません。それはまったく逆です。

チューリングマシンは、さまざまなコンピューターからのあらゆる種類のアルゴリズムコードを受け入れます。この意味で、コンピュータの動作ロジックをシームレスにシミュレートします。

この機械の名前は、イギリス出身の発明者アラン・チューリングに由来します。この人物は、生涯を通じてさまざまな分野で際立っていました。彼は主に論理的な天才として優れていました。実際、上記のことから、このマシンは当初「論理計算機」と呼ばれていました。

チューリングマシンは、コンピューティングの歴史において最も重要な貢献の 1 つです。

チューリングマシン誕生の歴史

19 世紀までに、数学は多くの分野で関連性を獲得しました。しかし、これはまだ正式には発表されていませんでした。この分野の専門家のほとんどは、この研究分野を確立するために懸命に努力してきました。

それは、マシンが実現を担当するシンボルとメソッドのグループに関する仮説を実装するという問題でした。

アラン・チューリングは1936 年にチューリングマシンの取り組みを発表しました。これはまさに彼の研究「Entscheidungsproblem への応用による計算可能な数について」のプレゼンテーションで起こりました。同年の出版物は、数学の決定可能性に対するデイヴィッド・ヒルベルトのアプローチを分析した。

言い換えれば、このアプローチは、あらゆる数学的答えに適用できる一定の手順の存在を確認し、それによってその結果が真であるかどうかを確認するというものでした。上記に基づいて、アランチューリングはチューリングマシンを設計し、一部のマシンがさまざまなアルゴリズムを解決できることを確認しました。

これまでチューリングは重要な遺産を残しました。彼の作品は物理的な表現に重点を置いているわけではありませんが、現代のコンピューター設計との関連性は否定できません。これらすべてに対して、コンピューターの動作を観察すると、チューリングマシンに直面することになります。

チューリングマシンはどのように作られるのでしょうか？

チューリングマシンには、ストレージデバイスとして機能する管理セクションに分割された無制限の数のテープがあります。さらに、テープのコードを読み書きするヘッドも備えています。一方、この同じ部分は、テープをあるスペースから別のスペースに移動する役割を果たします。

ヘルスチェック記録や縮小プロセステーブルも含まれます。後者はアクションテーブルとも呼ばれます。前に述べたように、チューリングマシンは自動的に動作します。したがって、さまざまな種類のアルゴリズムを解読するには、チョムスキー階層によって管理されます。

リボン: このリボンはセクションに分かれており、各セクションは他のセクションに従って配置されます。すべてのセルには、限定されたプライマーのシンボルがあります。プライマーには「B」と呼ばれる特定の記号が付いています。さらに、その他の追加のシンボルも含まれます。テープは、作業に必要なだけどちらの方向 (左または右) にも伸びます。
ヘッド– チューリングマシンのこの部分は、テープ上のコードを読み取り、生成します。さらに、テープを対応する方向に移動させる役割も果たします。ヘッドモデルによっては動く場合があります。そうであれば、バンドは固定されています。
ステータスの保存– 名前が示すように、アプライアンスのステータスを保存する必要があります。これは制限された状態を指します。さらに、レジスタが動作を開始する特定の初期状態があります。アラン・チューリングは、個人が特定の数学的演算を実行すると、それぞれの状態が「精神状態」に置き換わると述べています。
命令テーブル– 基本的に、すべてのチューリングマシンプロンプトを処理します。つまり、デバイスが特定の時間に何を実行すべきかを示します。たとえば、頭を移動したり、記号を書き込んだり、削除したりできます。

チューリングマシンはどのように動作するのでしょうか?

ヘッドがテープ上に配置されると、チューリングマシンは3 つの重要なタスクを実行します。このデバイスは、特定のセルにあるシンボルを読み取り、セルにあるシンボルの値を変更するか、ストリップを右または左に移動して、隣接するセルを解読して置き換えます。

さらに、各値には関連するタスクを含めることができます。つまり、たとえば、読み取られたシンボルが数字の 1 に対応する場合、チューリングマシンは 0 を書き込み、ストリップを右に移動します。ただし、読み取られたシンボルが 0 の場合、マシンは数値 1 を書き込みます。

チューリングマシンによって実行されるこのタスクは、反転と呼ばれます。この場合、バイナリ値が関係します。したがって、チューリングマシンは、非常に複雑なアルゴリズムを解読する特定のタスクを実行するようにプログラムされています。この装置の中心的な目的は、数学的演算によって計算される数値です。

チューリングマシンは何に使われますか?

実際、チューリングマシンはその歴史を通じて無数の用途に使用されてきました。そして、重要なことは、これは私たちの数学の見方や解釈の仕方を変えた革命的な発明であるということです。以前は、たとえば、言語ジェネレーターとして使用されていました。

ただし、現時点で議論できるアプリケーションは数多くあります。最も重要なものは次のとおりです。

計算理論– この理論は、コンピューターサイエンスと数学の研究の一部です。その主な目的は、コンピュータの本質的な性質と限界を分析することです。特に、この理論は、複雑さのレベルに応じて演算を計算および分類する可能性を認める数学的手順を見つけようとします。
Oracle Machine : これは、特定の数値記号に関連する質問に答えるオラクルを備えたチューリングマシンの一種です。

どのようなタイプのチューリングマシンが存在しますか?

チューリングマシンにはいくつかの種類があります。それらはそれぞれ、アルゴリズムの問題の実現を簡素化することを目的として生まれました。 5 つのタイプについては以下で説明します。

ステイディレクティブ付きチューリングマシン– このマシンには一方向に移動する無制限の帯域があります。通常、バンドは右に移動します。左側への移動は無効になります。
双方向チューリングマシン– チューリングマシンに無制限の数のテープがある場合、トラックが 2 つであることを除き、双方向マシンのように動作できます。この場合、情報はバンドのレイアウトに基づいて配置されます (該当する場合)。
マルチテープチューリングマシン– 名前が示すように、複数のテープがあります。その特徴は、それぞれに独自の頭があることです。したがって、これらの各部分は独立して動作します。一方、それらが同じ方向に、または同時に移動する必要はありません。
多次元チューリングマシン: この場合、マシンストリップには複数の次元があります。つまり、上下左右に移動する 2 次元のバンドです。マシンの状態と復号化するアルゴリズムに応じて、状態が変更されます。
非決定性チューリングマシン: 非決定性マシンを使用して決定性マシンをシミュレートすることは可能であり、その逆も同様です。決定論的な場合は、ストリップシンボルと現在の状態について、選択できる限られた数の数値から構成されることに基づいています。

チューリングマシンの利点は何ですか?

他のマシンと比較した場合、このタイプのマシンの最も重要な利点の 1 つは、その言語が非常に広範であることです。一方で、アルゴリズムを完全に再読することなく、アルゴリズムを承認または拒否することができます。チューリングマシンを扱う場合、とにかく演算が計算されます。さらに、そのエンコーディングは決定可能です。

これらのマシンは言語をリストまたは列挙します。一方で、彼らの自主性は他の追随を許しません。後者では、異なる状態間をジャンプできます。メモリが十分に大きいため、論理式を要約する必要はありません。