Editing Oracle machine (section)

== Oracles ==

An oracle machine can be conceived as a [[Turing machine]] connected to an '''oracle'''. The oracle, in this context, is an entity capable of solving some problem, which for example may be a [[decision problem]] or a [[function problem]]. The problem does not have to be computable; the oracle is not assumed to be a Turing machine or computer program. The oracle is simply a "[[black box]]" that is able to produce a solution for any instance of a given [[computational problem]]:
* A decision problem is represented as a set ''A'' of natural numbers (or strings). An instance of the problem is an arbitrary [[natural number]] (or string). The solution to the instance is "YES" if the number (string) is in the set, and "NO" otherwise. 
* A function problem is represented by a function ''f'' from natural numbers (or strings) to natural numbers (or strings). An instance of the problem is an input ''x'' for ''f''. The solution is the value ''f''(''x'').

An oracle machine can perform all of the usual operations of a Turing machine, and can also query the oracle to obtain a solution to any instance of the computational problem for that oracle. For example, if the problem is a decision problem for a set ''A'' of natural numbers, the oracle machine supplies the oracle with a natural number, and the oracle responds with "yes" or "no" stating whether that number is an element of ''A''.