基本介紹
- 中文名：預言機
- 外文名：Oracle machine
- 分類：計算機模型
定義,正式定義,與預言機相關的複雜度類,預言以及停機問題,相關條目,
定義
一部預言機可以視為是與一個預言者（oracle）相連線的圖靈機。所謂預言者的概念，是一個可以回答特定問題集合的一個實體，而且常常使用特定的自然數子集A來表示這個問題。我們可以很自然的發現，一部預言機可以執行很多對一般圖靈機來說很特殊的操作，並且可以藉由詢問預言者來獲得"x是否在A內?"這種特定形式問題的解答。
一部預言機，基本上必定包含一整個圖靈機。除了這個圖靈機之外，一部預言機還包含了：
- 一條預言紙帶（oracle tape），印上了一個包含許多B（代表空白）和1的無限序列，代表了一個可以計算預言集合（oracle set）A的函式;
- 一個預言讀取頭（oracle head），像是圖靈機的讀寫頭一樣可以在紙帶上左右移動來讀取資料，不同的是它不能寫入，而且跑的紙帶是預言紙帶。
這裡給出的定義只是幾種預言的其中一種方式。不過這一些定義大同小異，因為所有這一些定義都是表示這部機器做了某個能夠運算A的特定函式f。
正式定義
是有限多個狀態
預言機以包含有限但許多的1、其餘為空白的一些輸入訊號的工作帶（work tape）開始，包含預言獨特功能的預言帶A，和處於q0狀態的圖靈機，其讀寫頭正讀著工作帶第一個非空格的格子，而預言讀取頭則讀著相當於{\displaystyle \chi _{A}(0)}的預言帶的格子。
與預言機相關的複雜度類
我們以A這個符號，代表一個複雜度類裡面的決定性問題可以使用包含在A類別裡面的算法，加上帶有針對L語言之預言的預言機。舉例來說，P這個複雜度類，裡面的問題以一個帶有布爾可滿足性問題預言的預言機，以多項式時間可以解決。A這種表示法也可以引申成令B是一個問題的集合或者是一個複雜度類，使用的定義如下：
當語言L是複雜度類B裡面的完備問題時，如果這個完備定義內所使用的歸約過程是在A複雜度裡面，則A=A。例如，因為SAT在多項式歸約裡面是NP-完全，P=P。然而，要是A =DLOGTIME，因為SAT在DLOGTIME裡面並不一定是NP-完全，那么A並不一定等於A。
很顯然的，NP ⊆ P，但是NP，P，NP和P要相等則僅在最佳狀況才有可能。一般相信這些複雜度類不相等，並且導出了多項式譜系這個定義。
利用預言機，研究像是針對某種預言者A，P和NP之間的關係，對於研究P/NP問題非常的有幫助。舉例來說，已經證明出分別存在語言A和B，滿足P=NP與P≠NP。P = NP問題證偽與證明具有相對性被是為要證明這個問題是非常困難的一個佐證。因為這表示如果證明方法帶有相對性（這意思是說，增加了預言並不影響證明本身）都不可能解出P = NP問題。舉例來說，要是證明了P = NP，則這方法一定會被增加預言者所影響，否則無法解釋存在預言者B令P≠NP，但是多數證明方式都帶有相對性。
探討從所有可能的預言機中（一個無限大的集合）任意選擇預言機A時，會對複雜度類產生怎樣的變化是一個很有趣的問題。我們已經知道，任意選擇預言機A的話，P≠NP。當一個陳述對幾乎所有預言機成立時，我們可以說“對隨機預言機也成立”。這個術語的成立基於隨機預言機選擇支持陳述的機率僅可能是零或一（根據零一律）。這被視為P≠NP的一個佐證。不過，一個陳述可以同時對隨機預言機成立，但是對一般圖靈機不成立；例如，對任意預言A，IP≠PSPACE，但是IP=PSPACE。
預言以及停機問題
即使一個問題是不可計算的，我們還是可以定義一個解答這類問題的預言者，像是回答停機問題或者同類問題的預言者。一部帶有這類預言者的機器又被叫做超計算機。
有趣的是，停機問題的矛盾還是存在於這種機器上面；即使一個機器可以知道圖靈機的停機問題，但是他必定不能解決自己這類機器的停機問題。這個事實創造出了算術譜系，對每個解決停機問題更強的機器都會有難到不能解決的停機問題。
