En la teoría de la complejidad y la teoría de la computabilidad , una máquina de oráculo es una máquina abstracta utilizada para estudiar problemas de decisión . Se puede visualizar como una máquina de Turing con una caja negra , llamada oráculo , que es capaz de resolver ciertos problemas en una sola operación. El problema puede ser de cualquier clase de complejidad . Incluso se pueden utilizar problemas indecidibles , como el problema de detención .
Una máquina de oráculo puede concebirse como una máquina de Turing conectada a un oráculo . El oráculo, en este contexto, es una entidad capaz de resolver algún problema, que por ejemplo puede ser un problema de decisión o un problema de función . El problema no tiene que ser computable; no se supone que el oráculo sea una máquina de Turing o un programa de computadora. El oráculo es simplemente una " caja negra " que puede producir una solución para cualquier instancia de un problema computacional dado:
Una máquina de oráculo puede realizar todas las operaciones habituales de una máquina de Turing y también puede consultar al oráculo para obtener una solución a cualquier instancia del problema computacional para ese oráculo. Por ejemplo, si el problema es un problema de decisión para un conjunto A de números naturales, la máquina del oráculo proporciona al oráculo un número natural y el oráculo responde con un "sí" o un "no" indicando si ese número es un elemento de A. .
Hay muchas definiciones equivalentes de las máquinas de Turing del oráculo, como se explica a continuación. El que se presenta aquí es de van Melkebeek (2000:43).
De vez en cuando, la máquina Oracle puede entrar en el estado ASK. Cuando esto sucede, las siguientes acciones se realizan en un solo paso computacional:
El efecto de cambiar al estado ASK es recibir, en un solo paso, una solución a la instancia del problema que está escrita en la cinta de Oracle.