Máquina de Turing

Turing no diseñó una máquina para construirla: la diseñó para poder demostrar que ciertos problemas no tienen solución. Para eso hacía falta un modelo tan simple que nadie pudiera discutirlo, y tan potente que no se le escapara ningún cómputo posible.

Tres piezas: cinta, cabezal y control

El modelo tiene tres piezas: una cinta infinita dividida en celdas, un cabezal que lee y escribe una celda por vez y se mueve un lugar a izquierda o derecha, y un conjunto finito de estados con una tabla de reglas.

Cada regla dice: estando en tal estado y leyendo tal símbolo, escribir esto, moverse para allá y pasar a tal estado. Nada más. La máquina se detiene cuando llega a un estado de aceptación o rechazo, y puede no detenerse nunca.

Qué agrega la cinta que el autómata no tenía

La diferencia con un autómata finito es la cinta: memoria ilimitada a la que se puede volver. Con eso ya se puede contar, comparar dos mitades de la entrada y simular estructuras arbitrarias.

Y la diferencia con un autómata de pila es el acceso: la pila sólo se toca por un extremo, la cinta se recorre en las dos direcciones. Ese cambio es lo que convierte un modelo restringido en uno que abarca todo lo computable.

Agregarle cosas no le da más poder

Lo notable es que agregarle cosas no le da más poder. Varias cintas, cinta infinita en las dos direcciones, un alfabeto más grande, no determinismo: todas esas variantes se simulan con la máquina básica, con una pérdida de eficiencia pero sin ganar capacidad.

El no determinismo es el caso más llamativo. Una máquina determinista puede simularlo explorando todos los caminos en anchura; tarda exponencialmente más, pero resuelve exactamente lo mismo. Esa robustez del modelo es lo que le da autoridad a sus resultados negativos.

La máquina universal: el programa como dato

La idea con más consecuencias es la máquina universal. Una máquina de Turing se puede codificar como una cadena, y entonces existe una máquina $U$ que recibe la descripción de otra máquina más su entrada, y simula su ejecución.

Eso es exactamente una computadora de programa almacenado: el programa es un dato. La misma codificación de máquinas como cadenas es lo que después habilita los argumentos diagonales, y con ellos las demostraciones de imposibilidad.

Decidible y reconocible no son lo mismo

Con este modelo se separan dos nociones que en la práctica se confunden. Un lenguaje es decidible si hay una máquina que siempre se detiene y responde bien. Es reconocible si hay una máquina que acepta las cadenas del lenguaje, pero sobre las que no pertenecen puede quedarse colgada para siempre.

Hay lenguajes reconocibles y no decidibles, y esa brecha es el corazón de la computabilidad: se puede confirmar un sí, nunca descartar con certeza.

Para qué sirve si nadie la programa

Nadie programa una máquina de Turing, y ese no es el punto. El punto es que si algo no se puede hacer en este modelo, no se puede hacer en ningún lenguaje ni con ningún hardware, porque todos se simulan mutuamente.

De ahí sale el término “Turing completo”, que se aplica a lenguajes de programación y a cosas que no pretendían serlo: las plantillas de C++, las hojas de cálculo, las reglas de algunos motores de configuración. Ser Turing completo también implica heredar la indecidibilidad: sobre esos sistemas no se puede decidir automáticamente si un cálculo termina.

Para qué sirve un modelo tan incómodo

Cierre

Cinta, cabezal y tabla de reglas: con eso alcanza para todo lo computable, y agregarle piezas no cambia lo que puede hacer. La máquina universal convierte programas en datos, y la distinción entre decidible y reconocible marca dónde empieza lo que no tiene solución.