Un programa puede acertar algunos casos y aun así no resolver un problema. La cuestión será qué ocurre en cada entrada: si termina, si responde correctamente o si sigue esperando. Empezaremos con programas que podemos seguir a mano. Después construiremos la contradicción del problema de parada y veremos cómo los oráculos comparan la información que falta.
Si necesitas repasar:
1. Un problema de decisión pide una respuesta para cada entrada finita
Podemos codificar una palabra, una pareja de naturales o el texto finito de un programa mediante un natural. Un conjunto A recoge los códigos cuya respuesta es sí. Decidir A significa calcular su función característica: uno en A y cero fuera, terminando para toda entrada.
Fijamos un modelo formal de algoritmo, como las máquinas de Turing. La equivalencia entre varios modelos usuales es un resultado matemático. La tesis de Church–Turing identifica esa noción con procedimiento efectivo en sentido intuitivo; no se confunde esa tesis con uno de aquellos teoremas de equivalencia.
Codificar una pareja no resuelve todavía su pregunta
Usamos π(a, b)=(a+b)(a+b+1)/2+b, para a, b naturales incluyendo cero.
Ejemplo
La pareja (2,3) da (5·6)/2+3=18.Cada pareja tiene un código natural con esta regla biyectiva.
Recuperar
Se buscan los números triangulares que rodean el código.
Para 18, 15≤18<21; la suma es cinco, b=18−15=3 y a=5−3=2.Separar tareas
Leer un código permite recuperar la entrada. Todavía falta un algoritmo para responder la pregunta matemática que esa entrada representa.
Una representación efectiva permite manipular entradas de forma precisa.
Una codificación mala podría ocultar información; aquí se declara una regla calculable en ambos sentidos.
Una tabla finita da un decisor, aunque no sea una regla elegante
A={2,5,9} dentro de los naturales.
Algoritmo
Comparar la entrada n sucesivamente con dos, cinco y nueve. Si coincide, responder sí; si no coincide con ninguna, responder no.
Terminación
Solo hay tres comparaciones. El procedimiento acaba para cualquier n.
Corrección
Acepta exactamente los elementos listados. Para cinco responde sí; para ocho responde no.
Todo conjunto finito concreto es decidible.
Esto no permite guardar una tabla infinita arbitraria dentro de un programa finito.
2. Un decisor necesita corrección y terminación en los dos casos
Acertar cuando se responde no basta: un decisor debe terminar en todas las entradas. La corrección relaciona su respuesta con pertenecer al conjunto. La terminación justifica que siempre llegaremos a una respuesta.
Una prueba frecuente de terminación encuentra un natural que disminuye en cada vuelta. Probar que el algoritmo termina no prueba que sea rápido. La complejidad pregunta cuánto trabajo hace; la decidibilidad pregunta primero si existe un método total correcto.
Decidir paridad mediante una cantidad que disminuye
Entrada n natural; mientras n≥2, sustituir n por n−2. Aceptar si al final queda cero.
Invariante
Restar dos conserva la paridad. Por eso la entrada inicial y el valor actual tienen el mismo resto módulo dos.
Terminar
Mientras se ejecuta la vuelta, n es natural y disminuye estrictamente. Se acaba con cero o uno.
Responder
Cero significa par y uno impar.
Con ocho: 8→6→4→2→0, acepta.Con nueve termina en uno, rechaza.
La misma demostración cubre todas las entradas naturales.
Si se permitieran negativos habría que adaptar el algoritmo; el dominio forma parte del contrato.
Terminar siempre no garantiza acertar
Programa: ante cualquier natural, responder sí.
Tiempo
El programa termina de inmediato en todas las entradas.
Problema del universo
Para decidir N es correcto: todas sus entradas pertenecen.
Problema de pares
Para decidir los pares es incorrecto: acepta tres. Un solo contraejemplo basta para invalidar su corrección.
Las garantías pertenecen al problema y al programa juntos.
Un programa que calcula muy despacio todavía puede ser decisor si se demuestra terminación y corrección.
3. Reconocer permite confirmar un sí sin resolver todos los no
Un reconocedor de A acepta tras finitos pasos cada entrada de A. Fuera de A nunca acepta: puede rechazar o seguir indefinidamente. La diferencia con decidir está en la garantía sobre esas entradas negativas.
Un conjunto computablemente enumerable, abreviado c. e., es uno reconocible; también puede describirse mediante un procedimiento que imprime sus elementos, permitiendo repeticiones. Una lista vacía se maneja con un procedimiento que no imprime nada. No basta decir que un conjunto es numerable en sentido de cardinalidad.
Una búsqueda reconoce cuadrados aunque se programe sin salida negativa
Para n natural, probar k=0,1,2,… y aceptar si k²=n.
Entrada positiva
Para n=9 llega a k=3 y acepta tras finitos intentos.
Entrada negativa
Para n=3 no aparece ningún k y esta versión sigue buscando para siempre.
Diagnóstico
Es un reconocedor correcto de cuadrados. Los cuadrados también son decidibles: mejorar el programa para rechazar al llegar a k²>n da terminación en los negativos.
Un reconocedor que no termina no demuestra indecidibilidad del problema.
La imposibilidad debe referirse a todos los posibles decisores, no al defecto de una implementación.
Una prueba positiva puede encontrarse enumerando testigos
Entrada: un polinomio entero p(x). Buscar un entero x con p(x)=0.
Orden de búsqueda
Probar 0,1,−1,2,−2,…; cada evaluación de un polinomio en un entero es finita.
Si existe raíz
Toda raíz entera ocupa una posición finita de esa lista y será encontrada.
Si no existe
La búsqueda descrita no acepta nunca. Esto prueba reconocimiento del problema, pero no demuestra por sí solo que falte un decisor.
Se declara exactamente qué garantiza la búsqueda.
No se deduce indecidibilidad de problemas multivariables a partir de este ejemplo de una variable.
4. Entrelazar búsquedas evita que una ejecución infinita bloquee las demás
Si queremos simular muchos programas, ejecutarlos uno detrás de otro puede atascarse en el primero. Entrelazar significa guardar el estado de cada tarea y darles turnos finitos. El modelo de máquina permite pausar una simulación y retomarla.
Por ejemplo, en la etapa s damos un paso adicional a cada una de las primeras s tareas que no haya terminado. Toda tarea concreta acaba recibiendo cualquier cantidad finita de pasos que necesite. Las tareas ya terminadas se registran y se omiten en turnos posteriores.
Una tarea infinita no debe ocultar una respuesta rápida
P₀ nunca termina; P₁ acepta tras tres pasos propios.
En serie
Ejecutar P₀ hasta que acabe antes de empezar P₁ nunca permite ver la aceptación de P₁.
En turnos
La etapa uno da un paso a P₀. Las etapas dos, tres y cuatro dan también un paso a P₁; al final de la cuarta P₁ ha recibido sus tres pasos.
Conclusión
Detectamos su aceptación aunque P₀ siga ejecutándose. Cada etapa hace un trabajo finito y la espera de P₁ es finita.
Entrelazar cambia la organización de la búsqueda, no las respuestas correctas.
El número de etapa y el número de pasos recibidos por una tarea no son lo mismo.
Pasar de reconocedor a enumerador sin perder entradas
R reconoce A⊆N. Queremos imprimir todos los elementos de A.
Preparar
Iniciar R(0), R(1), R(2),… de forma gradual, conservando sus estados.
Entrelazar
En la etapa s dar un paso a cada R(n) con n<s que todavía no haya acabado. Si acepta, imprimir n.
Garantía
Si n∈A, su ejecución acepta después de un número finito de pasos propios y llegará a imprimirlo. Si n∉A, la corrección de R impide que se imprima como aceptación.
Reconocimiento implica enumeración efectiva mediante turnos.
En sentido inverso, para reconocer n se espera a que el enumerador lo imprima; si nunca aparece, se puede esperar indefinidamente.
5. Reconocer el conjunto y su complemento permite decidir
A es decidible si y solo si A y su complemento Aᶜ son c. e. Si hay un decisor, basta aceptar según su respuesta para reconocer cada lado. La otra dirección necesita hacer funcionar los dos reconocedores sin bloquearse.
Cada entrada pertenece exactamente a uno de los dos lados. Por ello alguno de los reconocedores terminará aceptando. Nunca deberían aceptar ambos si realmente reconocen conjuntos complementarios.
Dos confirmaciones parciales producen una respuesta total
R₊ reconoce A y R₋ reconoce Aᶜ; se recibe n.
Dar turnos
Ejecutar un paso de R₊(n), luego uno de R₋(n), y repetir. Si uno rechaza, no se deduce nada del otro: se continúa el que queda.
Elegir respuesta
Si R₊ acepta, responder sí. Si R₋ acepta, responder no.
Terminar
Si n∈A acepta R₊; si n∉A acepta R₋.En ambos casos los turnos le proporcionan los pasos finitos que necesita.
La terminación se demuestra sin conocer de antemano un tiempo de espera.
Esperar a que R₊ termine antes de iniciar R₋ perdería esta garantía.
La palabra complemento aporta una hipótesis indispensable
R₁ reconoce los múltiplos de dos y R₂ los múltiplos de tres.
Intersección
Seis está en ambos. Dos aceptaciones no podrían significar respuestas opuestas a una misma pregunta.
Hueco
Cinco no está en ninguno. Ambos reconocedores podrían quedarse esperando y no dar respuesta.
Requisito
No son conjuntos complementarios. El criterio anterior no aplica aunque ambos sean reconocibles y el entrelazado sea correcto.
La cobertura total y la exclusión mutua justifican el decisor.
El complemento de los pares son los impares, no los múltiplos de tres.
6. La parada es reconocible, pero ningún decisor resuelve todos sus casos
HALT recibe un programa P y una entrada x, y pregunta si P(x) termina. Se reconoce simulándolo y aceptando si llega a parar. No observar parada durante un tiempo finito no certifica que nunca vaya a ocurrir.
Para demostrar que no hay decisor supondremos que existe uno total correcto H(P, x). Bajo esa suposición construiremos otro programa que usa H y contradice su predicción sobre sí mismo. La contradicción elimina la suposición; no afirma la existencia de un H defectuoso que ya supiéramos construir.
Un tiempo de espera no es una prueba universal
Se simula un programa durante mil pasos sin observar parada.
Compatible con terminar
Un programa que da mil un pasos y después termina supera ese límite sin ser infinito.
Compatible con no terminar
Un bucle incondicional también supera el límite y nunca termina.
Conclusión
El hecho observado no distingue ambos casos. Algunos programas se resuelven por un análisis concreto, pero no existe un umbral de simulación universal que decida todos.
Lentitud y no terminación no son equivalentes.
La reconocibilidad usa parada observada como prueba positiva, no ausencia temporal como prueba negativa.
Construir la contradicción sobre el propio código
Si existiera H, definir D(P): si H(P, P) dice termina, entrar en bucle; si dice no termina, terminar.
Código propio
D es un programa finito bajo la suposición de que H existe y es total. Sea d el código de D; consideramos D(d).
Primera respuesta
Si H(d, d) dice que termina, la definición de D lo hace entrar en bucle. La predicción sería incorrecta.
Segunda respuesta
Si H(d, d) dice que no termina, D termina. También sería incorrecta. Las dos respuestas posibles contradicen la corrección de H.
HALT es c. e. e indecidible.
Si HALTᶜ fuera c. e., el criterio del complemento daría un decisor; por eso su complemento no es c. e.
7. Una reducción dice qué problema resolveríamos si tuviéramos otro
A≤T B significa que existe un procedimiento total para decidir A con un oráculo que contesta pertenencia a B. Es un recurso matemático ideal: cada consulta recibe sí o no. Las consultas pueden depender de respuestas anteriores.
Si A es indecidible y A≤T B, entonces B es indecidible: sustituir el oráculo por un decisor de B daría un decisor de A. La dirección importa. Una reducción muchos-a-uno es un caso particular: una función total computable f satisface n∈A si y solo si f(n)∈B.
Un problema fácil también puede reducirse a parada
Para n, generar el código de Qₙ: si n es par, terminar; si no, entrar en bucle. Qₙ ignora su entrada.
Transformar
El texto de Qₙ se obtiene efectivamente insertando el número n en una plantilla finita. No se necesita resolver parada para escribir ese texto.
Equivalencia
n es par exactamente cuando Qₙ termina sobre entrada cero.
Dirección
Un oráculo de HALT permitiría decidir paridad mediante esa consulta. Esto no hace indecidibles los pares: ya tienen un algoritmo sin oráculo.
Reducir fácil a difícil no prueba dificultad del primero.
La transformación de entradas debe ser total y computable, no depender de conocer ya la respuesta buscada.
La versión diagonal de parada contiene la misma información
K={e: el programa de código e termina sobre entrada e}.
K hacia HALT
Para preguntar e∈K basta consultar HALT con el programa e y la entrada e.
HALT hacia K
Dada una pareja (P, x), generar un programa Q que ignora su propia entrada y simula P(x). Si q es su código, Q(q) termina exactamente cuando P(x) termina.
Comparar
La compilación de esa plantilla es efectiva y total. Por tanto ambas versiones se reducen mutuamente y K también es indecidible y c. e.
Cambiar la forma de entrada no cambia aquí el grado de información.
No se ejecuta P(x) durante la transformación; solo se escribe un programa que lo ejecutaría después.
8. Un grado agrupa problemas que se resuelven mutuamente con oráculos
Es una relación de equivalencia; una clase es un grado de Turing. El grado 0 reúne todos los conjuntos decidibles. El grado de K se llama 0′.
Los grados se ordenan parcialmente por reducibilidad. No todos forman una única fila: existen grados incomparables. Ese resultado se enuncia, sin fingir que ya hemos construido un par. Ser c. e. no depende solo del grado: el acceso a un oráculo permite también invertir sus respuestas.
Un conjunto y su complemento tienen el mismo grado
Sea B cualquier conjunto de naturales.
Una consulta
Para decidir Bᶜ con oráculo B, preguntar si n∈B e invertir sí y no.
Volver
Con oráculo Bᶜ se hace lo mismo para decidir B. Así B≡T Bᶜ.
Caso de parada
K es c. e. pero Kᶜ no lo es; aun así tienen el mismo grado 0′. Igual grado no significa igual comportamiento de reconocimiento sin oráculo.
El grado mide capacidad de decisión relativa, no una sola etiqueta de enumerabilidad.
La inversión usa una respuesta negativa del oráculo, que un reconocedor ordinario no garantiza.
La unión codificada reúne la información de dos oráculos
A⊕B={2n: n∈A}∪{2n+1: n∈B}.
Recuperar A
Para preguntar n∈A, consultar si 2n pertenece a A⊕B.Recuperar B
Para preguntar n∈B, consultar si 2n+1 pertenece a A⊕B.Decidir la unión
Con acceso a ambos oráculos, se comprueba paridad de la entrada y se consulta el correspondiente. La codificación mantiene separados los dos conjuntos.
A⊕B contiene suficiente información para resolver A y B.
La unión ordinaria A∪B no permite en general recuperar qué elementos procedían de cada lado.
9. El salto añade parada relativa y supera estrictamente al oráculo inicial
Para un conjunto A, su salto A′ codifica qué programas con oráculo A terminan sobre su propio código. Fijamos una enumeración efectiva de esas máquinas. El oráculo aparece como un recurso del modelo, no como una máquina física que se promete construir.
La primera afirmación se prueba fabricando una consulta de parada. La segunda repite la diagonalización entre programas que ya disponen del oráculo A.
Preguntar por A usando una pregunta de parada relativa
Para n, generar Qₙ con oráculo A: consultar n∈A; terminar si sí y entrar en bucle si no.
Código
La plantilla de Qₙ se produce efectivamente sin conocer la respuesta del oráculo. El programa ignora su entrada ordinaria.
Consulta al salto
Si q es su código, q∈A′ significa que Qₙ con oráculo A termina sobre q.
Equivalencia
Eso ocurre exactamente cuando n∈A.Una consulta al salto permite resolver la pertenencia original.
El salto contiene al menos la información del oráculo de partida.
La fabricación de q es uniforme a partir de n; la consulta a A ocurre al ejecutar Qₙ.
Dar un oráculo no elimina la diagonalización
Suponer que H con oráculo A decide toda parada de programas con ese mismo oráculo.
Construir
Definir D con oráculo A que consulta H(P, P), entra en bucle si recibe sí y termina si recibe no.
Aplicar a sí mismo
D pertenece a la clase de programas con oráculo A. Aplicarlo a su propio código contradice H en cualquiera de las dos respuestas.
Consecuencia
No existe tal H.
A<_T A′ y, al iterar, 0<_T 0′<_T 0″.Ningún nivel obtiene gratuitamente su propia parada.
Cada salto introduce información estrictamente nueva.
La conclusión compara clases de procedimientos; no dice que todos los problemas indecidibles tengan el mismo grado.
10. Las propiedades del comportamiento pueden ser más difíciles que leer el texto
Leer si el texto de un programa contiene un símbolo es una pregunta sintáctica sobre un objeto finito. Preguntar qué función parcial calcula exige considerar sus ejecuciones. El teorema de Rice afirma que toda propiedad no trivial que dependa solo de la función parcial computada es indecidible en una enumeración estándar de programas.
No usaremos el nombre del teorema como sustituto de una prueba en un caso concreto. Vamos a reducir parada a una propiedad de funciones, y después veremos por qué totalizar todas las entradas es una exigencia todavía distinta de reconocer algunas.
Ser la función cero total permitiría decidir parada
Dada una instancia (P, x), generar Q(n): simular P(x); si termina, devolver cero.
Si P(x) termina
Para toda entrada n, Q acaba devolviendo cero. Calcula la función cero total.
Si P(x) no termina
Q no devuelve nada en ninguna entrada. Calcula una función parcial sin valores definidos.
Reducción
Un decisor de si un programa calcula la función cero total distinguiría ambos casos y decidiría HALT. Por tanto esa propiedad es indecidible.
Una propiedad semántica concreta se separa mediante una reducción explícita.
Contar los caracteres del programa sigue siendo decidible y no contradice el resultado.
El conjunto de programas totales no es c. e.
Dada (P, x), generar R(n): simular P(x) durante n pasos; si no terminó, devolver cero; si terminó, entrar en bucle.
Si P(x) nunca termina
Para cada n la simulación acotada acaba sin observar parada y R(n) devuelve cero. R es total.
Si P(x) termina
Hay un número T de pasos suficiente para verlo. Para n≥T, R(n) entra en bucle y R deja de ser total.
Conclusión
HALTᶜ se reduce muchos-a-uno al conjunto TOT de códigos de programas totales. Si TOT fuera c. e., reconocer su imagen permitiría reconocer HALTᶜ, contradicción. Por tanto TOT no es c. e.
No todas las propiedades indecidibles son reconocibles.
La simulación de n pasos siempre es finita; la transformación que escribe R no espera a que P(x) termine.
Ahora lo resolvemos de principio a fin.
EJEMPLO RESUELTO 1
Un conjunto decidible
Diseña un decisor para los números pares.
Dominio
La entrada es un natural n. Queremos responder sí exactamente cuando existe k natural con n=2k.
Procedimiento
Calcular el resto r al dividir n entre dos. Este cálculo termina para todo natural.
Respuesta
Si r=0, aceptar; si r=1, rechazar.Corrección positiva
r=0 equivale a n=2k, de modo que acepta exactamente los pares.
Negativos del conjunto
Para los impares el resto es uno y el programa también termina, dando no.
Comprobar
Ocho tiene resto cero y nueve resto uno. Las dos garantías, terminar y acertar, quedan justificadas para todo n.
Los pares son decidibles.
Para 8 acepta y para 9 rechaza.
EJEMPLO RESUELTO 2
Complemento y decisión
Supón que A y su complemento son enumerables. Construye un decisor.
Hipótesis
A y Aᶜ son computablemente enumerables, por lo que tienen reconocedores R₊ y R₋.
Entrada común
Dar la misma entrada n a ambos; no se busca un elemento diferente en cada simulación.
Turnos
Alternar un paso de cada ejecución que siga activa. Si una rechaza, continuar la otra.
Si n∈A
R₊ aceptará tras finitos pasos; al verlo, responder sí.
Si n∉A
Entonces n∈Aᶜ y R₋ aceptará tras finitos pasos; al verlo, responder no.
Terminar y acertar
Uno de los dos casos siempre ocurre, y los reconocedores no aceptan fuera de sus conjuntos. La alternancia proporciona un decisor total correcto.
A es decidible.
La alternancia evita bloquearse en el reconocedor incorrecto.
Los símbolos que hemos usado
- N
- Naturales 0,1,2,…, usados para codificar entradas y programas.
- Aᶜ
- Complemento N\A del conjunto A de entradas afirmativas.
- Decidible
- Admite un algoritmo que termina para toda entrada y responde pertenencia correctamente.
- c.e.
- Computablemente enumerable: existe un algoritmo que acepta exactamente sus elementos.
- A ≤T B
- Hay un decisor de A que puede consultar pertenencia a B como oráculo.
- A ≡T B
- A y B se reducen mutuamente; pertenecen al mismo grado de Turing.
- A′
- Salto de A: problema de parada para programas con oráculo A, en una codificación fijada.
Ahora te toca a ti.
Tienes cinco ejercicios. Inténtalos; las pistas te ayudan si te atascas.
Practicar este tema →