預言機的結構和運作原理主要是基於傳統的圖靈機，但它添加了一個稱為預言者的特殊組件，讓它能夠在運算過程中解答特定問題。以下是預言機的結構和運作原理的詳細說明，以及它與傳統圖靈機之間的主要區別：

### 預言機的結構

1. **圖靈機部分**：預言機基本上包含一個標準的圖靈機，其組成部分包括有限的狀態集（Q）、轉化函數（δ）、起始狀態（q₀）和停止狀態集合（F）。

2. **預言紙帶**：預言機擁有一條特殊的預言紙帶，這條帶上印有無限長的序列，這些序列由特定的 1 和空白 B 組成，代表了預言者能夠回答的問題集合 A。

3. **預言讀取頭**：預言機有一個預言讀取頭，這個讀取頭能夠在預言紙帶上左右移動，但不能寫入資料。這使得預言機能夠在運行過程中向預言者詢問特定問題的答案，如「某個輸入是否屬於集合 A」。

### 預言機的運作原理

預言機在執行時，如同傳統的圖靈機，也會在工作帶上讀取和寫入資料。當它進行計算時，若需要了解某個特定的問題是否在預言集合 A 內，它可以立即詢問預言者並獲得答案。這一部份的即時訪問使得預言機能夠解決一些傳統圖靈機無法解決的問題，甚至是一些不可判定的問題。

### 與傳統圖靈機的主要區別

1. **問題解答的能力**：傳統圖靈機只能根據其自身的演算法和結構來解決問題，而預言機可以使用外部預言者的即時解答來處理問題，因此其計算能力更強大。

2. **可解決問題的範圍**：預言機能夠處理一些傳統圖靈機無法計算的問題。例如，利用預言者回答停機問題，預言機能解決某些不可判定問題，而這對於標準的圖靈機來說則是無法達成的。

3. **運算速度**：預言機的運算可以被視為在馬上得到特定問題的解答，這不同於傳統圖靈機需要依賴一系列的計算過程來獲得結果。這使得預言機在計算某些複雜問題時，相較於傳統圖靈機能夠更快速地得出結論。

總結來說，預言機透過加入預言者的概念，極大地擴展了計算的疆界，使得即使是一些複雜且不可判定的問題也能夠在理論上得到處理，而這是傳統圖靈機所無法實現的。
預言機的結構和運作原理是什麼？它與傳統圖靈機之間有何主要區別？
在計算複雜度理論與可計算性理論中，**預言機**（英語：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_，和處於 _q_0 狀態的圖靈機，其讀寫頭正讀著工作帶第一個非空格的格子，而預言讀取頭則讀著相當於 $\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。
P = NP 問題證偽與證明具有相對性被視為要證明這個問題是非常困難的一個佐證。因為這表示如果證明方法帶有_相對性_（這意思是說，增加了預言並不影響證明本身）都不可能解出 P = NP 問題。舉例來說，要是證明了 P = NP，則這方法一定會被增加預言者所影響，否則無法解釋存在預言者 B 令 PB≠NPB，但是多數證明方式都帶有相對性。

探討從所有可能的預言機中（一個無限大的集合）任意選擇預言機 A 時，會對複雜度類產生怎樣的變化是一個很有趣的問題。我們已經知道，任意選擇預言機 A 的話，PA≠NPA。當一個陳述對幾乎所有預言機成立時，我們可以說「對隨機預言機也成立」。這個術語的成立基於隨機預言機選擇支持陳述的機率僅可能是零或一（根據零一律）。這被視為 P≠NP 的一個佐證。不過，一個陳述可以同時對隨機預言機成立，但是對一般圖靈機不成立；例如，對任意預言 A，IPA≠PSPACEA，但是 IP = PSPACE.

## 預言以及停機問題

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

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

## 參見

* 黑盒
* 圖靈機
* 圖靈歸約
* 交互式證明系統
* 隨機預言機

## 參考文獻

## 參考書目

* 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.
**圖靈機**（英語：Turing machine），又稱**確定型圖靈機**，是英國數學家艾倫・圖靈於 1936 年提出的一種將人的計算行為抽象化的數學邏輯機，其更抽象的意義為一種計算模型，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。 ## 定義

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

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

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

這裡給出的定義只是幾種預言的其中一種方式。不過這一些定義大同小異，因為所有這一些定義都是表示這部機器做了某個能夠運算 _A_ 的特定函式 _f_。 在密碼學裡面，**隨機預言機**（英語：Random oracle）是一部預言機（可以理解為理論的黑箱），對任何輸入都回傳一個真正均勻隨機的輸出（請參考離散型均勻分佈），不過對相同的輸入，該預言機每次都會用同一方法輸出。換句話說，隨機預言機是一個將所有可能輸入與輸出作隨機映射的函數。

## 限制

任何只能產生有限個輸出的函數均不是一個隨機預言函數，因為隨機預言機的定義要求其是一個有無限個輸出的函數。

事實上，一些刻意設計的簽名和加密方式被證明如果使用隨機預言機的話是安全的，但是使用其他的函式替代隨機預言的話則明顯不安全。 另外，對任何比較自然的安全協定，在隨機預言機模型之下證明為安全，是協定的「實用」可靠性的有力證據。

大體上說，一個作法被證明是安全的的話，要攻擊此作法就必需要突破該證明的假設；例如，一個加密法的安全證明是基於質因數分解的困難度（像是 RSA 演算法），那麼打破此證明的方法就是找到快速質因數分解的演算法（像是秀爾演算法就被視為是一個可能的攻擊）。在這裡，要打破隨機預言假設，我們就必須找到實際雜湊函式與隨機預言機未知且不好的不同之處。對於一般被認為不存在這種弱點，夠好的雜湊函式來說（這種雜湊函式現在被認爲是可靠的，像是 SHA-3），相關的協定因此可證明是安全的。

## 相關條目

* 預言機
* 標準模型 (密碼學)
* 密碼學主題列表
* 圖靈機
* 圖靈歸約
* 交互式證明系統

## 參考資料

## 外部連結

* The Random Oracle Model 在計算複雜度理論與可計算性理論中，**預言機**（英語：Oracle Machine），又稱**諭示機**，是一種抽象電腦，用來研究決定型問題。可以被視為具備在一次運算之內解答特定問題的黑盒子（又稱為預言者）的圖靈機；該問題可以是任何複雜度類，甚至可以是不可判定問題，像是停機問題。