Puntos extras

¿Que son las maquinas Turing y cómo funcionan?

Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en casillas. Sobre esta cinta hay un dispositivo capaz de desplazarse a lo largo de ella a razón de una casilla cada vez. Este dispositivo cuenta con un cabezal capaz de leer un símbolo escrito en la cinta, o de borrar el existente e imprimir uno nuevo en su lugar. Por último, contiene además un registro capaz de almacenar un estado cualquiera, el cual viene definido por un símbolo. Los símbolos que definen el estado del dispositivo no tienen por que coincidir con los símbolos que se pueden leer o escribir en la cinta.
En los programas presentados en el artículo, los posibles símbolos a leer o escribir en la cinta son el 0 y el 1, y los posibles estados se representan con letras mayúsculas. En el emulador, existe un cambio en la representación del estado, usando para ello los números del 0 al 99, para permitir un mayor número de ellos.

La máquina tiene un funcionamiento totalmente mecánico y secuencial. Lo que hace es leer el símbolo que hay en la casilla que tiene debajo. Después toma el símbolo del estado en que se encuentra. Con estos dos datos accede a una tabla, en la cual lee el símbolo que debe escribir en la cinta, el nuevo estado al que debe pasar y si debe desplazarse a la casilla izquierda o derecha.

Para comprender mejor, vamos a ver un simple ejemplo: sea la máquina de Turing capaz de leer o escribir los símbolos 0 y 1 en la cinta (en la definición original de Turing, el número de símbolos a usar podía ser cualquiera, con la única condición de ser un número finito, y no tenían por qué ser números; sin embargo, en aplicaciones prácticas se suelen limitar a estos dos), y que puede tener los estados A, B y C (una máquina de Turing puede tener cualquier número de estados; la única condición es que sea un número finito). Supongamos que definimos la siguiente tabla:
estado símbolo nuevo nuevo sentido de
inicial leído estado símbolo avance

A 0 B 1 DERECHA
A 1 B 0 IZQUIERDA
B 0 A 1 DERECHA
B 1 C 0 DERECHA
C 0 A 0 IZQUIERDA
C 1 C 0 DERECHA
La cual vamos a simplificar de la siguiente manera:
0 1

A B,1,> B,0,<

B A,1,> C,0,>

C A,0,< C,0,>
Hemos puesto los posibles estados en columna, y los posible símbolos en fila, y hemos expresado el nuevo estado, símbolo y sentido todo junto. El sentido lo expresamos con la dirección en la que apunta el símbolo < o >.
Vamos a poner nuestra máquina sobre esta cinta:

........cabezal.............
............v................
... 0 0 0 0 0 1 0 0 0 0 ...
Indicaremos el estado actual de la máquina encima del cabezal. Veamos los sucesivos pasos de esta máquina si partimos del estado A:

1).........A....................El estado es A y leemos un cero;
.............v....................luego debemos cambiar al estado B,
... 0 0 0 0 0 1 0 0 0 0 .......escribir un 1 y movernos a la derecha.

2)..........B..................El estado es B y leemos un cero;
............v..................luego debemos cambiar al estado A,
... 0 0 0 1 0 1 0 0 0 0 .......escribir un 1 y movernos a la derecha.

3)............A................El estado es A y leemos un uno;
..............v................luego debemos cambiar al estado B,
... 0 0 0 1 1 1 0 0 0 0 ... escribir un 0 y movernos a la izquierda.

4)..........B..................El estado es B y leemos un uno;
............v..................luego debemos cambiar al estado C,
... 0 0 0 1 1 0 0 0 0 0 .......escribir un 0 y movernos a la izquierda.

5)........C....................El estado es C y leemos un uno;
..........v....................luego debemos cambiar al estado C,
... 0 0 0 1 0 0 0 0 0 0 .......escribir un 0 y movernos a la derecha.

6)..........C..................El estado es C y leemos un cero;
............v..................luego debemos cambiar al estado A,
... 0 0 0 0 0 0 0 0 0 0 .......escribir un 0 y movernos a la izquierda.

7)........A....................El estado es A y leemos un cero;
..........v....................luego debemos cambiar al estado B,
... 0 0 0 0 0 0 0 0 0 0 .......escribir un 1 y movernos a la derecha.

La ejecución de esta máquina seguiría indefinidamente, rellenando la cinta con unos y ceros de una manera más o menos aleatoria. Realmente, una máquina de Turing útil debería poder detenerse; esto es, tener un estado en el que se detiene. Dicho estado se alcanzaría igual que cualquier otro estado. Esto es, supongamos que el estado D es el de paro; lo único que debemos hacer es que, cuando la máquina haya terminado el cálculo, pase a estado D; de este modo se detiene y permite examinar la cinta para buscar el resultado.

Vemos que esta máquina no hace gran cosa. Sin embargo, una máquina de Turing puede hacer cosas útiles, tales como sumar dos números, multiplicarlos, copiarlos, etc. Disponiendo de una máquina con el suficiente número de estados, podríamos hacer con ella cualquier operación que un ordenador normal pudiese realizar.

Las máquinas de Turing plantean una deducción bastante curiosa: dado que en ellas se puede realizar cualquier trabajo computable, es posible programarlas para que simulen el comportamiento de un potente ordenador. Y como una máquina de Turing puede ser codificada en cualquier ordenador, por pequeño que sea, sería posible (si disponemos de memoria suficiente, claro) emular en nuestro ordenador de casa una máquina de Turing que simule un superordenador.

Esto significa que todos los ordenadores pueden realizar exactamente el mismo tipo de tareas, y que los cálculos que pueda realizar el más grande los puede llevar a cabo también el más pequeño. La única diferencia sería, obviamente, la velocidad.