Máquina de Turing
La máquina de Turing (MT) es un ejecutor abstracto (computadora abstracta). Fue propuesto por Alan Turing en 1936 para formalizar el concepto de algoritmo .
Una máquina de Turing es una extensión de un autómata finito y, según la tesis de Church-Turing , es capaz de simular todos los ejecutores (estableciendo reglas de transición) que de alguna manera implementan un proceso de cálculo paso a paso en el que cada paso de cálculo es bastante elemental.
Es decir, cualquier algoritmo intuitivo puede implementarse utilizando alguna máquina de Turing [1] .
Dispositivo
La composición de la máquina de Turing incluye una cinta ilimitada en ambas direcciones (son posibles las máquinas de Turing que tienen varias cintas infinitas), dividida en celdas [2] [3] , y un dispositivo de control (también llamado cabezal de lectura y escritura ( GZCH ) ), capaz de estar en uno de los muchos estados . El número de estados posibles del dispositivo de control es finito y dado con exactitud.
El dispositivo de control puede moverse hacia la izquierda y hacia la derecha a lo largo de la cinta, leer y escribir caracteres de algún alfabeto finito en las celdas. Se asigna un símbolo vacío especial , que llena todas las celdas de la cinta, excepto aquellas (un número finito) en las que se escriben los datos de entrada.
El dispositivo de control opera de acuerdo con las reglas de transición , que representan el algoritmo implementado por la máquina de Turing dada. Cada regla de transición le indica a la máquina, según el estado actual y el símbolo observado en la celda actual, que escriba un nuevo símbolo en esta celda, vaya al nuevo estado y mueva una celda a la izquierda o a la derecha. Algunos estados de la máquina de Turing se pueden marcar como terminales , y el paso a cualquiera de ellos supone el final del trabajo, la parada del algoritmo.
Se dice que una máquina de Turing es determinista si cada combinación de estado y símbolo de cinta en la tabla coincide como máximo con una regla. Si hay un par "símbolo de cinta - estado" para el cual hay 2 o más instrucciones, tal máquina de Turing se llama no determinista .
Descripción de la máquina de Turing
Una máquina de Turing específica se especifica enumerando los elementos del conjunto de letras del alfabeto A, el conjunto de estados Q y el conjunto de reglas por las que opera la máquina. Tienen la forma: q i a j →q i1 a j1 d k (si la cabeza está en el estado q i , y la letra a j está escrita en la celda monitoreada , entonces la cabeza pasa al estado q i1 , a En la celda se escribe j1 en lugar de a j , la cabeza hace un movimiento d k , que tiene tres opciones: una celda a la izquierda (L), una celda a la derecha (R), permanecer en el lugar (N)). Para cada configuración posible <q i , a j > hay exactamente una regla (para una máquina de Turing no determinista puede haber más reglas). No hay reglas solo para el estado final, una vez en que la máquina se detiene. Además, debe especificar los estados inicial y final, la configuración inicial en la cinta y la ubicación del cabezal de la máquina.
Ejemplo
Un ejemplo de una máquina de Turing para multiplicar números en el sistema numérico unario . La entrada de la regla “q i a j →q i1 a j1 R/L/N” debe entenderse de la siguiente manera: q i es el estado en el que se ejecuta esta regla, a j son los datos en la celda en la que se encuentra la cabeza ubicado, q i1 es el estado al que desea ir, y j1 : lo que necesita escribir en la celda, R / L / N: el comando para moverse.
La máquina funciona de acuerdo con el siguiente conjunto de reglas:
| q0_ _ | q 1 | q2_ _ | q 3 | q 4 | q 5 | q 6 | q 7 | q 8 | |
|---|---|---|---|---|---|---|---|---|---|
| una | q 0 1→q 0 1R | q 1 1→q 2 aR | q 2 1→q 2 1L | q 3 1 → q 4 aR | q 4 1→q 4 1R | q 7 1→q 2 aR | |||
| × | q 0 ×→q 1 ×R | q2 ×→ q3 × L | q4 ×→ q4 × R | q6 ×→ q7 × R | q8 ×→ q9 × norte | ||||
| = | q 2 \u003d→q 2 \u003d L | q 4 \u003d→ q 4 \u003d R | q 7 \u003d→ q 8 \u003d L | ||||||
| a | q 2 a→q 2 aL | q 3 a→q 3 aL | q 4 a→q 4 aR | q 6 a→q 6 1R | q 7 a→q 7 aR | q 8 a→q 8 1L | |||
| * | q 0 *→q 0 *R | q3 *→ q6 * R | q 4 *→q 5 1R | ||||||
| q 5 →q 2 *L |
Descripción de estados:
| comienzo | |
| q0_ _ | estado inicial. Estamos buscando "x" a la derecha. Cuando lo encuentre, vaya al estado q1 |
|---|---|
| q 1 | reemplace "1" con "a" y vaya al estado q2 |
| Transferir todos los "1" del primer número al resultado | |
| q2_ _ | buscando "x" a la izquierda. Cuando lo encuentre, vaya al estado q3 |
| q 3 | busque "1" a la izquierda, reemplácelo con "a" y vaya al estado q4.
Si "1" ha terminado, busque "*" y vaya al estado q6 |
| q 4 | vaya al final (busque "*" a la derecha), reemplace "*" con "1" y vaya al estado q5 |
| q 5 | agregue "*" al final y vaya al estado q2 |
| Procesamos cada dígito del segundo número | |
| q 6 | buscamos "x" a la derecha y vamos al estado q7. Mientras mira, reemplace "a" con "1" |
| q 7 | buscando "1" o "=" a la derecha,
cuando se encuentra "1", lo reemplazamos con "a" y vamos al estado q2 al encontrar "=" ir al estado q8 |
| Final | |
| q 8 | buscando "x" a la izquierda. Cuando lo encuentre, vaya al estado q9. Mientras mira, reemplace "a" con "1" |
| q9 _ | estado terminal (parada de algoritmo) |
Multiplica con la ayuda de MT 3 por 2 en el sistema de unidades. El protocolo indica los estados inicial y final del MT, la configuración inicial en la cinta y la ubicación del cabezal de la máquina (símbolo subrayado).
Comienzo. Estamos en el estado q 0 , ingresamos los datos en la máquina: *111x11=*, el cabezal de la máquina se encuentra en el primer carácter *.
1er paso Nos fijamos en la tabla de reglas de lo que hará la máquina, estando en el estado q 0 y encima del símbolo “*”. Esta regla es de la primera columna de la quinta fila - q 0 *→q 0 *R. Esto significa que nos movemos al estado q 0 (es decir, no lo cambiamos), el símbolo se convierte en “*” (es decir, no cambia) y nos movemos a lo largo del texto “*111x11=*” que ingresamos a la derecha una posición (R), entonces hay un 1 para el 1er carácter A su vez, el estado q 0 1 (1ra columna 1ra fila) es procesado por la regla q 0 1→q 0 1R. Es decir, nuevamente solo hay una transición a la derecha de 1 posición. Esto sucede hasta que nos paramos en el símbolo "x". Y así sucesivamente: tomamos el estado (índice en q), tomamos el símbolo en el que nos encontramos (símbolo subrayado), los conectamos y observamos el procesamiento de la combinación resultante de acuerdo con la tabla de reglas.
En palabras simples, el algoritmo de multiplicación es el siguiente: marcamos la primera unidad del segundo factor, reemplazándola con la letra "a", y transferimos todo el primer factor más allá del signo igual. La transferencia se realiza reemplazando alternativamente las unidades del 1er multiplicador con "a" y agregando el mismo número de unidades al final de la línea (a la izquierda del "*" más a la derecha). Luego cambiamos todo "a" hasta el signo de multiplicación "x" de nuevo a unidades. Y el ciclo se repite. De hecho, después de todo, A multiplicado por B se puede representar como A + A + A B veces. Ahora marcamos la 2da unidad del 2do multiplicador con la letra "a" y nuevamente transferimos las unidades. Cuando no hay unidades antes del signo “=”, entonces la multiplicación está completa.
Completitud de Turing
Podemos decir que la máquina de Turing es la computadora de memoria lineal más simple que, de acuerdo con reglas formales, transforma los datos de entrada utilizando una secuencia de acciones elementales .
La elementalidad de las acciones es que la acción cambia solo una pequeña parte de los datos en la memoria (en el caso de una máquina de Turing, solo una celda), y el número de acciones posibles es finito. A pesar de la simplicidad de la máquina de Turing, en ella se puede calcular todo lo que se puede calcular en cualquier otra máquina que realice cálculos utilizando una secuencia de operaciones elementales. Esta propiedad se llama completitud .
Una forma natural de demostrar que los algoritmos computacionales que se pueden implementar en una máquina se pueden implementar en otra es simular la primera máquina en la segunda.
La imitación es la siguiente. La descripción del programa (reglas de funcionamiento) de la primera máquina y los datos de entrada que deberían haberse recibido en la entrada de la primera máquina se alimentan a la entrada de la segunda máquina. Es necesario describir dicho programa (las reglas de funcionamiento de la segunda máquina) para que, como resultado de los cálculos, la salida sea la misma que devolvería la primera máquina si recibiera datos .
Como se dijo, en una máquina de Turing es posible imitar (estableciendo las reglas de transición) todos los demás ejecutores que de alguna manera implementan el proceso de cálculo paso a paso, en el que cada paso del cálculo es bastante elemental.
En una máquina de Turing, puede simular una máquina Post , algoritmos normales de Markov y cualquier programa para computadoras ordinarias que convierta datos de entrada en salida de acuerdo con algún algoritmo. A su vez, en varios ejecutores abstractos es posible imitar la Máquina de Turing. Los ejecutores para los que esto es posible se denominan Turing completo.
Existen programas para ordenadores convencionales que imitan el funcionamiento de una máquina de Turing. Pero esta simulación es incompleta, ya que la máquina de Turing tiene una cinta infinita abstracta. Una cinta de datos infinita no se puede simular completamente en una computadora con una memoria finita: la memoria total de la computadora (RAM, discos duros, varios medios de almacenamiento externo, registros del procesador y caché, etc.) puede ser muy grande, pero siempre es finita. . El límite teórico de la cantidad de información que puede haber dentro de una superficie dada es, hasta un factor, igual a la entropía de un agujero negro con la misma área de superficie.
Variantes de la máquina de Turing
El modelo de la máquina de Turing permite extensiones. Se pueden considerar máquinas de Turing con un número arbitrario de cintas y cintas multidimensionales con diferentes restricciones. Sin embargo, todas estas máquinas son Turing completas y están modeladas por una máquina de Turing normal.
Una máquina de Turing que se ejecuta en una cinta semi-infinita
Como ejemplo de tal reducción, considere el siguiente teorema: para cualquier máquina de Turing, hay una máquina de Turing equivalente que funciona en una cinta semi-infinita (es decir, una cinta que es infinita en una dirección).
Considere la prueba dada por Yu.G. Karpov en el libro Theory of Automata. La demostración de este teorema es constructiva, es decir, daremos un algoritmo mediante el cual, para cualquier máquina de Turing, se puede construir una máquina de Turing equivalente con una propiedad declarada. Primero, numeramos arbitrariamente las celdas de la cinta de trabajo de MT, es decir, determinamos la nueva ubicación de la información en la cinta:
Luego renumeramos las celdas y supondremos que el símbolo "*" no está contenido en el diccionario MT:
Finalmente, cambiamos la máquina de Turing duplicando su número de estados y cambiamos el desplazamiento de la cabeza de lectura y escritura para que en un grupo de estados la operación de la máquina sea equivalente a su operación en la zona sombreada, y en el otro grupo de estados la máquina funciona como lo hace la máquina original en el área no sombreada. Si se encuentra el símbolo '*' durante la operación MT, entonces el cabezal de lectura y escritura ha alcanzado el límite de la zona:
El estado inicial de una nueva máquina de Turing se establece en una zona u otra, según en qué parte de la cinta original se encontraba el cabezal de lectura y escritura en la configuración original. Obviamente, a la izquierda de los marcadores de límite "*" la cinta no se usa en la máquina de Turing equivalente.
Máquinas de Turing bidimensionales
Véase también
- Programa multiplataforma JFLAP : simulador de autómatas, máquinas de Turing, gramática, dibuja gráficos de autómatas
- Máquina de Turing Universal
- Máquina de Turing no determinista
- Máquina de Turing probabilística
- máquina cuántica de turing
- Teoría de Algoritmos
- atolladero de turing
- diagrama de turing
- el coche de Minsky
Otros implementadores abstractos y sistemas informáticos formales
- Algoritmo normal de Markov ( programación de producción )
- Máquina de correos ( programación automática )
- Función recursiva (teoría de la computabilidad)
- Cálculo lambda ( programación funcional )
- Brainfuck ( programación imperativa )
Notas
- ↑ Nefiodov, 1992 , pág. 97.
- ↑ Nefiodov, 1992 , pág. 94.
- ↑ Ebbinhouse, 1972 , pág. 24
Literatura
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Capítulo 8. Introducción a la teoría de la máquina de Turing // Introducción a la teoría de autómatas, lenguajes y computación. - M. : Williams , 2002. - 528 p. - ISBN 0-201-44124-1 .
- Karpov Yu. G. Teoría de los autómatas. - Pedro, 2003. - ISBN 5-318-00537-3 .
- Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Máquinas de Turing y funciones recursivas. — M .: Mir, 1972. — 262 p.
- Nefedov V. N., Osipova V. A. Curso de matemáticas discretas. — M. : MAI, 1992. — 260 p.
Enlaces
- Máquina de Turing // Conferencia de Alexander Shen en el proyecto PostNauka (06/04/2013)
| Lenguajes formales y gramáticas formales | |
|---|---|
| Conceptos generales | |
| tipo 0 | |
| Tipo 1 |
|
| Tipo 2 | |
| Tipo 3 |
|
| analizando | |
 diccionarios y enciclopedias | ||||
|---|---|---|---|---|
| ||||