預言機

维基百科,自由的百科全书
跳转至: 导航搜索

预言机(oracle machine)又稱谕示机,是在計算複雜度理論可計算性理論中,用來研究決定型問題抽象電腦。可以被視為一個多了個黑盒子(預言)的圖靈機,這個黑盒子的功能是可以在單位時間之內解答特定問題。預言可以解答的問題,根據給定可以是任何複雜度類之內的問題。甚至可以使用非決定型問題這一類,像是停機問題

定義[编辑]

一個預言機可以視為是與一個預言(oracle)相連接的圖靈機。所謂預言的概念,是一個可以回答特定問題集合的一個實體,而且常常使用特定的自然數子集A來表示這個問題。我們可以很自然的發現,一個預言機可以執行很多對一般圖靈機來說很特殊的操作,並且可以藉由詢問預言來獲得"x是否在A內?"這種特定形式問題的解答。

一個預言機,基本上必定包含一整個圖靈機。除了這個圖靈機之外,一個預言機還包含了:

  • 一個預言紙帶(oracle tape),印上了一個包含許多B(代表空白)和1的無限序列,代表了一個可以計算預言集合(oracle set)A的函式;
  • 一個預言讀取頭(oracle head),像是圖靈機的讀寫頭一樣可以在紙帶上左右移動來讀取資料,不同的是它不能寫入,而且跑的紙帶是預言紙帶。

這裡給出的定義只是幾種預言的其中一種方式。不過這一些定義大同小異,因為所有這一些定義都是表示這機器實做了某個能夠運算A的特定函式f

正式定義[编辑]

一個預言機是由四個多元組M= \langle Q, \delta, q_0, F \rangle構成如下:

  • Q是有限多個狀態
  • \delta: Q \times \{B,1\}^2 \rightarrow Q \times \{B,1\} \times \{L,R\}^2是一個叫做轉化函數(transition function)的部分函數(partial function),這裡L代表左移,R代表右移。
  • q_0 \in Q代表起始狀態
  • F \subseteq Q停止狀態的集合。

預言機以包含有限但許多的1、其餘為空白的一些輸入訊號的工作帶(work tape)開始,包含預言獨特功能的預言帶A,和處於q0狀態的圖靈機,其讀寫頭正讀著工作帶第一個非空格的格子,而預言讀取頭則讀著相當於\chi_A(0)的預言帶的格子。

與預言機相關的複雜度類[编辑]

我們以AL這個符號,代表一個複雜度類裡面的決定性問題可以使用包含在A類別裡面的演算法,加上帶有針對L語言之預言的預言機。舉例來說,PSAT這個複雜度類,裡面的問題以一個帶有布爾可滿足性問題預言的預言機,以多項式时间可以解決。AB這種表示法也可以引申成令B是一個問題的集合或者是一個複雜度類,使用的定義如下:A^B = \bigcup_{L \in B} A^L

當語言L是複雜度類B裡面的完備問題時,如果這個完備定義內所使用的歸約過程是在A複雜度裡面,則AL=AB。例如,因為SAT在多項式歸約裡面是NP-完全,PSAT=PNP。然而,要是A = DLOGTIME,因為SAT在DLOGTIME裡面並不一定是NP-完全,那麼ASAT並不一定等於ANP

很顯然的,NP ⊆ PNP,但是NPNP,PNP,NP和P要相等則僅在最佳狀況才有可能。一般相信這些複雜度類不相等,並且導出了多項式譜系這個定義。

利用預言機,研究像是針對某種預言A,PA和NPA之間的關係,對於研究P/NP問題非常的有幫助。舉例來說,已經證明出分別存在語言A和B,滿足PA=NPA與PB≠NPB[1] P = NP問題證偽與證明具有相對性被是為要證明這個問題是非常困難的一個佐證。因為這表示如果證明方法帶有相對性(這意思是說,增加了預言並不影響證明本身)都不可能解出P = NP問題。舉例來說,要是證明了P = NP,則這方法一定會被增加預言所影響,否則無法解釋存在預言B令PB≠NPB,但是多數證明方式都帶有相對性。

探討任意選擇預言A時,會對複雜度類產生怎樣的變化是一個很有趣的問題(當然,這裡所有預言的母體是一個無限大的集合)。我們已經知道,任意選擇預言A的話,PA≠NPA.[2]。當一個陳述幾乎對所有預言成立時,在機率母體是無限多的預言這個情況,我們可以說"對這個情況,任意的預言均成立"。這個術語的成立基於選擇任意預言時,陳述成立的機率僅可能是零或一(根據零一律)。這被視為P≠NP的一個佐證。不過,一個陳述可以同時對任意預言都成立,但是對一般圖靈機不成立;例如,對任意預言A,IPA≠PSPACEA,但是IP = PSPACE.[3]

預言以及停機問題[编辑]

即使一個問題是不可計算的,我們還是可以定義一個解答這類問題的預言,像是回答停機問題或者同類問題的預言。一個帶有這類預言的機器又被叫做超計算機

有趣的是,停機問題的矛盾還是存在於這種機器上面;即使一個機器可以知道圖靈機的停機問題,但是他必定不能解決自己這類機器的停機問題。這個事實創造出了算術譜系,對每個解決停機問題更強的機器都會有難到不能解決的停機問題。

相關條目[编辑]

参考文献[编辑]

  1. ^ T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431-442 (1975)
  2. ^ 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)
  3. ^ Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, Pankaj Rohatgi. The Random Oracle Hypothesis is False. Journal of Computer and System Sciences, volume 49, issue 1, pp.24–39. August 1994. ISSN 0022-0000. http://citeseer.ist.psu.edu/282397.html

参考书目[编辑]

  • Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
  • C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Section 14.3: Oracles, pp. 339 – 343.
  • Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X.  Section 9.2: Relativization, pp.318 – 321.
  • Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. Turing's paper is in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.