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.
Operaciones
- avanzar el cabezal lector/escritor para la derecha.
- avanzar el cabezal lector/escritor para la izquierda.
La máquina de Turing escribe en su cinta una entrada para el oráculo y seguidamente este se ejecuta, en un solo paso el oráculo computa la función, borra la entrada y escribe la salida a la cinta. A veces la máquina de Turing es descrita con dos cintas, una destinada a pasar las entradas al oráculo y la otra a recibir las salidas del mismo.
Clases
La clase de complejidad de problemas de decisión que pueden ser resueltas por un algoritmo en clase A con un oráculo para un problema en clase B se escribe de la siguiente forma: A^B. La notación A^B también significa la clase de problemas que resolver por el algoritmo en clase A con un oráculo para el lenguaje B. Las máquinas oráculo son útiles para investigar la relación entre complejidad de clases, por ejemplo entre P y NP, considerando la relación entre P^A y NP^A siendo A un oráculo. En particular se ha demostrado que existen idiomas A y B donde P^A = NP^A, pero en cambio P^B ≠ NP^B.
Es interesante considerar el caso en el que el oráculo es elegido al azar de entre todos los oráculos posibles. Se ha demostrado que si el oráculo, verdaderamente se ha elegido al azar, entonces, con probabilidad de 1, P^A ≠ NP^A (Bennett, Gill, 1981). Cuando una pregunta es verdadera para casi todos los oráculos, se dice que es cierta para cualquier oráculo escogido al azar. Por otro lado, una sentencia puede ser verdadera para un oráculo al azar y en cambio falsa para una máquina de Turing. Problemas de paradas con oráculos:
Es posible la existencia de un oráculo que compute una función no-computable, como por ejemplo la respuesta al problema de parada o problemas similares. Una máquina con un oráculo de este tipo es una hipercomputadora. Con hipercomputadora se hace referencia a varios métodos propuestos para la computación de funciones no computables por máquinas de Turing, este término fue introducido por primera vez por Jack Copeland.
Aunque pueden determinar si una particular máquina de Turing se parará con unas determinadas entradas, no pueden determinar si las máquinas oráculo que detectan la parada también se pararán o no. Este hecho crea una jerarquía de máquinas, conocida como la jerarquía aritmética, en la cual cada una tiene un mayor potencial y a su vez un mayor problema de parada.
Aplicaciones a la criptografía
Hoy en día los oráculos se usan en protocolos de criptografía. Si suponemos la existencia de un oráculo al azar que da una respuesta a cualquier pregunta, entonces esto da que dada una respuesta por el oráculo, es imposible para algún programa averiguar cual es la entrada que ha producido la salida. Esto desemboca en protocolos muy fuertes usados en la criptografía.