Modelos de computación y decidibilidad

Un alfabeto Σ es un conjunto finito de símbolos. Σ* contiene todas sus cadenas finitas, incluida la vacía ε. Un lenguaje L⊆Σ* reúne las entradas cuya respuesta es sí. Decidir L exige responder correctamente tanto si la cadena pertenece como si no pertenece, en tiempo finito.

Se pueden codificar enteros, grafos o programas como cadenas. La codificación debe ser efectiva: un procedimiento finito permite construirla e interpretar su estructura. Las entradas mal formadas pueden rechazarse según la especificación. Una pregunta de decisión no es lo mismo que pedir construir una solución, aunque ambas puedan relacionarse.

Un autómata finito determinista tiene estados Q, uno inicial q₀, un conjunto de aceptación F y una transición δ(q, s) por cada estado y símbolo. Lee de izquierda a derecha. Tras consumir toda la cadena acepta si su estado final pertenece a F. No guarda el prefijo completo: solo el estado.

Para contar unos módulo dos basta recordar par o impar. El dibujo usa P inicial y aceptante, I no aceptante: 0 mantiene y 1 cambia. Los lenguajes aceptados por autómatas finitos son regulares. La memoria finita permite muchas preguntas, pero no recordar sin límite una cantidad exacta de símbolos.

Una máquina de Turing combina control finito, cinta de símbolos y un cabezal. Una transición mira estado y símbolo, escribe uno, cambia de estado y mueve el cabezal. La cinta tiene espacio disponible sin una cota fija común a todas las entradas; cada ejecución finita utiliza solo una parte finita.

Las variantes usuales con varias cintas y los modelos de registros apropiados tienen igual capacidad de cálculo que una cinta, aunque la simulación cambie los costes. Esas equivalencias entre modelos formales son teoremas. La tesis de Church–Turing relaciona informalmente esa capacidad con lo que llamamos algoritmo efectivo; no se confunde con una igualdad de velocidades ni con un teorema sobre una definición informal.

Un decisor siempre termina y responde sí exactamente en L. Un reconocedor debe aceptar cada entrada de L después de un número finito de pasos y no aceptar ninguna de fuera; en negativos puede rechazar o seguir ejecutándose. Todo lenguaje decidible es reconocible, porque su decisor cumple la exigencia más débil.

No observar aceptación hasta cierto instante no es una respuesta negativa de un reconocedor. La distinción está en la garantía universal de terminación en negativos, no en que el programa haya acertado alguna vez o en cuánto tiempo lleva ejecutándose.

Si L y su complemento son reconocibles, simulamos ambos reconocedores con la misma entrada, alternando un paso de cada uno. Si acepta el de L respondemos sí; si acepta el del complemento respondemos no. La entrada pertenece a uno de los dos, así ese reconocedor aceptará tras un número finito de sus pasos.

Ejecutar primero uno hasta que termine y luego el otro no ofrece esa garantía: el primero podría quedarse para siempre en una entrada negativa. La intercalación hace progresar ambos sin esperar a que uno rechace. Junto con el hecho de que un decidible tiene complemento decidible, obtenemos: L es decidible si y solo si L y su complemento son reconocibles.

Una descripción finita de máquina puede codificarse como una cadena ⟨M⟩. Una máquina universal lee esa descripción y simula las transiciones de M con una entrada w. La pregunta HALT reúne pares ⟨M, w⟩ para los que M termina con w. Terminar incluye tanto aceptar como rechazar: no es la misma pregunta que “acepta”.

HALT es reconocible: se simula M y se acepta el par si la simulación alcanza cualquier estado de parada. Si M no termina, la simulación puede continuar indefinidamente sin aceptar. Ningún tiempo finito de espera por sí solo certifica no parada; una prueba especializada de un programa concreto sí podría hacerlo.

Supongamos que H(p, w) siempre termina y acierta si el programa descrito por p termina con entrada w. Construimos D(p): consulta H(p, p); si H responde que termina, D entra en bucle; si responde que no termina, D termina. Si H existiera, esa sería una construcción efectiva mediante una llamada y una bifurcación.

Ahora se ejecuta D con su propia descripción ⟨D⟩ como dato. No hace falta que D descubra su código ni que pueda resolver su propio comportamiento: nosotros proporcionamos esa cadena de entrada. Las dos posibles respuestas de H se contradicen con la definición de D. Por tanto ese H total y correcto no existe.

Una reducción computable A≤ₘB transforma cualquier entrada x en f(x), termina y cumple x∈A si y solo si f(x)∈B. Si B fuese decidible, primero calcular f y después usar su decisor decidiría A.

La transformación no debe resolver antes la pregunta difícil. Puede construir el código de otro programa que la simulará después. La dirección importa: reducir un problema fácil a uno indecidible no vuelve difícil al primero. Tampoco basta conservar solo las respuestas positivas; el “si y solo si” controla positivos y negativos.

La indecidibilidad excluye un único algoritmo correcto y terminante para todas las entradas del dominio. No impide resolver programas concretos con invariantes, inspección o restricciones sintácticas. Muchas clases restringidas tienen decisores; eso no contradice el resultado universal.

Un problema decidible puede ser extremadamente costoso y sigue siendo decidible. Si limitamos la pregunta a “¿termina en como máximo T transiciones?”, hay un procedimiento finito: comprobar parada inicial, simular hasta T pasos y revisar si se alcanzó parada dentro del límite. Un no en esa pregunta no afirma que jamás termine.

Si T se da en binario, esa simulación puede ser muy cara respecto a su longitud, sin dejar de terminar.