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:

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*.

There are many equivalent definitions of oracle Turing machines, as discussed below. The one presented here is from van Melkebeek (2000:43).

An oracle machine, like a Turing machine, includes:

In addition to these components, an oracle machine also includes:

This page was last edited on 8 January 2018, at 15:28.

Reference: https://en.wikipedia.org/wiki/Oracle_machine under CC BY-SA license.

Reference: https://en.wikipedia.org/wiki/Oracle_machine under CC BY-SA license.

- Complexity Theory
- Computability Theory
- Abstract Machine
- Decision Problems
- Turing Machine
- Complexity Class
- Undecidable Problems
- Halting Problem
- Turing Machine
- Decision Problem
- Function Problem
- Black Box

- Oracle Machine
- Thick-billed Fox Sparrow
- Roman Catholic Archdiocese Of Bucaramanga
- Dov Levin
- Gr%C3%A9gory Mallet
- Matt Barbet
- Our Boys Institute
- Johann Christoph Von Westerstetten
- Recanati Polyptych
- Cleveland State
- Tit Berrypecker
- Shirley Temple (cocktail)
- Malden, MA
- ABA Heavyweight Champions
- Austrian Identity Card
- Paul Barnes (footballer)
- Karl Wilhelm Ludwig Pappe
- United Nations General Assembly
- Eight Views Of Omi
- Anastasios Soulis
- Monitor Radio Network
- Ramsey St Mary%27s
- Tingha And Tucker
- High Court Of Karnataka
- Charles F. Curry, Jr.
- This Is My Element
- Kid Chan
- Edmonds Community College
- Kulebaki
- Efficient Frontier