チューリングは、停止問題がチューリング マシン上で決定不能であることを証明しました。ただし、実際のコンピューターは実際にはチューリング完全ではありません。無限のメモリがあれば、完全になるでしょう。
コンピュータのメモリ量は有限であり、完全なターニング完全ではないという事実を考えると、停止問題は決定可能になりますか? 私の直感では、そうですが、この制限付きの停止問題を解決するプログラムの時間と空間の複雑さは、対象となるコンピューターのメモリのサイズに指数関数的に比例する可能性があります。
1264 次
1 に答える
4
有限テープのチューリングマシンの停止問題は、無限テープのチューリングマシンで解くことができます。無限チューリング マシンがしなければならないことは、有限チューリング マシンのすべての可能な状態を列挙することです (非常に多くの数の可能な状態が存在します)。プログラムを実行しています。最終的に、次の 2 つのいずれかが発生します。
- 有限チューリングマシンは停止します。
- 有限チューリング マシンは状態を再訪します。状態を再訪する場合、マシンは決定論的であるため、無限ループがあることがわかります。したがって、次の状態は前の状態によって完全に決定されます。状態がある場合、マシンはth ステップ
nでそのうちの 1 つを再訪することが保証されます。n+1
于 2014-04-03T00:45:04.957 に答える