- Máquina oracle
-
La máquina oracle en teoría tiene como finalidad la de estudiar la decisión de problemas. Puede verse como una máquina de Turing con una caja negra, llamada oracle. La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor.
Contenido
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 oracle y seguidamente este se ejecuta, en un solo paso el oracle 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 oracle 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 oracle 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 oracle para el lenguaje B. Las máquinas oracle 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 oracle. 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 oracle es elegido al azar de entre todos los oracles posibles. Se ha demostrado que si el oracle, 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 oracles, se dice que es cierta para cualquier oracle escogido al azar. Por otro lado, una sentencia puede ser verdadera para un oracle al azar y en cambio falsa para una máquina de Turing. Problemas de paradas con oracles:
Es posible la existencia de un oracle que compute una función no-computable, como por ejemplo la respuesta al problema de parada o problemas similares. Una máquina con un oracle 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 oracle 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 con mayor problemas de paradas.
Aplicaciones a la criptografía
Hoy en día los oracles se usan en protocolos de criptografía. Si suponemos la existencia de un oracle al azar que da una respuesta a cualquier pregunta, entonces esto da que dada una respuesta por el oracle, es imposible para ningún programa averiguar cual es la entrada que ha producido la salida. Esto desemboca en protocolos muy fuertes usados en la criptografía.
Naturaleza de los oracles
Turing ya dejó claro que los oracles no eran máquinas. Además se entiende como máquina o maquinaria el ensamblaje de partes que transmiten fuerza, movimiento, energía mutuamente de una forma predeterminada. Un oracle no puede ser un ensamblaje de diversas partes, y tampoco puede ser un organismo vivo o uno de sus sistemas funcionales, así pues un oracle no es una máquina y por lo tanto su naturaleza se debería hallar en la metafísica.
Véase también
Enlaces externos
Categorías:- Lógica matemática
- Informática teórica
Wikimedia foundation. 2010.
