私の知る限り、チューリング マシンを作成して、テープにエンコードされた命令のループまたは反復を実行できます。これは、ライン セパレータを特定し、ライン セパレータの特定の数に達するまで (つまり、ループ内で) チューリング マシンを戻すことによって実行できます。しかし、チューリングマシンは再帰プログラムも実行できるのでしょうか?
そのようなチューリングマシンのさまざまな詳細を誰かが説明できますか?
チューリングマシンで再帰が実行できれば、クイックソートも実行できるのではないでしょうか？
質問する
1730 次
2 に答える
10
チューリング マシンがソート アルゴリズムを実行できるかどうかという質問の場合、チューリング マシンではあらゆる計算可能な関数を実装できるため、答えはイエスです。ただし、質問が本当にクイックソートの構造を模倣し、その複雑さを維持することである場合、答えはそれほど単純ではなく、テープの数にも依存します。
n 個の要素があり、それぞれが次元 l=k*log(n) であると仮定すると、1 つのテープのチューリング マシンでの最適な並べ替えアルゴリズムの複雑さは O(n^2*log(n)) であることが証明されているため、この場合、答えはノーです。クイックソートに似たものは何もありません。一方、3 本のテープでは、複雑さ O(n*log(n)*l) で実行されるマージソートのようなアルゴリズムを作成できます。
データが単一のテープ セルに収まるとは期待できないため、データの次元 l はこのコンテキストに関連しています (そうでない場合、データは有限になり、有限範囲内の要素の並べ替えはより単純な線形問題になります)。
一般に、チューリング マシンの問題は、2 つのセルの内容を交換するには、それらの距離に比例して時間がかかることです。長さ l のテープの連続した部分を移動 (または比較) する必要がある場合、状況はさらに悪化します。1 つのテープ マシンでは、テープ上の 2 つの場所の間を l 回前後に移動する必要があるからです。
詳細な参考文献については、Holger Petersen 著、2008 年の「1 テープ オフライン チューリング マシンでのエレメントの明確性とソート」を参照してください。
于 2017-02-01T12:39:41.687 に答える
-4
はい、チューリング マシンはクイックソートを含む任意のアルゴリズムを実行できます。
于 2015-04-10T16:49:54.773 に答える