私の理解によれば、チューリングマシンはアルゴリズムの単なるマシン表現です。アルゴリズムとチューリングマシンに違いはありますか?
それらは非常に異なります。
アルゴリズムは手順です。通常、プログラミング言語でプログラムを書き留めることにより、さまざまな方法で指定できます。対照的に、チューリングマシンは、非常に特殊で非現実的なマシンで実行するように適合された手順を説明します。
ただし、アルゴリズムの特性は、それが実行されているマシンによって異なります。また、チューリングマシンは、実際に関心のあるマシンとはまったく異なります。したがって、すべてのアルゴリズムをチューリングマシンで表すことができますが、チューリングマシンは推奨される表現ではありません。また、チューリングマシンの表現は、アルゴリズムの最も興味深いプロパティを覆い隠します。
たとえば、マージソートは広く知られていますO(n log(n))
。1960年代のドナルドクヌースの人工MIXアーキテクチャから、今日のクラウドでの高度に並列化された分散実装まで、あらゆるものに対応できます。
しかし、チューリングマシンでは、2つの配列を並列に繰り返し、3つ目の配列に書き込むには、テープ内の2つの離れた場所の間を絶えず前後に探して比較し、出力を書き込む場所をもう一度探す必要があります。したがって、認識可能なマージソートを実装するチューリングマシンを構築することはできますが、そうではありませんO(n log(n))
。カントリーマイルではありません。そして実際には、バブルソートよりもはるかにパフォーマンスが低下します。(バブルソートはテープ上で物事を比較するだけなので、前後に探す時間が少なくて済みます。)
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加