3

チューリング マシンの拡張機能 (双方向無限テープ、RAM、複数の読み取り/書き込みヘッド、非決定性など) のうち、以前は決定できなかった問題を TM が決定できるものはありますか?

4

2 に答える 2

6

双方向の無限テープは、計算能力を拡張しません。RAM は状況によっては処理速度を変更しますが、計算能力は変更しません。複数の読み取り/書き込みヘッドを使用して、非決定論的チューリング マシン (NDTM) をシミュレートできますが、それでも計算能力は向上しません。

したがって、いいえ、これらの調整で新しい問題を解決することはできませんが、計算速度は時々変更される可能性があります。

これらの追加の拡張機能は、限られたステップ数内で単純なチューリング マシンに還元できます。また、その逆も可能です。ただ、TMは双方向無限テープが標準モデルだと思います。

(基本的な TM の拡張について話している間、Quantum TM を見てください。私が知る限り、まだ新しい問題を解決していません: http://en.wikipedia.org/wiki/Quantum_Turing_machine )

于 2013-04-30T19:09:53.580 に答える