F | | P(T) R P(u) R P(r) R P(i) R P(n) R P(g) R P( ) R P(M) R P(a) R P(c) R P(h) R P(i) R P(n) R P(e) R P(s) R -> B B | | L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) -> F

Translations: English, Spanish

En 1928, David Hilbert, uno de los matemáticos más influyentes de su época, se preguntó si era posible crear un algoritmo que pudiera determinar la corrección de un enunciado matemático. Este problema se denominó «problema de decisión», o «Entscheidungsproblem» en el alemán nativo de Hilbert. En 1936, tanto Alan Turing como Alonzo Church llegaron independientemente a la conclusión, utilizando métodos diferentes, de que la respuesta es «no».

La forma en que Turing lo hizo fue imaginar una «máquina universal», una máquina que pudiera computar cualquier cosa que pudiera ser computada. Esta idea, la «máquina de Turing» como la bautizó Alonzo Church en 1937, sentó las bases del dispositivo que estás utilizando para leer este post. Si nos fijamos bien, podemos ver el legado de Turing en las Unidades Centrales de Procesamieto (Central Processing Unit, CPU, por sus siglas en inglés) actuales.

Al final de este post, sabrás:

• Qué es una máquina de Turing.
• Qué se puede y qué no se puede computar.
• Qué significa ser una máquina de Turing completa.
• Cómo se relacionan las computadoras modernas con las máquinas de Turing.
• Cómo escribir y ejecutar tus propios programas para una máquina de Turing.

# ¿Qué es una máquina de Turing?

Cabría esperar que una máquina universal, capaz de calcular cualquier cosa que pueda computarse, fuera un dispositivo complejo. Nada más lejos de la realidad. La máquina sólo tiene 4 partes, y el lenguaje utilizado para programarla sólo tiene 5 instrucciones.

Las partes son: una !cinta, un !cabezal, un !programa y un !estado. Cuando estés listx, sigue adelante y pulsa !play.

Lo que estás viendo aquí es un programa que ejecuta P(0) para imprimir 0 en la cinta, mueve la cabeza a la derecha con la instrucción R, y luego ︎!salta de nuevo al inicio. Seguirá imprimiendo 0s para siempre.

En cualquier momento, siéntete libre de !pausar, mover la máquina hacia !adelante o hacia !atrás una instrucción cada vez, o !reiniciar el programa desde el principio. También hay un selector de velocidad en el extremo derecho de los controles si deseas acelerar la máquina.

Observa que el !estado y el !valor nunca cambian. Cada vez que la máquina realiza un !salto, el estado actual y el valor se utilizan para elegir la siguiente fila correcta de instrucciones a ejecutar. Este programa sólo tiene un único estado, iniciar, y cada vez que salta, el símbolo bajo la !cabeza es ︎en !blanco.

Veamos un programa con múltiples estados.

Este programa imprime alternativamente 0s y 1s en la cinta. Tiene 2 estados, cero y uno, para ilustrar lo que ocurre cuando ︎!salta a un estado diferente.

También puedes conseguir este mismo resultado utilizando un único !estado y alternando el !valor. He aquí un ejemplo de ello:

La columna de !valor siempre se mantiene al día con lo que el símbolo actual está bajo la !cabeza, entonces cuando nosotres !salta ese valor se utiliza para saber qué fila de instrucciones debe ejecutar. La combinación de estado y valor nos da una sorprendente nivel de control sobre lo que hace nuestro !programa.

Hasta ahora hemos visto 3 instrucciones:

• P imprime un símbolo dado en la cinta.
• R mueve la cabeza de la cinta a la derecha.
• ↪︎ salta a un estado dado.

Hay 2 más:

• L mueve la cabeza de la cinta a la izquierda.
• H detiene la máquina.

Este programa imprime la palabra "Alan" de derecha a izquierda y luego se detiene. Si no puedes ver la palabra completa, puedes arrastrar la cinta de izquierda a derecha. Si la máquina se ha parado, puedes utilizar !reiniciar para arrancarla de nuevo desde el principio.

¡Todo! Probablemente no consigas que el videojuego Crysis funcione a 60 cuadros por segundo en una máquina de Turing simulada, pero todos los cálculos necesarios para renderizar cada fotograma se pueden hacer con sólo estas 5 instrucciones. Todo lo que alguna vez hayas visto hacer a una computadora puede hacerse con una máquina de Turing. Veremos cómo puede funcionar en la práctica un poco más adelante.

El último ejemplo que quiero mostrarte antes de continuar es el primer programa que Alan Turing mostró al mundo. Es el primer programa que aparece en su artículo de 1936: "Sobre Números Computables, con una aplicación al Entsheidungsproblem".

A Turing le gustaba dejar espacios entre símbolos, llegando incluso a definirlos como "cuadrados F" y "cuadrados E". F de figura, y E de borrable (la “E” proviene del inglés “erasable”). Sus algoritmos a menudo hacían uso de cuadrados E para ayudar a la máquina a recordar la ubicación de cuadrados de !cinta específicos.

# ¿Qué significa «computable»?

Se dice que algo es "computable" si existe un algoritmo que puede llegar desde la entrada dada hasta la salida esperada. Por ejemplo, sumar 2 enteros es computable. Aquí estoy dando a la máquina una cinta que comienza con los valores 2 y 6 en binario separados por un en !blanco.

b2 | 0 | R -> b2
b2 | 1 | R -> b2
b2 |   | L -> dec

dec | 0 | P(1) L -> dec
dec | 1 | P(0) L -> b3
dec |   | H

b3 | 0 | L -> b3
b3 | 1 | L -> b3
b3 |   | L -> inc

inc | 0 | P(1) R -> b1
inc | 1 | P(0) L -> inc
inc |   | P(1) R -> b1

Este programa suma los dos números, llegando a la respuesta 8. Lo hace decrementando desde el número de la derecha e incrementando el número de la izquierda hasta que el número de la derecha es 0. Aquí está el propósito de cada estado:

• b1 Muévete a la derecha hasta encontrar el primer cuadrado en !blanco. Esto es para navegar más allá del primer número.
• b2 Mover a la derecha hasta encontrar el segundo cuadrado en !blanco. Esto es para navegar más allá del segundo número.
• dec Disminuye el número actual en 1. En la práctica esto siempre será el número correcto. Decrementa volteando bits hasta que o bien llega a un 1, donde navegará de nuevo al número de la izquierda, o a un en !blanco, que interpretará como que el número ha llegado a 0.
• b3 Mover a la izquierda hasta el primer cuadrado !blanco de nuevo. Esto sólo se usa siempre después de que hayamos decrementado el número que está más a la derecha. No podemos reutilizar el estado b1 aquí porque cuando alcancemos el en !blanco, queremos saltar a inc.
• inc Incrementa el número actual en 1. Similar a decrementar, esto sólo ocurrirá en el número que esté más a la izquierda en la práctica. Esto se hace volteando bits hasta que llegamos a un 0, momento en el que navegamos de nuevo al número de la derecha.

Que podamos escribir este programa es una prueba de que la suma es computable, pero también implica que todos los números enteros son computables. Si podemos sumar 2 números enteros cualesquiera, podemos calcular cualquier otro número entero. 1 es 0+1, 2 es 1+1, 3 es 2+1, y así sucesivamente.

Es difícil escribir el equivalente de if (rightNum === 0) break; en una máquina de Turing, así que este programa lo hace como parte del proceso de decremento. Si, mientras decrementa, llega a un cuadrado en !blanco, interpreta que el número ha llegado a 0 y se detiene.

# Binario vs Decimal

