Math
La máquina de Turing y los castores afanosos
Una cinta de papel entre dos carretes, un cabezal metálico con una lámpara de estado y una tabla de reglas. Cada paso se reproduce como leer, escribir, mover, nuevo estado; el diario de abajo guarda toda la ejecución, y una regla editada conserva la antigua como un fantasma. Los récords se hallan enumerando todas las máquinas, no se citan.
Qué ocurre
Una máquina tan pequeña es una tabla y nada más: para cada estado y símbolo, qué escribir, hacia dónde moverse, qué estado sigue - o parar. Sobre la mesa es un aparato: una cinta de papel entre dos carretes, un cabezal sobre rieles con una lámpara que muestra su estado. Cada paso se reproduce en cuatro fases - el cabezal lee la celda, estampa la nueva cifra, se desliza una celda, la lámpara cambia de color - y la hoja de abajo lleva el diario: cada paso de la ejecución como mapa de calor con eje de tiempo. Pulsa un paso para detener allí la máquina. Pulsa una ficha de la tabla para cambiar una regla: la ejecución anterior queda como un fantasma de vidrio junto a la nueva, con el paso en que las dos historias se separan. El castor afanoso pregunta cuánto puede correr una máquina así antes de parar. Los récords aquí no se citan: las 64 máquinas de un estado, las 20736 de dos y 1048576 de tres en forma normal se construyen y se ejecutan - tres estados dan a lo sumo 21 pasos y a lo sumo 6 unos, con dos máquinas distintas. Cuatro estados cuestan 268 millones de máquinas, así que ese campeón se toma como conocido y se comprueba ejecutándolo: 107 pasos, 13 unos. Una máquina que alcanza el tope de 400 pasos no ha parado, y nada en esta tarjeta puede decir si lo hará alguna vez.
Ecuaciones del módulo
Ecuaciones una máquina es una tabla: para cada (estado, símbolo) dice qué escribir, hacia dónde moverse (L o R) y qué estado viene a continuación - o H, parada la cinta empieza toda a ceros y no tiene límite; la ventana de la tarjeta contiene 49 celdas, suficientes para cada máquina que ejecuta S(n) - el mayor número de pasos que da una máquina que se detiene con n estados; Σ(n) - el mayor número de unos que deja alguna de ellas hallado aquí por enumeración, no citado: n = 1 son 64 máquinas, n = 2 son 20736, n = 3 son 16^5 = 1048576 en forma normal (primer movimiento 1RB) S(1) = 1, Σ(1) = 1; S(2) = 6, Σ(2) = 4; S(3) = 21, Σ(3) = 6 - y para n = 3 esas son dos máquinas DISTINTAS subir el tope de pasos de 25 a 200 no añade ni una sola máquina que se detenga: toda máquina de 3-estados que se detiene, lo hace como máximo en el paso 21 n = 4 costaría 16^7 = 268435456 máquinas, así que su campeona se toma como conocida y se comprueba ejecutándola: 107 pasos, 13 unos S(n) crece más deprisa que cualquier función computable - por eso la tabla de arriba se detiene en cuatro y no en diez
