| En el estado | Lee | Escribe | Se mueve | Estado siguiente |
|---|
Simulador de máquina de Turing
Una máquina de Turing es el ordenador más sencillo posible: un cabezal que lee un símbolo de una cinta infinita, escribe un símbolo, se mueve una celda a la izquierda o a la derecha y cambia de estado, siguiendo una breve tabla de reglas. Alan Turing la inventó en 1936, y todo lo que hace tu ordenador podría hacerse, en principio, de esta manera. Escribe tus propias reglas o carga un ejemplo, pulsa Ejecutar y observa cómo cambia la cinta paso a paso, con un diagrama de toda su historia debajo. Elige un programa o escribe el tuyo, introduce la entrada y pulsa Ejecutar, o Paso para seguir una regla cada vez; Atrás deshace un paso. Cada línea del programa es una regla: estado, símbolo leído, símbolo que se escribe, movimiento (L, R o N para no moverse) y estado siguiente, por ejemplo A 0 -> 1 R B. Usa _ para una celda en blanco. La máquina empieza en el estado de la primera regla, sobre el primer símbolo de la entrada, y se detiene en H, accept o reject, o cuando ninguna regla encaja. El diagrama muestra la cinta después de cada paso, de arriba abajo.
Cómo funciona
- Elige un programa de ejemplo o escribe reglas como A 0 -> 1 R B, una por línea, y teclea la entrada.
- Pulsa Ejecutar para ver moverse el cabezal, o Paso para seguir una regla cada vez; Atrás deshace un paso.
- Consulta el estado, los pasos y los símbolos en la cinta en las fichas, y la historia de la cinta en el diagrama.
Cómo funciona la máquina
En cada momento, la máquina está en uno de unos pocos estados y su cabezal está sobre una celda de la cinta. La regla para ese estado y el símbolo bajo el cabezal dice tres cosas: qué símbolo escribir en la celda, si moverse a la izquierda, a la derecha o no moverse, y a qué estado pasar después. Esa es toda la máquina. Se detiene cuando llega a un estado de parada, como H, accept o reject, o cuando ninguna regla encaja. Un programa que suma 1 a un número binario solo necesita nueve reglas así.
Castores afanosos
¿Qué máquina con n estados, puesta en marcha sobre una cinta en blanco, escribe la mayor cantidad de unos antes de detenerse? Tibor Radó lo preguntó en 1962. Las campeonas se llaman castores afanosos, y crecen más rápido que cualquier función que un ordenador pueda calcular. Dos estados dan 4 unos en 6 pasos, tres estados 6 unos, cuatro estados 13 unos en 107 pasos. La campeona de cinco estados, hallada en 1989, escribe 4.098 unos en 47.176.870 pasos, y en 2024 una colaboración en línea demostró con matemáticas verificadas por ordenador que ninguna otra máquina de cinco estados que se detenga funciona durante más tiempo.
Preguntas frecuentes
¿Cómo escribo una regla?
Una regla por línea: el estado actual, el símbolo que lee, el símbolo que escribe, el movimiento (L, R o N) y el estado siguiente, por ejemplo A 0 -> 1 R B. La flecha y las comas son opcionales. Usa _ para una celda en blanco y # para un comentario. La máquina empieza en el estado de la primera regla; un estado siguiente llamado H o halt la detiene, y accept y reject la detienen con un veredicto.
¿De verdad puede una máquina de Turing calcularlo todo?
Todo lo que cualquier ordenador pueda calcular, con suficiente cinta y tiempo: esa es la tesis de Church-Turing. Una máquina de Turing no tiene límite de memoria, así que en ese sentido es más potente que cualquier ordenador real, aunque mucho más lenta. Lo que no puede hacer es responder a todas las preguntas: Turing demostró que ninguna máquina puede decidir, para todo programa y toda entrada, si se detendrá.
¿Por qué el contador nunca se detiene?
Sus reglas nunca llevan a un estado de parada. Sigue sumando 1 a un número binario en el extremo derecho de la cinta y volviendo atrás, así que el número crece para siempre. El problema de la parada de Turing dice que ningún método general puede saber, para toda máquina, si se detendrá; en este contador sencillo se ve, pero en algunas máquinas de solo seis estados nadie lo sabe todavía.
¿Cómo puede el castor afanoso de cinco estados dar aquí 47 millones de pasos?
La cinta se guarda como un array compacto que crece en ambas direcciones, y en el ajuste Muy rápida la aplicación ejecuta cientos de miles de pasos entre actualizaciones de la pantalla, así que la ejecución completa tarda unos segundos en un navegador moderno. El diagrama registra solo los primeros 400 pasos, porque una imagen de 47 millones de filas no cabría en ninguna pantalla.
¿Se envía algo a un servidor?
No. El programa se ejecuta en tu navegador, y tu programa y tu entrada se quedan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor