神託機械とは? わかりやすく解説

神託機械

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/03/12 02:16 UTC 版)

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

定義

神託機械はオラクル付きのチューリングマシンである。チューリングマシンはオラクルへの入力を自身のテープに書き込み、オラクルにその実行を指示する。1ステップでオラクルはそれを計算し、入力を消去して出力をテープに書き込む。場合によってはチューリングマシンが2本のテープを持つように描かれる場合もあり、一方がオラクルへの入力、もう一方がオラクルからの出力に使われる。

神託機械の複雑性クラス

クラス A のアルゴリズムにクラス B の問題を解くオラクルを組み合わせることで解ける決定問題複雑性クラスを AB と表記する。例えば、決定性チューリングマシンNPクラスのオラクルが付属したもので多項式時間で解ける問題のクラスは、PNP で表される。このクラスの問題は、NPクラスに多項式時間チューリング還元で還元可能である。

NP ⊆ PNP であることは明らかだが、NPNP、PNP、NP、P の関係(等価かどうか)は未解決の問題である。詳しくは多項式階層を参照されたい。

AB は、クラス A のアルゴリズムに「言語」B のオラクルを付加することで解ける問題のクラスをも意味している。例えば、PSAT は、チューリングマシン充足可能性問題のオラクルを付与することで多項式時間で解ける問題のクラスである。言語 B がクラス C について完全であるとき、AB=AC が成り立つ。特に SAT はNP完全問題なので、PSAT=PNP となる。

神託機械は、例えばオラクル A について PA と NPA の関係を考えることでP≠NP予想の研究に役立つ。例えば、PA=NPA かつ PB≠NPB であるような言語 A と B が存在することが示されている(Baker、Gill、Solovay、1975)。どのような相対化された証明方法(すなわち、オラクルの有無が影響しない方法)もP=NP問題に答えられないことから、P=NP問題が両方の方法を相対化するという事実はこの問題が難しいということの証拠である。

考えられる様々な神託機械から無作為の1つの神託機械を選ぶ場合を考える。神託機械 A が無作為に選ばれた場合、確率 1 で PA≠NPA となる(Bennett, Gill, 1981)。ある質問がほとんど全ての神託機械で真となる場合、「ランダムオラクル」についても真と言える。これは、P≠NP の証拠とされることもある。だが、ランダムオラクルにとっては真だが、通常のチューリングマシンでは偽となるような文がありうる。

オラクルと停止問題

計算不可能とされている計算を行う神託機械を想定することもある。例えばチューリングマシンの停止問題やそれと等価な問題を解ける神託機械である。このようなオラクルを付加された機械をハイパーコンピュータと呼ぶ。

停止問題はそのような機械にも適用される。すなわち、そのような神託機械は、あるチューリングマシンが与えられた入力について停止するかどうかを判定できるが、神託機械自身が与えられた入力について停止するかどうかは判定できない。ここから機械の一種の階層が生み出され、これを算術的階層と呼ぶ。この階層はどこまでいっても判定不能な問題が存在することを示している。

暗号への応用

最近の計算機科学での神託機械の応用として、暗号への応用がある。質問に対して無作為だが一貫した答を返す(同じ質問には同じ答を返す)ランダムオラクルがあったとしたとき、非常に安全な一方向性関数として利用できる。すなわちランダムオラクルの出力を得ても、総当り的に入力値を試してみない限り入力を探し出すプログラムは作成できない。これにより非常に強力な暗号ができるが、実際にはランダムオラクルではなく擬似乱数生成器が使われることになる。だが、擬似乱数生成器はランダムオラクルほど安全ではない。

関連項目

参考文献

  1. Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
  2. C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Section 14.3: Oracles, pp. 339 – 343.
  3. T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431-442 (1975)
  4. C. H. Bennett, J. Gill. Relative to a Random Oracle A, PA != NPA != co-NPA with Probability 1. SIAM Journal on Computing, 10(1): 96-113 (1981)
  5. Michael Sipser (1997年). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X  Section 9.2: Relativization, pp.318 – 321.
  6. Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. チューリング、ゲーデル、チャーチ、クリーネの論文が掲載されている。

神託機械

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/10/17 08:19 UTC 版)

計算可能性理論」の記事における「神託機械」の解説

神託機械とは、特定の決定不能な問題への解を「神託」として与え機械である。例えば、チューリングマシンに「停止問題の神託機械」が付属していれば、与えられ入力についてそのチューリングマシン停止するかどうか即座に判定できるこのような機械再帰理論中心的話題である。

※この「神託機械」の解説は、「計算可能性理論」の解説の一部です。
「神託機械」を含む「計算可能性理論」の記事については、「計算可能性理論」の概要を参照ください。

ウィキペディア小見出し辞書の「神託機械」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「神託機械」の関連用語

神託機械のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



神託機械のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの神託機械 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの計算可能性理論 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS