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.

Other Languages