Qué es una máquina de Turing
Una máquina de Turing es un modelo de computador con una cinta infinita, una cabeza que lee y escribe, y una tabla de reglas. Es la máquina más sencilla que puede calcular todo lo que calcula un ordenador.
Piensa en una libreta infinita con un lápiz. En cada paso miras una casilla, escribes algo y mueves el lápiz una casilla.
Al final de esta lección
Nota
Puedo seguir una máquina de Turing sobre una cinta paso a paso.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Cinta | una fila infinita de casillas con un símbolo cada una | |
| Cabeza | lee y escribe la casilla en la que está | |
| Regla | dado el estado y lo leído, qué escribir, hacia dónde ir y el estado nuevo | |
| Hueco | el símbolo de una casilla vacía | _ |
| Parada | la máquina termina porque llega a halt o no tiene regla | |
| Máquina de Turing | estados, cinta, cabeza y reglas |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Cada paso: mirar, escribir y mover
La cabeza lee el símbolo de su casilla. Con ese símbolo y el estado en que está, busca una regla en la tabla.
La regla dice tres cosas. Qué símbolo escribir. Si mover la cabeza a la derecha (R) o a la izquierda (L). Y a qué estado pasar. Si no hay regla, o el estado es halt, la máquina para. El resultado es lo que queda en la cinta.
Una máquina sencilla en Python
# Una máquina con tres estados implícitos: cambia cada a por una b.
cinta = list("aaba_")
cabeza = 0
estado = "buscar"
while estado != "fin":
simbolo = cinta[cabeza]
print(estado, cabeza, "".join(cinta))
if simbolo == "a":
cinta[cabeza] = "b"
cabeza = cabeza + 1
elif simbolo == "b":
cabeza = cabeza + 1
else:
# Un hueco en blanco: ya no queda texto.
estado = "fin"
print("Cinta final:", "".join(cinta))
# Cambia la cinta inicial por "baab_" y vuelve a ejecutar.
La tabla de reglas es el programa
Esta máquina suma uno a un número binario. Primero va hasta el final del número. Luego vuelve atrás: cada 1 pasa a 0 y se lleva uno, hasta encontrar un 0 o un hueco.
Cada fila de la tabla es una regla. No hay nada más: ni variables, ni bucles. Las reglas y la cinta lo hacen todo.
Reglas de la máquina que suma uno
| Estado | Lee | Escribe | Mueve | Estado nuevo |
|---|---|---|---|---|
| ir | 0 | 0 | R | ir |
| ir | 1 | 1 | R | ir |
| ir | hueco | hueco | L | llevar |
| llevar | 1 | 0 | L | llevar |
| llevar | 0 | 1 | R | halt |
| llevar | hueco | 1 | R | halt |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Ejemplo: sumar uno a 11
| Paso | Estado | Cabeza lee | Cinta después |
|---|---|---|---|
| 1 | ir | 1 | 11 |
| 2 | ir | 1 | 11 |
| 3 | ir | hueco | 11, la cabeza vuelve al último 1 |
| 4 | llevar | 1 | 01 |
| 5 | llevar | 1 | 00 |
| 6 | llevar | hueco | 100 y para en halt |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
El terminal hace lo mismo con una línea
Una máquina de Turing es lenta de escribir, pero cualquier otro programa se puede traducir a una. Los Runs hacen en una línea lo que la máquina hace paso a paso.
tr 01 10 cambia cada 0 por 1 y cada 1 por 0: es la máquina que invierte bits. Python suma uno a un número binario con int y bin.
Invierte los bits de 10110
echo 10110 | tr 01 10Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
El valor de 1011 en decimal
python3 -c "print(int('1011', 2))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Suma uno a 1011 en binario
python3 -c "print(bin(int('1011', 2) + 1)[2:])"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que una máquina de Turing es más débil que un ordenador, porque es tan simple. No lo es: calcula lo mismo. Solo es mucho más lenta y más incómoda. Es un modelo para pensar, no una máquina para comprar.
Para ir más lejos
Diseña la tabla de una máquina que reconoce una cinta de unos y la deja con un 1 más al final: de 111 a 1111.
Escribe sus reglas con el mismo formato que SUMAR_UNO y prueba tu simulador con ellas. Cuenta los pasos para 1, 11 y 111: ¿cómo crecen?