computer-science - 右チューリングマシン

Question

右にしか動かない（またはとどまる）ことができるチューリングマシンが、標準のチューリングマシンと同じかどうかを確認するように依頼しました。

入力を別のテープにコピーしようと思いましたが、制限はありませんでした。しかし、それは可能ですか？

ありがとう。

Answer 1

常に終了し、n個の状態があり、テープ/入力アルファベットが{0,1}であるようなTMについて考えてみます。サイズmの入力では、最大2 * m*nステップ後に停止する必要があります。これは、前進せずに同じシンボルを2回読み取ることで同じ状態を通過できないためです。もしそうなら、それは止まらないでしょう。

これは、そのようなTMによって解決可能なすべての問題がPにあることを意味します。一方、EXPTIMEの問題を解決するための通常のTMが存在します。PはEXPTIMEの適切なサブセットであるため、2つのモデルは同等ではありません。

ところで：チューリングマシンには通常テープが1つしかないため、別のテープにコピーすることはできません。

Answer 2

右にしか動かずにとどまることができるチューリングマシンは、チューリングマシンのバリエーションであり、標準のチューリングマシンのサブセットです。つまり、基本的には標準のチューリングマシンほど強力ではありませんが、それでもTMです。

さらに、複数のチューリングマシンテープを組み合わせても、計算能力は向上せず、単一の標準TMと完全に同等です。

（複数のテープは、計算ではなく効率の点でのみ有利です。ただし、TMは効率ではなく計算可能性のみを考慮しているため、これは関係ありません）。