決定性チューリング機械との等価性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/29 08:54 UTC 版)
「非決定性チューリングマシン」の記事における「決定性チューリング機械との等価性」の解説
直観的に NTM は、考えられる計算を同時並行的に行え、そのうち1つが成功すればよいのだから、DTM より強力であると思われるかもしれない。しかし、NTM が認識可能な言語は全て DTM でも認識可能である。DTM は NTM での遷移の分岐ごとに複製を作り、マルチタスクのような方法でそれらを並列にシミュレートできる。 このようなシミュレーションが NTM に比較して非常に時間がかかることは明らかである。一般にどれだけ長くかかるかは不明であり、これはP≠NP予想の問題と根本的には同じである。
※この「決定性チューリング機械との等価性」の解説は、「非決定性チューリングマシン」の解説の一部です。
「決定性チューリング機械との等価性」を含む「非決定性チューリングマシン」の記事については、「非決定性チューリングマシン」の概要を参照ください。
ウィキペディア小見出し辞書の「決定性チューリング機械との等価性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 決定性チューリング機械との等価性のページへのリンク
