Mathematical logic and foundations Computability theory Concept
Oracle machine
Summary
An oracle machine is a Turing machine with an extra device, the oracle, that answers questions of the form "is in the set ?" in a single step. The set can be any set of natural numbers, even an uncomputable one. Oracle machines define relative computability: what can be computed if some set is given for free. They are used to define Turing reduction, Turing degrees and the Turing jump.
Where this leads
2 pages build on this one.
Further reading
About this page
| Tag | Z5CCVBME2V |
|---|---|
| URI | m2://Z5CCVBME2V |
| Kind | concept |
| Writing | W0 stub |
| MSC | 03D10, 03D30 |
| Specializes | Turing machine |
| Same as | |
| Changed | 2 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.