Máquina oráculo

En teoría de la complejidad y en la teoría de la computabilidad, una máquina oráculo es una máquina abstracta usada para estudiar problemas de decisión. Puede ser visualizada como una máquina de Turing con una caja negra, llamada oráculo, la cual puede decidir ciertos problemas de decisión en una simple operación. El problema puede ser cualquier clase de complejidad. Incluso pueden usarse problemas indecidibles, como el problema de la parada.