Oracle Computing - Beräkning med en Turing-maskin utökad med ett orakel med okända interna funktioner. Det postuleras att oraklet kan "gissa" lösningen på avgörbarhetsproblemet i ett samtal (en cykel av den anropande Turing-maskinen), varefter (Turing-maskinen) bara kommer att behöva kontrollera denna lösning.
Turing-maskinen interagerar med oraklet genom att skriva indata till oraklet på dess band och sedan köra oraklet för exekvering. I ett steg utvärderar oraklet funktionen, raderar inmatningen och skriver utmatningen till bandet. Ibland beskrivs en Turing-maskin som att den har två band, ett för oraklets ingång och ett för utmatningen.
Komplexitetsklassen av problem lösta av en algoritm från klass A med ett orakel för ett problem av klass B betecknas med A B . Till exempel betecknas klassen av problem som löses i polynomtid av en deterministisk Turing-maskin med ett orakel för NP-problem med P NP .