神託機械 - Wikipedia神託機械（しんたくきかい、英: oracle machine）または預言機械（よげんきかい）は、計算複雑性理論や計算可能性理論における抽象機械の一種であり、決定問題の研究で使われる。チューリングマシンに神託（oracle）と呼ばれるブラックボックスが付加されたものであり、そのブラックボックスは特定の決定問題を1ステップで決定可能である。チューリングマシンの停止問題のような決定不能な問題にも神託機械を想定することができる。 定義[編集] 神託機械はオラクル付きのチューリングマシンである。チューリングマシンはオラクルへの入力を自身のテープに書き込み、オラクルにその実行を指示する。1ステップでオラクルはそれを計算し、入力を消去して出力をテープに書き込む。場合によってはチューリングマシンが2本のテープを持つように描かれる場合もあり、一方がオラクルへの入力、もう一方がオラクルからの出力に使われる。
