Máquina oracle

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


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Oracle WebLogic — es un servidor de aplicaciones Java EE y también un servidor web HTTP desarrollado por BEA Systems posteriormente adquirida por Oracle Corporation. Se ejecuta en Unix, Linux, Microsoft Windows, y otras plataformas. WebLogic puede utilizar Oracle …   Wikipedia Español

  • Base de datos de tablas de finales — Saltar a navegación, búsqueda Una interfaz típica para solicitar una base de datos de tablas. Para cada movimiento del Blanco, la base de datos devuelve el número de movimientos necesarios para ganar. Rc6 y Da6+ gana en cinco movimientos, por lo… …   Wikipedia Español

  • VirtualBox — Oracle VM VirtualBox VirtualBox 2.0.4 OSE virtualizando Fedora 10 en un anfitrión Ubuntu 8.10 Desarrollador Oracle Corporation …   Wikipedia Español

  • Java (lenguaje de programación) — Este artículo o sección se encuentra desactualizado. Es posible que la información suministrada aquí haya cambiado o sea insuficiente …   Wikipedia Español

  • Lenguaje de programación Java — Saltar a navegación, búsqueda Java Paradigma: Orientado a objetos Apareció en: 1991 Diseñado por: Sun Microsystems Tipo de dato: Fuerte, Estático Implementacion …   Wikipedia Español

  • Android — Parte de la familia Linux …   Wikipedia Español

  • Acorn Computers — Este artículo trata sobre Acorn Computers. Para la actual usuaria de la marca que fabrica sólo ordenadores para Windows , véase Acorn Computers Ltd. Acorn Computers Lema The choice of experience Fundación Diciembre de 1978 …   Wikipedia Español

  • VNC — son las siglas en inglés de Virtual Network Computing (Computación Virtual en Red). VNC es un programa de software libre basado en una estructura cliente servidor el cual nos permite tomar el control del ordenador servidor remotamente a través de …   Wikipedia Español

  • Sun Microsystems — Para otros usos de este término, véase Sun (desambiguación). Sun Microsystems Tipo Multinacional (NASDAQ: JAVA) Fundación 1982 Sede …   Wikipedia Español

  • Xen — es un monitor de máquina virtual de código abierto desarrollado por la Universidad de Cambridge. La meta del diseño es poder ejecutar instancias de sistemas operativos con todas sus características, de forma completamente funcional en un equipo… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”