Máquinas de Turing

La máquina de Turing, presentada por Alan Turing en 1936 en On computable numbers, with an application to the Entscheidungsproblems, es el modelo matemático de un dispositivo que se comporta como un autómata finito y que dispone de una cinta de longitud infinita en la que se pueden leer, escribir o borrar símbolos. Existen otras versiones con varias cintas, deterministas o no, etc., pero todas son equivalentes (respecto a los lenguajes que aceptan).

Dato Histórico:

• Alan Turing fue un brillante matemático, criptoanalista e informático teórico nacido el veintitrés de Junio de 1912 en Maida Vale un distrito residencial al oeste de Londres. Turing, además de ser un brillante científico era homosexual, razón por la que se presume perdió la vida el siete de junio de 1954.

Representación de la Máquina de Turing

Uno de los teoremas más importantes sobre las máquinas de Turing es que pueden simular el comportamiento de una computadora (almacenamiento y unidad de control). Por ello, si un problema no puede ser resuelto por una de estas máquinas, entonces tampoco puede ser resuelto por una computadora (problema indecidible, NP).

La notación de las máquinas de Turing es sencilla y exacta, por lo que es más cómodo trabajar con ellas a la hora de estudiar qué problemas son decidibles (P) y cuáles indecidibles (NP).

Por el momento la relación de inclusión entre P y NP está por demostrar, aunque sí sabemos que

P⊆NPP⊆NP

Definición de la Máquina de Turing

Máquina de Turing(MT), es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.

Llamamos Máquina de Turing (ó MT) a

M=(Q,Σ,T,δ,q₀,B,F)

donde

• Q es el conjunto finito de estados que denotaremos por q₀, q₁, q₂, ...
• Σ es el alfabeto: el conjunto finito de símbolos de entrada.
• Τ es el conjunto de símbolos de cinta. El alfabeto es un subconjunto de Τ.
• q₀ es el estado inicial: el estado en el que se encuentra inicialmente la MT.
• B es un elemento de Σ: el símbolo en blanco. Se encuentra en todas las casillas de la cinta que no tienen un símbolo de entrada.
• F es el conjunto de estados finales.
• δ es la función de transiciones.

La expresión δ(q,X)=(p,Y,D) indica que en el estado q, si la cabeza de la MT señala al símbolo de cinta X, entonces la MT escribe el símbolo de cinta Y en la casilla actual (cambia X por Y ) y mueve la cabeza una casilla en una dirección D (que puede ser derecha, R; o izquierda, L) y pasa al estado p. La cinta de la MT está formada por infinitas casillas.

Inicialmente, la palabra de entrada (una concatenación de símbolos del alfabeto) se encuentra escrita en casillas consecutivas de la cinta y la cabeza señala al primer símbolo de la palabra. Todas las otras casillas (hacia la izquierda y la derecha) contienen el símbolo en blanco.

Lenguaje de una Máquina de Turing

El lenguaje de una Máquina de Turing M=(Q,Σ,T,δ,q₀,B,F) es L(M):={w ∈ Σ^* : q₀w⊢∗ αpβ, p ∈ F, α, β ∈ T∗}

Es decir, las w de Σ^* tales que la máquina de Turing alcanza un estado de aceptación.

Ejemplo de una Máquina de Turing

Características de la máquina de Turing

Las principales características de la máquina de Turing son:

• 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 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.
• Está formada por un alfabeto de entrada y uno de salida y por un símbolo especial llamado blanco.

Usos de la máquina 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.

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. También en las máquinas “colossus” que descifraban los mensajes cifrados interceptados en las comunicaciones de los nazis.

Bibliografía

• (s.f.). Máquina de Turing: teoría de la computación: lenguaje, ejemplos y teoremas.. Recuperado 26 octubre, 2019, de https://www.matesfacil.com/automatas-lenguajes/Maquina-Turing.html
• Cursos y Master en Madrid - Formatalent. (s.f.). ¿Qué es una máquina de Turing y cómo funciona? | Formatalent. Recuperado 27 octubre, 2019, de http://formatalent.com/que-es-una-maquina-de-turing-y-como-funciona/
• (s.f.-e). Máquina de Turing - EcuRed. Recuperado 28 octubre, 2019, de https://www.ecured.cu/M%C3%A1quina_de_Turing
• Gabriela Briceño V, G. B. V. (2019, 15 agosto). Máquina de Turing | Qué es, características, historia, cómo funciona, usos. Recuperado 28 octubre, 2019, de https://www.euston96.com/maquina-de-turing/