ウィキペディア

神託機械

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2011/03/06 12:00 UTC 版)

神託機械（しんたくきかい、英: Oracle machine）または預言機械（よげんきかい）は、計算複雑性理論や計算可能性理論における抽象機械の一種であり、決定問題の研究で使われる。チューリングマシンにオラクル（oracle）と呼ばれるブラックボックスが付加されたものとして具体化され、そのブラックボックスは特定の決定問題を1ステップで決定可能である。その問題は任意の複雑性クラスに属する。チューリングマシンの停止問題のような決定不能な問題にも神託機械を想定することができる。