チューリング マシンや PDA について勉強しているときに、最初のコンピューティング デバイスはチューリング マシンだと思っていました。
そこで、チューリングマシンという実用的なマシンが存在し、その状態を特殊なデバイス (フリップフロップなど) で表すことができ、磁気テープを入力として受け入れることができると考えました。
したがって、入力文字列が磁気テープでどのように表現されるかを尋ねましたが、答えと私の本に記載されている詳細から、チューリングマシンはやや仮説的であることがわかりました。
私の質問は、チューリング マシンを実際にどのように実装するかということです。たとえば、現在のプロセッサでスペル ミスをチェックするためにどのように使用されているかなどです。
チューリングマシンは時代遅れですか？それともまだ使われていますか？
チューリングが、現在チューリング マシンと呼ばれるものを最初に考案したとき、彼は純粋に理論的な理由 (決定不能な問題の存在を証明するために使用された) であり、現実の世界で実際に構築したことはありませんでした。時を経て現在に至ると、趣味でチューリング マシンを構築する趣味を除いて、TM は本質的にセオリーランドに限定されています。
チューリング マシンは、いくつかの理由で実際には使用されていません。まず、無限のテープを構築するには無限のリソースが必要になるため、真の TM を構築することは不可能です。(ただし、限られた量のテープで TM を構築し、必要に応じてテープを追加することを想像することもできます。) さらに、チューリング マシンは、データ アクセスのシーケンシャルな性質のために、他の計算モデルよりも本質的に低速です。たとえば、チューリング マシンは、スキップする配列のすべての要素を最初に通過しない限り、配列の途中にジャンプすることはできません。その上、チューリング マシンの設計は非常に困難です。たとえば、32 ビット整数のリストをソートするチューリング マシンを作成してみてください。（実際、やめてください。本当に難しいです！）
これは疑問を投げかけます...なぜチューリングマシンを研究するのですか? 幸いなことに、これを行う理由は数多くあります。
計算できる可能性のある限界について推論するため。チューリング マシンは、地球上の任意のコンピューター (または、チャーチ チューリングのテーゼによれば、物理的に実現可能な任意のコンピューティング デバイス) をシミュレートできるため、チューリング マシンが計算できる限界を示すことができれば、その限界を示すことができます。実際のコンピュータ上で達成されることを期待することはできません。
アルゴリズムの定義を形式化すること。「答えを推測する」というステートメントはアルゴリズムではないのに、なぜバイナリ検索はアルゴリズムなのですか? この質問に答えるには、コンピューターとは何か、アルゴリズムが何を意味するかについての正式なモデルが必要です。チューリング マシンを計算のモデルとして使用することで、アルゴリズムとは何かを厳密に定義することができます。実際にアルゴリズムをフォーマットに変換したいと思う人は誰もいませんが、変換できることで、アルゴリズムと計算可能性理論の分野に確固たる数学的根拠が与えられます。
決定論的および非決定論的アルゴリズムの定義を形式化すること。おそらく現在、コンピューター サイエンスにおける最大の未解決の問題は、P = NP かどうかです。この質問は、P と NP の正式な定義がある場合にのみ意味があり、決定論的および nndeterministic 計算の場合は定義が必要です (ただし、技術的には 2 次ロジックを使用して定義できます)。チューリング マシンを使用すると、NP 完全問題を見つける方法が得られるだけでなく、NP の重要な問題について話すことができます。たとえば、SAT が NP 完全であることの証明は、SAT を使用してチューリング マシンをエンコードできるという事実と、それが入力で実行されるという事実を使用します。
お役に立てれば！
これは、実現不可能な概念的なデバイスです (無限のテープが必要なため)。チューリング マシンの物理的な実現を構築した人もいますが、物理的な制限により、真のチューリング マシンではありません。
ここにそのビデオがあります: http://www.youtube.com/watch?v=E3keLeMwfHY
チューリング マシンは正確には物理的なマシンではなく、基本的に概念的なマシンです。Turing の概念は仮説であり、小さくて簡単なソリューションにも無限のテープが必要になるため、これを現実の世界で実装するのは非常に困難です。
これは理論上のマシンです。ウィキペディアの次の段落
チューリング マシンは、規則の表に従ってテープのストリップ上の記号を操作する理論的な装置です。その単純さにもかかわらず、チューリング マシンは、任意のコンピューター アルゴリズムのロジックをシミュレートするように適合させることができ、コンピューター内部の CPU の機能を説明するのに特に役立ちます。
このマシンと非決定論的マシン (実際には存在しません) のような他のマシンは、複雑さを計算するのに非常に役立ち、あるアルゴリズムが別のアルゴリズムよりも難しいことや、あるアルゴリズムが解けないことを証明します...など