Alan Turing introdujo el concepto de máquina de Turing en el trabajo On computable numbers, with an application to the Entscheidungsproblem, publicado por la Sociedad Matemática de Londres en 1936, en el que se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, Turing ideó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver.
Mediante este modelo teórico y el análisis de la complejidad de los algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones pueden encontrarse en tiempo polinómico por máquinas de Turing deterministas y no deterministas, respectivamente.
Definición
Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
Una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador.
Elementos de la máquina de Turing:
-
Unidad de control
Se puede percibir como una cabeza lectora/escritora que se encuentra en un estado específico.
-
Cinta:
Cinta infinita que puede dividirse en celdas. En estas se puede almacenar un solo símbolo específico en cada momento.
-
Mecanismo para mover la cinta:
Mueve la cinta un paso a la vez, ya sea a la derecha o la izquierda tomando en cuenta tanto el estado actual en la unidad de control como el símbolo en la posición actual en la que se encuentra sobre la cinta.
Una máquina de Turing con una sola cinta puede definirse como una 7-tupla
M = (Q, Σ, Τ, q0, B, F, δ.)
Donde:
-
Q: Conjunto finito de los estados de la unidad de control
-
Σ: Conjunto finito de los posibles símbolos de entrada
-
Γ: Conjunto finito de símbolos de cinta, Σ ⊆ Γ
-
q0: Es el estado en el que se inicia
-
B: Es el símbolo que representa el espacio en blanco
-
F: Es el subconjunto de Q que representa los estados finales o de aceptación.
-
δ(p, Y, S) : Función de transición que retorna el nuevo estado p; Y es el símbolo de Γ que se escribirá en la posición actual de la cinta, S el sentido o dirección en la que se moverá la unidad de control sobre la cinta
Características de las máquinas de Turing:
-
La entrada que tiene la cinta antes de que comience el cálculo debe consistir en un número finito de símbolos.
-
La cinta de la máquina tiene una de longitud ilimitada.
-
El cabezal de lectura y escritura puede ser programable.
-
La máquina de Turing es capaz de hacer seis tipos de operaciones fundamentales: leer, escribir, mover hacia la izquierda, mover hacia la derecha, cambiar de estado y detenerse.
-
Tiene la capacidad de computar cualquier cosa que cualquier computadora moderna pueda calcular.
Usos de las máquinas de Turing
La máquina de Turing ha sido, por ejemplo, utilizada como generadora de lenguajes, pues este tipo de máquina posee varias cintas incluyendo una cinta de salida que al inicio está vacía y luego se va llenando con palabras de lenguaje.
Es usada también en compiladores I y II, máquinas de estado, máquinas autómatas y generadores de códigos. Además, en la antigüedad fue utilizado en máquinas como la “Bombe” que era un dispositivo utilizado por los criptólogos británicos para poder descifrar señales cifradas por la máquina alemana “enigma” durante la Segunda Guerra Mundial.
Referencias
Briceño, G. (2019, 15 agosto). Máquina de Turing | Qué es, características, historia, cómo funciona, usos. Euston96. https://www.euston96.com/maquina-de-turing/
H. (2007). Teoria De Automatas, Lenguajesy Computacion (1.a ed.). PearsonEducación.
Oribe, J. (2010, 10 septiembre). ¿Qué es una Máquina de Turing? (i). El Máquina de Turing. https://elmaquinadeturing.wordpress.com/2009/12/15/%C2%BFque-es-una-maquina-de-turing-i/