Te habrás preguntado por qué elijo trabajar con números binarios en lugar de decimales. No es sólo porque así es como funcionan las computadoras modernas. Te voy a mostrar 2 ejemplos, y a partir de ellos podrás ver por qué las computadoras modernas eligen trabajar en binario.

El primer ejemplo es un programa que incrementa un número binario en un bucle sin fin.

El segundo ejemplo es un programa que incrementa un número decimal en un bucle sin fin.

Estos dos programas están haciendo lo mismo, pero el programa para manipular números decimales es mucho más largo. Incluso hemos introducido una nueva sintaxis, el símbolo *, para manejar un !valor bajo la cabeza que no coincide con ninguno de los otros valores para ese !estado. Por esta razón, cuando programamos máquinas de Turing preferimos los números binarios: los programas acaban siendo más cortos y más fáciles de razonar.

Esta ventaja también se traslada al mundo físico. Los componentes que conmutan entre dos estados son más baratos, pequeños y fiables que los que conmutan entre diez. Era más práctico construir computadoras que funcionaran en binario que computadoras que funcionaran en decimal, aunque se hicieron intentos de construir computadoras decimales.

# ¿Qué no se puede calcular?

Para abordar esta pregunta necesitamos explicar el "Problema de Halting" (Problema de la Detención en español). Es así:

Dado un programa y alguna entrada, ¿es posible escribir un segundo programa que nos diga con certeza si el primer programa se detendrá o se ejecutará para siempre?

La respuesta es no, y esto es lo que Turing esencialmente demostró. La prueba es complicada y no me avergüenza admitir que no la entiendo, pero hay un ejemplo que puedo darte y que se puede entender intuitivamente como "indecidible".

Imagina que escribes un programa que toma como entrada el programa que se utiliza para decidir si se detiene o no. Lo que hace entonces es ejecutar el programa que decide sobre sí mismo, y luego hacer lo contrario de lo que dice el programa que decide.

function undecidable(willHalt) {
  if (willHalt(undecidable)) {
    while (true);
  } else {
    return true;
  }
}

Este programa entra intencionadamente en un bucle infinito si se le dice que se detendrá, y se detiene si se le dice que se ejecutará para siempre. Parece un ejemplo tonto, el tipo de respuesta con la que un pícaro estudiante de secundaria podría intentar salirse con la suya, pero es un contraejemplo legítimo a la idea de que el problema de detención puede resolverse.

Si imagináramos codificar el programa y la entrada en algo que pudiera representarse en la cinta, no habría ningún programa que pudiera determinar si el programa se detendría o no. Imaginar esta codificación se vuelve bastante natural cuando te das cuenta de que los programas modernos se codifican como datos binarios que se guardan en el disco.

# ¿Qué significa ser Turing completo?

Si has estado involucrade en el mundo de la programación durante más de unos pocos años, es muy probable que te hayas topado con el término "Turing completo (o Turing Complete en inglés)". Muy probablemente en el contexto de cosas que realmente no deberían ser Turing completas, como las plantillas de C++, el sistema de tipos de TypeScript o Microsoft Excel.

Pero, ¿qué significa?

Al igual que el problema de Halting, la prueba es complicada, pero hay una prueba directa que se puede aplicar a algo para juzgar si es que es Turing completo, o no.

Un sistema es Turing completo si puede utilizarse para simular una máquina de Turing.

He escrito este post, con las simulaciones de la máquina de Turing, en el lenguaje de programación JavaScript. Por lo tanto JavaScript es Turing completo. El ejemplo de plantillas de C++ dado anteriormente simula una máquina de Turing en el sistema de plantillas de C++. El ejemplo de TypeScript toma la ruta de escribir un intérprete para un lenguaje Turing completo diferente.

Tienes razón, y todo el mundo tiende a hacer un poco de trampa con la definición. Cuando alguien dice que algo es Turing completo, lo que quiere decir es que sería Turing completo si tuviera una cantidad infinita de memoria. La limitación de cinta infinita significa que ninguna máquina de Turing podría existir nunca en nuestra realidad física, así que se tiende a renunciar a ese requisito.

