La Máquina de Turing es un simple artefacto imaginario inventado por Alan Turing antes de que existieran las computadoras. La Máquina de Turing consiste básicamente de una cinta, una cabeza para lectura-escritura, y un programa.
La cinta es de largo infinito. Tiene una sola dimensión y está dividida en una secuencia de cuadros. Cada cuadro es capaz de retener cualquier símbolo ó estar en blanco. Aunque infinitamente larga la cinta de la Máquina de Turing contiene una cantidad finita de cuadros no en blanco. El resto de los cuadros se presumen en blanco. Obviamente, el número de cuadros que no está en blanco puede cambiar durante la ejecución de un programa. La Cinta es básicamente utilizada para registrar las entradas y las salidas.
La cabeza para lectura-escritura es un aparato que en un instante cualquiera está leyendo un cuadro de la cinta y obedeciendo una de las instrucciones del programa en un solo paso. Tiene un número finito de estados. Esta puede leer símbolos de la cinta, y basado en ese símbolo y su estado actual podría escribir otro símbolo sobre el símbolo leído, cambiar su estado y moverse a la izquierda ó a la derecha en la cinta. Inicialmente, el primer símbolo que sirve de entrada al programa está registrado en el primer cuadro a la izquierda de la cinta, e inicialmente la cabeza para lectura-escritura está posicionada sobre ese cuadro.
El programa es una secuencia finita de instrucciones. El programa le indica a la cabeza para lectura-escritura que escribir y como moverse, basado en el símbolo en la cintas, y los estados del programa. La Máquina de Turing normalmente obedece las instrucciones en el orden en que ocurren. Esta secuencia puede ser alterada por una instrucción que le requiera Saltar a otra posición. Cuando no hay una regla para la combinación de estado y símbolo que se encuentre la Máquina de Turing, la maquina se detiene y no se mueve más.
Esta simple máquina es tan poderosa que puede comprender todo aquello que conocemos como cómputos. Cuando es propiamente programada, una Máquina de Turing puede realizar cualquier operación realizable en una computadora contemporánea. Quizás no trabaja tan rápido como uno quisiera, pero es efectiva. ¡Funciona!
Última modificación : viernes 8 de agosto de 1997.
©Derechos Reservados - 1997 - Prof. H. D. A. Cabassa.