Máquina de Turing

La máquina de Turing es un dispositivo informático el cual consiste en un cabezal de lectura y escritura, lo que mejor conocemos hoy en día con el nombre de escáner y de una cinta de papel que atraviesa la máquina. Esta cinta se encontraba divida en cuadrados, y cada uno de ellos tenía al mismo tiempo un símbolo. Esta cinta era la encargada del almacenamiento de la máquina, y era una especie de vehículo de entrada y salida, además de funcionar como memoria de trabajo para almacenar los resultados de los pasos intermedios del cálculo.

• ¿Quién la invento? Alan Turing
• ¿En qué año? 1936

¿Qué es la máquina de Turing?

La máquina es un módulo de reconocimiento de lenguaje más general que cualquier autómata finito y de pila, pues tiene la capacidad de reconocer los lenguajes regulares y, los independientes de contexto, además de muchos otros tipos de lenguajes.

Características de la máquina de Turing

Las principales características de la máquina de Turing eran las siguientes:

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

Historia de la máquina de Turing

Alan Mathison Turing fue el inventor de la máquina de Turing. Fue conocido como un hombre extremadamente talentoso, que tuvo grandes influencias en el desarrollo de la informática y en la formalización del concepto de algoritmo y computación por medio de su máquina de Turing, la cual jugó un papel muy importante en la creación de la computadora moderna.

Turing la describió por primera vez en su artículo publicado en el año 1936 que trataba temas concernientes a los números computables. En su artículo, Turing imagina que su creación no es una máquina mecánica, sino más bien una persona a la que decidió llamar computadora, la cual ejecuta estas reglas mecánicas deterministas de manera descuidada.

Cómo funciona

La máquina de Turing funciona por medio de un control finito, una cabeza lectora y una cinta por en la cual puede haber diferentes caracteres, y en la cual se encuentra la palabra de entrada. Hacia el lado derecho la cinta tiene una longitud que es el lugar donde se llenan los espacios con el carácter blanco el cual es representado por la letra “t”. Hacia su lado izquierdo pasa lo contrario pues la cinta no es infinita razón por la cual hay un cuadro de la cinta que es el extremo izquierdo. Además, tiene una cabeza que se mueve hacia la izquierda y derecha, por lo que tiene la capacidad de pasar en ciclos repetidos sobre un mismo segmento de la cinta.

La máquina está conformada por un alfabeto de entrada y uno de salida, por un símbolo especial conocido con el nombre de blanco el cual normalmente se representa por medio de una b, Δ o 0, por un grupo de estados finitos y por un conjunto de transiciones entre estos estados.

Su funcionamiento se fundamenta en la transición, la cual se encarga de recibir un estado inicial y una cadena de caracteres los cuales pertenecen al alfabeto de entrada. A partir de ese momento la máquina empieza a leer una celda de la cinta, borrando el símbolo, y escribiendo el nuevo símbolo que pertenece al alfabeto de salida para luego avanza a la izquierda o a la derecha, un tiempo a la vez y repitiendo el proceso según se indique en la función de transición. Al final del proceso se detiene en un estado de aceptación, representando así la salida.

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.

Ejemplos

Algunos ejemplos de la máquina de Turing son:

• Una cadena de X seguida de una cadena de Y. Ambas de la misma longitud.
• {X^n Y^n, n>0}
• Estado inicial de la cinta: 000111#
• Transiciones:
  • 0 0 X r 1
  • 1 0 0 r 1
  • 1 Y Y r 1
  • 2 X X r 0
  • 3 Y Y r 3
  • 0 Y Y r 3
  • 1 1 Y l 2
  • 2 0 0 l 2
  • 2 Y Y l 2
  • 3 # # r 4
  • 4 * * r halt