# ¿Cómo se relaciona todo esto con los computadoras modernas?

Si lees sobre el tema de las máquinas de Turing fuera de este post, puede que veas que se dice que las computadoras modernas son efectivamente máquinas de Turing. Se te perdonaría que te resultara difícil imaginar cómo se pasa de sumar 2 enteros en binario en una cinta a ejecutar un navegador web, pero la línea está ahí.

Una diferencia clave entre nuestra máquina de Turing y el dispositivo en el que estás leyendo esto es que la CPU de tu dispositivo tiene "registros". Estos son pequeños trozos de memoria que viven directamente en la CPU y se utilizan para almacenar valores temporalmente mientras se está operando con ellos. Los valores se cargan constantemente de la memoria a los registros y se guardan de nuevo. Puedes pensar en los registros como variables para tu CPU, pero sólo pueden almacenar números de tamaño fijo.

Podemos crear registros en nuestra máquina de Turing. Podemos hacerlo creando un "formato" para nuestra cinta.

Aquí definimos 3 registros: A, B y C. Cada registro contiene 3 bits y puede almacenar números entre 0 y 7. En el extremo izquierdo tenemos una H, que significa "home", que nos ayudará a navegar.

Para incrementar el registro C, podemos escribir un programa como este:

Estamos haciendo un uso mucho más libre del símbolo * aquí para ayudarnos a navegar a partes específicas de la !cinta sin tener que enumerar todos los valores posibles que podrían estar bajo la !cabeza en el camino hacia allí.

Este programa es efectivamente equivalente al siguiente código ensamblador x86, si x86 tuviera un registro llamado c:

mov c, 0 ; Carga 0 en c
inc c    ; Incrementa c en 1

Si quisiéramos sumar valores en A y B, almacenando el resultado en C, necesitaríamos hacer más trabajo. Aquí está el código ensamblador que intentamos replicar:

mov a, 2 ; Carga 2 en a
mov b, 3 ; Carga 3 en b
add c, a ; Suma a a c
add c, b ; Suma b a c

Antes de que te desplaces hacia abajo te advertiré que el programa es largo y complejo. Es el último programa que veremos en este post, y no espero que lo entiendas en su totalidad para continuar hasta el final. Su propósito principal es mostrarte que podemos implementar operaciones vistas en código ensamblador moderno en una máquina de Turing.

iniciar | * | L -> iniciar
iniciar | H | R -> go_a

go_a | * | R -> go_a
go_a | A | R R R -> dec_a

dec_a  | 0 | P(1) L -> cry_a
dec_a  | 1 | P(0) -> go_c1

cry_a | 0 | P(1) L -> cry_a
cry_a | 1 | P(0) -> go_c1
cry_a | * | R P(0) R P(0) R P(0) -> goto_b

go_c1 | * | R -> go_c1
go_c1 | C | R R R -> inc_c1

inc_c1 | 0 | P(1) -> h2a
inc_c1 | 1 | P(0) L -> cry_ca

cry_ca | 0 | P(1) -> h2a
cry_ca | 1 | P(0) L -> cry_ca
cry_ca | * | R -> h2a

h2a | * | L -> h2a
h2a | H | R -> go_a

goto_b | * | R -> goto_b
goto_b | B | R R R -> dec_b

dec_b | 0 | P(1) L -> dec_bc
dec_b | 1 | P(0) -> go_c2

dec_bc | 0 | P(1) L -> dec_bc
dec_bc | 1 | P(0) -> go_c2
dec_bc | * | R P(0) R P(0) R P(0) -> end

go_c2 | * | R -> go_c2
go_c2 | C | R R R -> inc_c2

inc_c2 | 0 | P(1) -> go_hb
inc_c2 | 1 | P(0) L -> cry_cb

