Oracle Computing : computación con una máquina de Turing aumentada con un oráculo con componentes internos desconocidos. Se postula que el oráculo es capaz de "adivinar" la solución al problema de decidibilidad en una llamada (un ciclo de la máquina de Turing que llama), después de lo cual (la máquina de Turing) solo tendrá que comprobar esta solución.
La máquina de Turing interactúa con el oráculo escribiendo entradas al oráculo en su cinta y luego ejecutando el oráculo para su ejecución. En un solo paso, el oráculo evalúa la función, borra la entrada y escribe la salida en la cinta. A veces, se describe que una máquina de Turing tiene dos cintas, una para la entrada del oráculo y otra para la salida.
La clase de complejidad de problemas resueltos por un algoritmo de clase A con un oráculo para un problema de clase B se denota por A B . Por ejemplo, la clase de problemas resueltos en tiempo polinomial por una máquina de Turing determinista con un oráculo para problemas NP se denota por P NP .