An oracle machine is a Turing machine connected to an oracle. The oracle, in this context, is thought of as an entity capable of answering some collection of questions, and usually represented as some subset A of the natural numbers. Intuitively then, the oracle machine can perform all of the usual operations of a Turing machine, and can also query the oracle for an answer to a specific question of the form "is x in A?"
The definition given here is one of several possible oracle machine definitions. All these definitions are equivalent, as they agree on which specific functions f can be computed by an oracle machine with oracle A.
An oracle machine, like a Turing machine, includes:
- a work tape: a sequence of cells without beginning or end, each of which may contain a B (for blank) or a 1;
- a read/write head, which rests on a single cell of the work tape and can read the data there, write new data, and move left or right along the tape;
- a control mechanism, which can be in one of a finite number of states, and which will perform different actions (reading data, writing data, moving the control mechanism, and changing states) depending on the current state and the data being read.
In addition to these components, an oracle machine also includes:
- an oracle tape, on which an infinite sequence of B's and 1's is printed, corresponding to the characteristic function of the oracle set A;
- an oracle head, which (like the read/write head) can move left or right along the oracle tape reading data, but which cannot write.
Read more about Oracle Machine: Complexity Classes of Oracle Machines, Oracles and Halting Problems, Applications To Cryptography
Famous quotes containing the words oracle and/or machine:
“There be three things which are too wonderful for me, yea, four which I know not: the way of an eagle in the air; the way of a serpent upon a rock; the way of a ship in the midst of the sea; and the way of a man with a maid.”
—Bible: Hebrew Proverbs, 30:18-19.
From the oracle of Agur, son of Jakeh.
“... in the fierce competition of modern society the only class left in the country possessing leisure is that of women supported in easy circumstances by husband or father, and it is to this class we must look for the maintenance of cultivated and refined tastes, for that value and pursuit of knowledge and of art for their own sakes which can alone save society from degenerating into a huge machine for making money, and gratifying the love of sensual luxury.”
—Mrs. H. O. Ward (1824–1899)