cry_cb | 0 | P(1) -> go_hb
cry_cb | 1 | P(0) L -> cry_cb
cry_cb | * | R -> go_hb

go_hb | * | L -> go_hb
go_hb | H | R -> goto_b

end | * | L -> end
end | H | H

Esto es dolorosamente laborioso, y ni siquiera coincide exactamente con el código ensamblador. Destruye los valores en A y B a medida que los suma, y no maneja el desbordamiento. Pero es un comienzo, y espero que te dé una idea de cómo se puede construir esta máquina teórica para que funcione como una CPU moderna.

Si observas cómo se ejecuta el programa hasta su finalización, algo que puede llamarte la atención es cuánto trabajo se necesita para hacer algo tan simple como sumar dos números. Las máquinas de Turing no fueron diseñadas para ser prácticas, Turing nunca pretendió que nadie saliera a construir una de estas máquinas con la esperanza de que fuera útil.

Las máquinas modernas tienen circuitos que pueden sumar dos números haciendo pasar dos señales eléctricas y obteniendo la suma como una única señal. Esto ocurre en menos de un nanosegundo. Las máquinas modernas tienen una memoria a la que se puede acceder a cualquier byte en cualquier momento, sin necesidad de manipular la cinta. Este acceso a la memoria tarda unas decenas de nanosegundos.

# Escribir y ejecutar tus propios programas

He construido un entorno de desarrollo basado en web para escribir programas que se ejecutarán en las visualizaciones de la máquina de Turing que has visto a lo largo del post.

Puedes acceder al editor aquí.

Te animo a que juegues con él. Ponte un objetivo sencillo, como sumar 2 números sin volver a mirar cómo lo hice en el post. Es una buena forma de hacerte una idea de cómo funciona la máquina.

# Conclusión

Para recapitular, hemos cubierto:

• Qué es una máquina de Turing.
• Qué se puede y qué no se puede calcular.
• Qué significa ser una máquina de Turing completa.
• Cómo se relacionan las computadoras modernas con las máquinas de Turing.

Y ahora tienes acceso a un entorno para escribir y ejecutar tus propios programas de máquinas de Turing. Si lo usas para hacer algo bueno, ¡por favor, ponte en contacto conmigo y enséñamelo! Mi dirección de correo electrónico es hello@samwho.dev.

# Lectura adicional

• El artículo original de Turing sobre los números computables.
• The Annotated Turing Lo he consultado durante la elaboración de este artículo. Es una lectura fabulosa, muy recomendable.
• Alan Turing: The Enigma, de Andrew Hodges. Una excelente biografía de Turing, que leí mientras escribía este post.
• Calculating a Mandelbrot Set using a Turing Machine. Esto me resultó excepcionalmente útil para entender cómo se pasa de las máquinas de Turing a los computadoras modernas.

# Agradecimientos

Estos posts nunca son un esfuerzo en solitario, y éste no es una excepción. Mi más sincero agradecimiento a las siguientes personas:

• A mi mujer, Sophie, que dibujó los esbozos biográficos que ves al final, y por aguantar mis incesantes charlas sobre este post las últimas 2 semanas.
• A todos los que me permitieron verles leer este post en tiempo real a través de una videollamada y me dieron su opinión: Jaga Santagostino, Robert Aboukhalil, Tarun Verghis, Tyler Sparks.
• Todos los que vinieron a pasar el rato y ayudar en las transmisiones de Twitch cuando estaba construyendo las primeras versiones de las visualizaciones de la máquina de Turing.
• Todos los que apoyan mi trabajo en Patreon.
• Todos los que trabajan en las herramientas utilizadas para construir este post: TypeScript, Bun, Two.js, Tween.js, Monaco, Peggy, Zed, y muchas otras dependencias indirectas. Realmente estamos a hombros de gigantes.
• Cristián Rojo por ayudarme a traducir el post al español.