Programas predefinidos
Configuración
qf
Tabla de reglas (transiciones)
| Estado | Lee | Escribe | Mueve | Nuevo estado | |
|---|---|---|---|---|---|
600 ms
Cinta
Estado:q0
Pasos ejecutados0
Celdas modificadas0
Movimientos del cabezal0
Cinta final (limpia)1011
Resultado: LISTA
Cinta, reglas y programas clásicos animados paso a paso. Aprende computabilidad de forma visual.
| Estado | Lee | Escribe | Mueve | Nuevo estado | |
|---|---|---|---|---|---|
Cómo funciona el modelo computacional universal
| Componente | Qué es | Ejemplo |
|---|---|---|
| Cinta | Memoria infinita en ambos sentidos, dividida en celdas que contienen un símbolo cada una | … _ _ 1 0 1 1 _ _ … |
| Cabezal | Apunta a una sola celda. Lee, escribe y se mueve una posición a la izquierda, derecha o se queda quieto | Triángulo naranja sobre la celda activa |
| Estados | Conjunto finito de configuraciones internas (q0, q1…). Hay un estado inicial y uno o varios estados finales | Q = { q0, q1, q2, qf } |
| Alfabeto | Conjunto finito de símbolos válidos en la cinta, incluido el símbolo blanco | { 0, 1, _ } |
| Función de transición δ | Para cada (estado, símbolo leído) define qué escribir, hacia dónde mover el cabezal y qué estado pasar | δ(q0, 1) = (1, R, q0) |
| Estados finales | Si la máquina llega a uno de ellos, la cadena se acepta. Si no hay regla aplicable y no es final, se rechaza | F = { qf } |
| Símbolo blanco | Marca celdas vacías. Por convención se representa como _ o con el símbolo ⊔ | _ |
Cursas Autómatas y Lenguajes Formales en grado de Informática y necesitas diseñar máquinas que reconozcan lenguajes como aⁿbⁿ o palíndromos para el examen.
Preparas oposiciones de informática (auxiliar, técnico, profesor de secundaria) donde aparecen preguntas teóricas sobre computabilidad y la tesis Church-Turing.
Quieres entender por qué Alan Turing es considerado el padre de la informática moderna y qué significa que un lenguaje sea "Turing-completo".
Enseñas la asignatura y necesitas un recurso visual para que el alumnado entienda transiciones, estados y la diferencia entre aceptar y rechazar una entrada.
Porque es el modelo teórico más simple capaz de capturar todo lo que es computable mecánicamente. Define los límites de la computación: si algo no puede hacerse en una máquina de Turing, no puede hacerse en ningún ordenador físico. Es la base de la teoría de la complejidad (clases P, NP, etc.).
Idea clave: una máquina de Turing es una abstracción matemática, no un dispositivo a fabricar.
Sostiene que todo problema que pueda resolverse mediante un algoritmo (en el sentido intuitivo) puede resolverse en una máquina de Turing. Es una tesis, no un teorema: no se puede demostrar formalmente porque requiere definir "algoritmo intuitivo", pero un siglo de evidencia la respalda.
En la determinista (la que simula esta app) cada par (estado, símbolo) tiene una sola transición posible. En la no determinista puede haber varias, y la máquina "adivina" el camino correcto. Ambas reconocen los mismos lenguajes (los recursivamente enumerables), pero la no determinista puede ser exponencialmente más rápida en algunos casos. De ahí la pregunta abierta P vs NP.
Es la pregunta: dada una máquina de Turing M y una entrada x, ¿M se detendrá alguna vez con esa entrada? Turing demostró en 1936 que no existe ningún algoritmo general que responda esta pregunta para cualquier (M, x). Es el primer ejemplo histórico de problema indecidible.
Por eso ningún antivirus puede detectar todo el malware ni ningún IDE puede detectar todos los bucles infinitos.
En la práctica, sí. En sentido estricto, no: las máquinas reales tienen memoria finita, mientras que la máquina de Turing tiene cinta infinita. Con memoria fija, el modelo formal que le corresponde a un ordenador es un autómata finito —enorme, pero finito—, y a efectos prácticos lo tratamos como Turing-completo porque esa memoria es tan grande que el límite no se nota.
Los lenguajes recursivamente enumerables (la clase más amplia de la jerarquía de Chomsky). Cuando además siempre se detiene, el lenguaje es recursivo (decidible). Un autómata finito reconoce regulares; un autómata a pila reconoce libres de contexto; una MT los engloba a todos.
Decide qué símbolos pueden aparecer en la cinta de entrada y qué símbolos auxiliares usarás (marcas como X, Y o $). Incluye siempre el símbolo blanco _.
Cada estado representa una "fase" del algoritmo: buscar, marcar, comparar, retroceder, aceptar. Pon nombres descriptivos en tu diseño y luego renombra a q0, q1…
Para cada (estado, símbolo) decide la terna (escribir, mover, nuevo estado). Una buena heurística: imagínate como el cabezal y decide qué harías al leer ese símbolo.
Define qué estados representan la aceptación. Si quieres que rechace explícitamente, deja entradas sin transición definida y que no sean finales: la máquina parará y rechazará.
Cadena vacía, un solo símbolo, cadena máxima, cadena que debe rechazarse. Ejecuta paso a paso en el simulador y verifica que el resultado coincide con tu diseño en papel.
Dibuja el diagrama de estados antes de teclear reglas. Te ahorrará horas de depuración.
Reescribir "a" como "X" al consumirla evita perder el conteo en problemas como aⁿbⁿ.
A 1500-2000 ms verás cada transición claramente. Acelera solo cuando ya entiendas el flujo.
Cuando el resultado no es el esperado, avanza con "Paso siguiente" y observa qué regla se aplica.
Si un estado intenta hacer dos cosas a la vez, divídelo en dos. La claridad supera a la concisión.
Cadena vacía, un solo carácter, casos que deben rechazarse: probarlos detecta errores que los casos normales esconden.