¿Qué es una máquina de Turing?

Una máquina de Turing es una idealización matemática de un agente finito capaz de calcular. El ingenio fue propuesto por Alan Turing en el año 1936, en un artículo titulado «On computable numbers, with an application to the Entscheidungsproblem», en el que se enfrentaba al problema planteado por David Hilbert sobre la decidibilidad de las matemáticas. En el artículo Turing introducía su máquina para demostrar que había problemas indemostrables para la máquina y que, por tanto, la matemática era indecidible. A continuación pasaremos a ver este ingenio con mayor profundidad.

Representación gráfica de una máquina de Turing

1. Descripción formal de la máquina de Turing

La máquina tiene una cinta infinita, dividida en cuadros, una cabeza que puede moverse a izquierda y derecha y borrar y escribir símbolos de una lista sobre la cinta y un conjunto de estados. Lo que la máquina hace se establece en la tabla de máquina. En efecto, allí se especifica, para un estado y un símbolo dados, lo que la máquina debe hacer (escribir o borrar un símbolo, por ejemplo) en el punto en el que se encuentra, y el estado siguiente. Una máquina de Turing es capaz de calcular todo aquello que pueda calcular un computador digital, siempre que pueda ser expresado mediante un algoritmo.

Si hemos de describir con mayor precisión una máquina de Turing, entonces hemos de decir que esta se compone de:

1. Una cinta de cálculo dividida en celdas consecutivas. En cada una de ellas hay un símbolo que pertenece a algún alfabeto finito. Este ha de contener un símbolo que recibe el nombre de «blanco» más uno o más símbolos extra. La cinta, como se ha mencionado, es infinita. Esto quiere decir que se puede extender tanto como se desee a izquierda y derecha. Se asume, desde el principio, que las celdas en als que no hay un símbolo escrito está el símbolo blanco, es decir, que una celda vacía y una celda con el símbolo blanco son exactamente iguales.

2. Un cabezal que lee, escribe y borra símbolos en las celdas de la cinta y que se mueve sobre la cinta (o mueve la cinta) a izquierda y derecha.

3. Un registro con los estados de la máquina. Esots son finitos. Dentro de estos estados hay uno especial. Se trata del estado inicial, que es el que inicia el registro de estados. Según Turing, estos estados simularían los estados mentales de una persona que está realizando cálculos.

4. Una tabla finita de instrucciones que le indican a la máquina lo que ha de hacer en función del estado en que se encuentre.

2. La máquina de Turing universal

Una máquina de Turing como la descrita más arriba solo puede realizar un programa para una función. Hay máquinas que pueden copiar números, otras pueden sumarlos, otras los restan, etc. Turing también ideó en su ensayo de 1936 una máquina de Turing capaz de imitar a cualquier otra máquina de Turing. Se trata de la máquina de Turing universal (U). Lo que hace la máquina de Turing universal es leer la descripción de la máquina particular que ha de simular junto con la entrada de su cinta de memoria.