チューリングマシンは実際のデバイスですか、それとも想像上の概念ですか?

theory turing-machines
チューリングマシンは実際のデバイスですか、それとも想像上の概念ですか?

チューリングマシンとPDAについて勉強しているとき、最初のコンピューティングデバイスはチューリングマシンだと思っていました。

したがって、チューリングマシンと呼ばれる実用的なマシンが存在し、その状態はいくつかの特別なデバイス(フリップフロップなど)で表すことができ、磁気テープの入力を受け入れることができると考えました。

したがって、https://stackoverflow.com/questions/7366085/how-input-string-is-represented-in-magnetic-tapes [磁気テープでの入力文字列の表現方法]に疑問を投げかけました。 しかし、答えと私の本で与えられた詳細によって、私はチューリング機械がなんらかの仮説的であることを知るようになりました。

私の質問は、チューリングマシンを実際にどのように実装するかです。 たとえば、現在のプロセッサのスペルエラーを確認するためにどのように使用されるか。

チューリングマシンは古くなっていますか? または、まだ使用されていますか?

  13  5


ベストアンサー

チューリングマシンは、いくつかの理由で実際には使用されません。 まず、無限のテープを構築するには無限のリソースが必要になるため、構築することはできません。 さらに、チューリングマシンは、データアクセスのシーケンシャルな性質のため、他の計算モデルよりも本質的に低速です。 チューリングマシンは、たとえば、最初にスキップする配列のすべての要素を横断しない限り、配列の中央にジャンプすることはできません。 さらに、チューリングマシンの設計は非常に困難です。 たとえば、チューリングマシンを作成して、32ビット整数のリストをソートしてみてください。 (実際には、しないでください。 本当に難しい!)

これは質問を頼みます…​ チューリング機械を研究する理由は何ですか? 幸いなことに、これを行うには非常に多くの理由があります。

  1. 計算される可能性があるものの限界について推論する。 なぜなら
    チューリングマシンは、地球上のコンピューター(または、チャーチチューリングの論文によると、物理的に実現可能なコンピューティングデバイス)をシミュレートできます。チューリングマシンが計算できるものの限界を示すことができれば、実際のコンピューターで達成されることを望みます。

  2. アルゴリズムの定義を形式化する。 なぜバイナリ検索は
    「答えを推測する」という文はそうではありませんが、アルゴリズム この質問に答えるためには、コンピューターとは何か、アルゴリズムが何を意味するかの正式なモデルが必要です。 チューリングマシンを計算のモデルとして使用すると、アルゴリズムを厳密に定義できます。 実際にアルゴリズムを形式に変換したい人は誰もいませんが、そうする能力はアルゴリズムと計算可能性理論の分野に確固たる数学的根拠を与えます。

  3. 決定論的および非決定論的の定義を形式化する
    アルゴリズム。 おそらく現在のコンピューターサイエンスにおける最大の未解決の問題は、P = NPかどうかという問題です。 この質問は、PおよびNPの正式な定義がある場合にのみ意味があり、決定論的および非決定論的計算の場合は定義が必要になります(技術的には2次論理を使用して定義できます)。 チューリングマシンを使用すると、NPの重要な問題について話すことができ、NP完全な問題を見つける方法も提供できます。 たとえば、SATがNP完全であることの証明では、SATを使用してチューリングマシンと入力での実行をエンコードできるという事実を使用します。

お役に立てれば!

29


これは概念的なデバイスであり、実現できません(無限テープの要件のため)。 チューリングマシンの物理的な実現を構築した人もいますが、物理的な制限のため、それは真のチューリングマシンではありません。

次の動画をご覧ください:http://www.youtube.com/watch?v=E3keLeMwfHY

6


これは理論的なマシンであり、ウィキペディアの次の段落

_
チューリングマシンは、規則の表に従ってテープストリップ上のシンボルを操作する理論上のデバイスです。 その単純さにもかかわらず、チューリングマシンは、任意のコンピューターアルゴリズムのロジックをシミュレートするように適合させることができ、コンピューター内部のCPUの機能を説明するのに特に役立ちます。 ブロッククォート
_

このマシンと非決定的マシン(実際には存在しない)のような他のマシンは、複雑さの計算に非常に役立ち、あるアルゴリズムが別のアルゴリズムよりも難しいか、またはあるアルゴリズムが解けないことを証明します…​など

0


チューリングマシンは物理的なマシンではなく、基本的に概念的なマシンです。 チューリングの概念は仮説であり、小さくて簡単な解決策にも無限のテープが必要なので、これを現実の世界に実装するのは非常に困難です。

-1


タイトルとURLをコピーしました