Máquina de Turing
Un algoritmo es un conjunto de pasos lógicos y secuenciales para solucionar un problema. Este concepto fue implementado en 1936 por Alan Turing, matemático inglés, en la llamada Máquina de Turing (MT).
La Máquina de Turing está formada por tres elementos: una cinta, una cabeza de lectura-escritura y un programa. La cinta tiene la propiedad de ser infinita (no acotada por sus extremos) y estar dividida en segmentos del mismo tamaño, los cuales pueden almacenar cualquier símbolo o estar vacíos. La cinta puede interpretarse como el dispositivo de almacenamiento.
La cabeza de lectura-escritura es el dispositivo que lee y escribe en la cinta. Tiene la propiedad de poder actuar en un segmento y ejecutar sólo una operación a la vez. También tiene un número finito de estados, que cambian de acuerdo a la entrada y a las instrucciones definidas en el programa que lo controla.
El último elemento, el programa, es un conjunto de instrucciones que controla los movimientos de la cabeza de lectura-escritura indicándole hacia dónde debe moverse y si debe escribir o leer en la celda donde se encuentre.
Actualmente, la Máquina de Turing es una de las principales abstracciones utilizadas en la teoría moderna de la computación, ya que auxilia en la definición de lo que una computadora puede o no puede hacer.
Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM
