INTRODUCCIÓN

¿Qué es una máquina de Turing y cómo funciona?

La llamada “Máquina de Turing” es en realidad un modelo matemático consistente en un autómata que es capaz de “implementar cualquier problema matemático expresado a través de un algoritmo”. A pesar de esta definición tan complicada, en realidad la máquina de Turing destaca por su simplicidad pues manipula símbolos sobre una tira de cinta siguiendo una serie de reglas. A pesar de esta simplicidad, una máquina de Turing puede adaptarse para que simule la lógica de cualquier algoritmo de computador, de ahí su enorme potencial y valor.

Como su propio nombre indica, la máquina de Turing fue creada por el matemático inglés Alan Turing, un genio en muchos campos pero especialmente en la criptografía y la lógica. Originalmente la denominó “Máquina de Computación Lógica” siendo una de las mayores aportaciones pues despejó el camino de la ciencia de la Computación, de la Informática moderna.

Una Máquina de Turing consta de una cinta infinita dividida en espacios de trabajo o celdas yuxtapuestas que actúa como memoria, un cabezal capaz de leer y escribir símbolos en la cinta y moverla de celda en celda a derecha e izquierda, un registro de estado, y una tabla finita de instrucciones o tabla de acción.

La máquina de Turing es considerada un autómata con la capacidad de reconocer lenguajes formales de acuerdo a la jerarquía de Chomsky, razón por la cual es muy superior a otros autómatas como el autómata con pila o el autómata finito.

Existen diversos tipos de máquinas de Turing: con movimiento stay o “esperar”, con cinta infinita a ambos lados, con cinta multipista, multicinta, determinista y no determinista, la Máquina de Turing Cuántica. En resumen, una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT, ambos formados por un código binario de unos y ceros.