神託機械
オラクルとは特定の決定問題を1ステップで決定可能なブラックボックスである.
オラクル付きのTMを神託機械という.
ブラックボックスなので停止性問題を1ステップで解けるブラックボックスを仮定することも出来る.
余談: 多項式階層 の話に繋がる.
余談: ランダムオラクル: 無作為に同じ値には同じ答えを返すオラクルは理想的な One-way function として扱うことが出来る. しばしば暗号理論の証明で用いられ, ランダムオラクル仮定 のもとで安全と言ったりする.
オラクルとは特定の決定問題を1ステップで決定可能なブラックボックスである.
オラクル付きのTMを神託機械という.
ブラックボックスなので停止性問題を1ステップで解けるブラックボックスを仮定することも出来る.
余談: 多項式階層 の話に繋がる.
余談: ランダムオラクル: 無作為に同じ値には同じ答えを返すオラクルは理想的な One-way function として扱うことが出来る. しばしば暗号理論の証明で用いられ, ランダムオラクル仮定 のもとで安全と言ったりする.