Máquina de Turing de oráculo

Máquina de Turing :

Alan Mathison Turing propuso la máquina de Turing en 1936, un modelo informático capaz de simular todos los comportamientos computacionales. Una máquina de Turing es una máquina ficticia. La máquina de Turing fue fundamental en el desarrollo de la computadora moderna.

• Una máquina de Turing es una máquina ficticia.
• A pesar de su sencillez, la máquina es capaz de simular CUALQUIER algoritmo informático, por complejo que sea.
• En aras de la simplicidad, supondremos que esta máquina solo puede procesar 0, 1 y en blanco.
• La máquina tiene un cabezal que se coloca sobre uno de los cuadrados de la cinta.
• El cabezal puede realizar las tres operaciones básicas que se enumeran a continuación:

                1. Leer los símbolos del cuadrado de la cabeza.

                2. Edite el símbolo reemplazándolo con un nuevo símbolo o borrándolo.

                3. Mueva la cinta hacia la izquierda o hacia la derecha un cuadrado para que la máquina pueda leer y editar el símbolo en el siguiente cuadrado

• Una representación muy básica de una máquina de Turing sería una cinta infinitamente larga (memoria)
• Cada cuadrado de la cinta está inicialmente en blanco y se pueden escribir símbolos sobre él.

El problema de la detención:

• Alan Turing demostró en 1936 que es imposible predecir si un programa arbitrario eventualmente terminará o se ejecutará indefinidamente.
• Martin Davis lo denominó el «problema de la detención» más adelante.
• Es uno de los primeros casos de un problema de decisión.

El problema de detención es el problema de determinar si un programa de computadora arbitrario terminará de ejecutarse o continuará ejecutándose indefinidamente en función de una descripción del programa y una entrada.

Por ejemplo:

• mientras (verdadero) continuar;

No se detiene; más bien, continúa indefinidamente en un ciclo infinito.

• imprimir «¡Hola mundo!»;

Se detendrá.

¿Por qué es importante el problema de la detención?

• Con frecuencia queremos saber si un programa converge (se detiene), pero no existe un único algoritmo que pueda responder a esta pregunta para todos los programas.
• Se demuestra que muchos problemas no tienen solución al reducirlos a problemas de parada.

Máquinas de Turing de Oracle:

Una máquina de Turing del oráculo es similar a una máquina de Turing estándar, pero con la adición de una segunda cinta conocida como la cinta del oráculo. Se pueden encontrar espacios en blanco (B), 0 o 1 en las celdas de la cinta de Oracle. Dado un conjunto A, una máquina Oracle Turing con Oracle A escribirá la función característica del conjunto A en una cinta. El cabezal de cinta de Oracle comienza en la celda con la letra X _A (0). X _A (1) está en la celda a la derecha de ésta, y así sucesivamente en orden creciente. Solo hay espacios en blanco a la izquierda de la celda donde comienza el encabezado de la cinta de Oracle.

El cálculo de una máquina de Turing de Oracle se lleva a cabo de la misma manera que un cálculo de máquina de Turing estándar. A pesar de que la cabeza de Oracle tiene un estado inicial de p0, la máquina de Turing se detiene si la cabeza de lectura/escritura entra en un estado de acento. La distinción clave entre una máquina de Turing con el oráculo A y una máquina de Turing regular es que un cálculo de parada de la máquina de Turing del oráculo puede determinar si A contiene o no un número finito de números.

La máquina de Oracle puede entrar ocasionalmente en el estado QUERY. Cuando esto ocurre, las siguientes operaciones se llevan a cabo en un solo paso computacional:

• Se lee el contenido de la cinta de Oracle.
• Se consulta el oráculo y el contenido de la cinta del oráculo se reemplaza con la solución a esa instancia específica del problema.
• El estado de la máquina de Oracle cambia a RESPUESTA, que puede ser Q _sí o Q _no.

Por lo tanto, cambiar al estado de CONSULTA da como resultado recibir una solución para la instancia del problema escrita en la cinta de Oracle en un solo paso.

Importancia de las máquinas Oracle Turing:

• Los OTM se pueden considerar como cálculos que utilizan subrutinas. Independientemente de la complejidad, el tiempo dedicado a estas subrutinas solo cuenta como un paso. Como resultado, OTMs es un modelo de computación ficticio.
• Se utiliza ampliamente en la teoría de las ciencias de la computación para estudiar la dificultad relativa de varios problemas.
• Ayudan en la codificación del concepto de reducciones de Turing.
• Ayudan a identificar algunos de los obstáculos para probar resultados en la teoría de la complejidad.
• También es importante en criptografía.