Máquinas de Turing y decidibilidad

Usamos una cinta con celdas indexadas por enteros, un cabezal que lee una celda y un control de estados finitos. La entrada ocupa un bloque finito; el resto empieza en blanco □.

El alfabeto de entrada Σ no contiene el blanco. El alfabeto de cinta Γ incluye Σ, el blanco y posibles marcas auxiliares. El cabezal comienza en el primer símbolo, o en blanco si la palabra es vacía. Una ejecución finita solo visita finitas celdas.

Una transición usa el estado y el símbolo actuales. Escribe b en esa celda, cambia a q′ y se mueve según D∈{L,R,S}: izquierda, derecha o quedarse. Los estados de aceptar y rechazar detienen la ejecución.

La máquina determinista tiene un único paso por pareja no final. Declaramos los casos de la tabla; una descripción de alto nivel es un algoritmo válido cuando sus acciones se pueden descomponer en instrucciones locales finitas.

Una configuración consta de estado, contenido de cinta y posición del cabezal. Repetir solo el estado no repite necesariamente la situación.

En una máquina determinista, volver exactamente a una configuración completa no final reproduce todo el futuro. Si no se ha detenido entre las dos visitas, queda un ciclo infinito. Pero también puede no parar sin repetir configuraciones, por ejemplo avanzando siempre a celdas nuevas.

Para decidir {0ⁿ1ⁿ:n≥0}, primero comprobamos que la entrada tenga forma 0*1*. Después marcamos el primer cero sin marcar como X, buscamos un uno sin marcar y lo cambiamos por Y. Volvemos al comienzo y repetimos.

Después de cada pasada completa hay tantas X como Y: cada marca representa una pareja. Si falta un uno o sobran unos al terminar los ceros, rechazamos. Cada pasada elimina dos símbolos pendientes; cada barrido termina en el borde blanco de un bloque finito. Esto prueba corrección y terminación, incluida ε.

Un decisor acepta exactamente las palabras del lenguaje, rechaza las demás y termina en todas las entradas. Un reconocedor garantiza aceptación finita de las palabras del lenguaje; fuera de él puede rechazar o seguir indefinidamente.

Todo decidible es reconocible. Una simulación que todavía no acepta no ha respondido no. Y que un algoritmo concreto se quede en bucle no demuestra que su lenguaje sea indecidible: podría existir otro algoritmo que sí termine siempre.

La máquina también puede producir una salida. En unario, una palabra de n unos representa n y ε representa cero. Añadir un uno calcula el sucesor.

Si termina con salida para todo dato válido, la función calculada es total; si solo lo hace para algunos, es parcial. En binario el sucesor necesita acarreos: la representación cambia el algoritmo, aunque la operación numérica sea la misma.

Una tabla finita de transiciones se puede codificar como una palabra. Una máquina universal recibe ⟨M,w⟩ y simula sus pasos. Si M se ejecuta sin fin, la simulación también; ser universal no significa decidir si terminará.

Varias cintas, cinta seminfinta o máquinas de registros tienen la misma capacidad de cómputo, aunque las simulaciones cambien el coste. La tesis de Church–Turing relaciona estos modelos con la idea informal de procedimiento efectivo; no es solo un teorema entre dos modelos ya definidos.

Supongamos un H total que siempre acierta si M termina con entrada w. Construimos D con entrada p: consulta H(p,p); si predice parada, D entra en bucle; si predice no parada, D se detiene.

Ahora damos a D su propia descripción. Si H predice que D para, D no para; si predice que no, D para. Las dos posibilidades contradicen la corrección supuesta. No existe ese decisor general. Es una contradicción sobre terminar, no solo sobre aceptar.

No parar tras mil pasos solo informa de esos mil pasos. Puede detenerse después. Para probar no parada sirven un invariante que excluya estados finales o una repetición completa de configuración.

La indecidibilidad excluye un algoritmo total correcto para todos los casos, no pruebas particulares o clases restringidas. La complejidad pregunta cuántos pasos o celdas usa un algoritmo existente: un decisor muy lento sigue siendo decisor.