ABSTRACT
Let Φ be a set of total functions. We generalize the notion of computable to allow us to use the values of the functions in Φ at any arguments we wish in the course of the computation. Following Turing, we picture the computation as 40taking place as follows. For each F in Φ, we are given an object called an oracle for F. During the computation, we may ask the oracle for F ( x → ) https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780203741139/8e9d6847-fedd-45bc-9ee6-91ac5be8d222/content/in12_1.tif"/> for any x → https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780203741139/8e9d6847-fedd-45bc-9ee6-91ac5be8d222/content/in2_1.tif"/> which we have computed. The oracle supplies the value, which may then be used in the rest of the computation. A function which can be computed using oracles for the functions in Φ is said to be computable in Φ or relative to Φ. (Turing used this terminology because the oracle produces a value of the function without the use of an algorithm. However, one should not consider an oracle as a mystical object. We can think of it as an infinite set of file cards on each of which a value of the function is printed; we get the value at a particular set of arguments by searching through the file.)
