チューリングマシンとアルゴリズムの違いは何ですか?

Obaid Ur Rehman

私の理解によれば、チューリングマシンはアルゴリズムの単なるマシン表現です。アルゴリズムとチューリングマシンに違いはありますか?

btilly

それらは非常に異なります。

アルゴリズムは手順です。通常、プログラミング言語でプログラムを書き留めることにより、さまざまな方法で指定できます。対照的に、チューリングマシンは、非常に特殊で非現実的なマシンで実行するように適合された手順を説明します。

ただし、アルゴリズムの特性は、それが実行されているマシンによって異なります。また、チューリングマシンは、実際に関心のあるマシンとはまったく異なります。したがって、すべてのアルゴリズムをチューリングマシンで表すことができますが、チューリングマシンは推奨される表現ではありません。また、チューリングマシンの表現は、アルゴリズムの最も興味深いプロパティを覆い隠します。

たとえば、マージソートは広く知られていますO(n log(n))1960年代のドナルドクヌースの人工MIXアーキテクチャから、今日のクラウドでの高度に並列化された分散実装まで、あらゆるものに対応できます。

しかし、チューリングマシンでは、2つの配列を並列に繰り返し、3つ目の配列に書き込むには、テープ内の2つの離れた場所の間を絶えず前後に探して比較し、出力を書き込む場所をもう一度探す必要があります。したがって、認識可能なマージソートを実装するチューリングマシンを構築することはできますが、そうではありませO(n log(n))カントリーマイルではありません。そして実際には、バブルソートよりもはるかにパフォーマンスが低下します。(バブルソートはテープ上で物事を比較するだけなので、前後に探す時間が少なくて済みます。)

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]

編集
0

コメントを追加

0

関連記事

分類Dev

チューリングマシンのアルゴリズム

分類Dev

チューリングマシンのこのアルゴリズムを正式に説明するにはどうすればよいですか?

分類Dev

ベルマンフォード法とフロイドウォーシャルアルゴリズムの基本的な違いは何ですか?

分類Dev

無向グラフと有向グラフの最小スパニングツリーアルゴリズムの違いは何ですか?

分類Dev

クロスエントロピーと遺伝的アルゴリズムの違いは何ですか?

分類Dev

ポーターとランカスターのステミングアルゴリズムの主な違いと利点は何ですか?

分類Dev

遺伝的アルゴリズム/遺伝的プログラミングソリューションの良い例は何ですか?

分類Dev

シリアル化とマーシャリングの違いは何ですか?

分類Dev

アンカーピアとゴシップリーディングピアの違いは何ですか?

分類Dev

OpenCVのkmeansアルゴリズムとcvKMeans2アルゴリズムの違いは何ですか?

分類Dev

このソリューションのアルゴリズムの複雑さは何ですか?

分類Dev

生成アルゴリズムと識別アルゴリズムの違いは何ですか?

分類Dev

遺伝的アルゴリズムと反復局所探索アルゴリズムの違いは何ですか?

分類Dev

BFSアルゴリズムとDFSアルゴリズムの違いは何ですか?

分類Dev

トップダウンアルゴリズムと分割統治アルゴリズムの違いは何ですか?

分類Dev

この(プリエンプティブではない)スケジューリングアルゴリズムの複雑さは何ですか?

分類Dev

一意のフォームアルゴリズムと一意のリストコンテナの違いは何ですか?

分類Dev

暗号アルゴリズムAESとAES_128の違いは何ですか

分類Dev

このスケジューリングアルゴリズムのシナリオに答える最良の方法は何ですか?

分類Dev

コーディングインタビューをクラックすることからのアルゴリズムは何か間違っているようです

分類Dev

マルチプロセッシングモジュールのThreadPoolとPoolの違いは何ですか?

分類Dev

ニューラルネットワークフレームワークとRLアルゴリズムライブラリの違いは何ですか?

分類Dev

Javaでシングルスレッドの複雑なアルゴリズムを測定するための最良のマクロベンチマークツール/フレームワークは何ですか?

分類Dev

Youtubeコメントシステムのソート/ランキングアルゴリズムとは何ですか?

分類Dev

フレーズクエリとシングルフィルターの使用の違いは何ですか?

分類Dev

イーサリアムとチェーンの違いは何ですか?

分類Dev

巡回セールスマン問題を解決するとき、ブランチアンドバウンドアルゴリズムはブルートフォースアルゴリズムよりどのくらい高速ですか?

分類Dev

並列アルゴリズム分析における作業、スパン、時間の違いは何ですか?

分類Dev

Qtとstd :: stringの一般的で効率的なトリミングアルゴリズムは何ですか?

Related 関連記事

  1. 1

    チューリングマシンのアルゴリズム

  2. 2

    チューリングマシンのこのアルゴリズムを正式に説明するにはどうすればよいですか?

  3. 3

    ベルマンフォード法とフロイドウォーシャルアルゴリズムの基本的な違いは何ですか?

  4. 4

    無向グラフと有向グラフの最小スパニングツリーアルゴリズムの違いは何ですか?

  5. 5

    クロスエントロピーと遺伝的アルゴリズムの違いは何ですか?

  6. 6

    ポーターとランカスターのステミングアルゴリズムの主な違いと利点は何ですか?

  7. 7

    遺伝的アルゴリズム/遺伝的プログラミングソリューションの良い例は何ですか?

  8. 8

    シリアル化とマーシャリングの違いは何ですか?

  9. 9

    アンカーピアとゴシップリーディングピアの違いは何ですか?

  10. 10

    OpenCVのkmeansアルゴリズムとcvKMeans2アルゴリズムの違いは何ですか?

  11. 11

    このソリューションのアルゴリズムの複雑さは何ですか?

  12. 12

    生成アルゴリズムと識別アルゴリズムの違いは何ですか?

  13. 13

    遺伝的アルゴリズムと反復局所探索アルゴリズムの違いは何ですか?

  14. 14

    BFSアルゴリズムとDFSアルゴリズムの違いは何ですか?

  15. 15

    トップダウンアルゴリズムと分割統治アルゴリズムの違いは何ですか?

  16. 16

    この(プリエンプティブではない)スケジューリングアルゴリズムの複雑さは何ですか?

  17. 17

    一意のフォームアルゴリズムと一意のリストコンテナの違いは何ですか?

  18. 18

    暗号アルゴリズムAESとAES_128の違いは何ですか

  19. 19

    このスケジューリングアルゴリズムのシナリオに答える最良の方法は何ですか?

  20. 20

    コーディングインタビューをクラックすることからのアルゴリズムは何か間違っているようです

  21. 21

    マルチプロセッシングモジュールのThreadPoolとPoolの違いは何ですか?

  22. 22

    ニューラルネットワークフレームワークとRLアルゴリズムライブラリの違いは何ですか?

  23. 23

    Javaでシングルスレッドの複雑なアルゴリズムを測定するための最良のマクロベンチマークツール/フレームワークは何ですか?

  24. 24

    Youtubeコメントシステムのソート/ランキングアルゴリズムとは何ですか?

  25. 25

    フレーズクエリとシングルフィルターの使用の違いは何ですか?

  26. 26

    イーサリアムとチェーンの違いは何ですか?

  27. 27

    巡回セールスマン問題を解決するとき、ブランチアンドバウンドアルゴリズムはブルートフォースアルゴリズムよりどのくらい高速ですか?

  28. 28

    並列アルゴリズム分析における作業、スパン、時間の違いは何ですか?

  29. 29

    Qtとstd :: stringの一般的で効率的なトリミングアルゴリズムは何ですか?

ホットタグ

アーカイブ