9.5 Welcome to Delphi

In ancient Greece, the Oracle of Delphi was a high priestess at the Temple of Apollo who issued prophecies under the right conditions and during warm weather. oracle

In computer science, an oracle is a function that we supply with data, and it responds with a 1 for yes and a 0 for no. Our oracles cannot answer random questions; we build them to respond to specific queries. For an algorithm using an oracle, two things are significant:

• The implementation of the oracle must be as fast and efficient as possible.
• We want to call the oracle as few times as possible to minimize the algorithm’s complexity.

An oracle is a black box, meaning we understand its behavior but not how it does what it does. We use it without seeing inside it.

Since we can represent all classical data by bits, we express the inputs to the oracle function as strings of zeros and ones. If we call the function f, which is traditional...