預言機

定義

• 一條預言紙帶oracle tape），印上了一個包含許多B（代表空白）和1的無限序列，代表了一個可以計算預言集合（oracle setA的函式;

正式定義

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

參考文獻

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.