オラクルと停止問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/28 15:11 UTC 版)
計算不可能とされている計算を行う神託機械を想定することもある。例えばチューリングマシンの停止問題やそれと等価な問題を解ける神託機械である。このようなオラクルを付加された機械をハイパーコンピュータと呼ぶ。 停止問題はそのような機械にも適用される。すなわち、そのような神託機械は、あるチューリングマシンが与えられた入力について停止するかどうかを判定できるが、神託機械自身が与えられた入力について停止するかどうかは判定できない。ここから機械の一種の階層が生み出され、これを算術的階層と呼ぶ。この階層はどこまでいっても判定不能な問題が存在することを示している。
※この「オラクルと停止問題」の解説は、「神託機械」の解説の一部です。
「オラクルと停止問題」を含む「神託機械」の記事については、「神託機械」の概要を参照ください。
ウィキペディア小見出し辞書の「オラクルと停止問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- オラクルと停止問題のページへのリンク
