Oracle Computing - Práce na počítači s Turingovým strojem rozšířeným o věštce s neznámými internals. Předpokládá se, že orákulum je schopno „uhádnout“ řešení problému rozhodnutelnosti v jednom volání (jeden cyklus volajícího Turingova stroje), po kterém bude muset (Turingův stroj) toto řešení pouze zkontrolovat.
Turingův stroj interaguje s věštcem tak, že zapíše vstup věštci na jeho pásku a poté spustí věštce k provedení. V jednom kroku orákulum vyhodnotí funkci, vymaže vstup a zapíše výstup na pásku. Někdy je Turingův stroj popisován tak, že má dvě pásky, jednu pro vstup věštce a jednu pro výstup.
Třída složitosti problémů řešených algoritmem třídy A s věštcem pro problém třídy B se značí A B . Například třída problémů řešených v polynomiálním čase deterministickým Turingovým strojem s věštcem pro NP problémy je označena P NP .