Así es como funciona la reducción:
1. Comprender el problema de detención:
*El problema de detención pregunta:Dado un algoritmo (programa) *H *y una entrada *i *Para ese algoritmo, *H *se detendrá (terminará en ejecución) cuando se ejecuta con la entrada *I *?
* El problema de detención es indecidible . No hay algoritmo, `Halts (H, I)`, que siempre puede devolver correctamente `True` si *H *se detiene *I *, y` False` if *H *loops para siempre.
2. La técnica de reducción (prueba por contradicción):
Para demostrar que un problema * p * es indecidible, haces lo siguiente:
1. Suponga, en aras de la contradicción, que * p * es decidible. Esto significa que asumimos que existe un algoritmo `solvep (inputForp)` que siempre devuelve correctamente la solución para cualquier instancia de problema *P *.
2. Construya una reducción: Debe mostrar cómo usar el algoritmo hipotético `solvep ()` para resolver el problema de detención. En otras palabras, creas un algoritmo `Halts (H, I)` que usa `solvep ()` como subrutina. Este algoritmo `se detiene (h, i)` debería funcionar de la siguiente manera:
`` `` ``
se detiene (h, i):
1. Transforme la instancia del problema de detención (H, I) en una instancia del problema P, llamemos `inputforp`. Este es el paso crucial:está elaborando `inputforp` de una manera que *la solución al problema P en esta entrada revela directamente si H se detiene en i *. Los detalles de cómo haces esta transformación dependen completamente del problema *P *.
2. Resultadop =solvep (inputForp) // llame a nuestro solucionador hipotético para el problema P.
3. Basado en ResultP, determine si H se detiene en I y devuelve verdadero o falso en consecuencia.
`` `` ``
3. Demuestre que su reducción implica una solución al problema de detención: Explique claramente cómo el resultado de `solvep (inputForp)` directamente le indica si el algoritmo *h *se detiene en la entrada *i *.
4. Contradicción: Debido a que se sabe que el problema de detención es indecidible, y ha demostrado que un hipotético `solvep` podría usarse para resolverlo, ha alcanzado una contradicción.
5. Conclusión: Por lo tanto, nuestra suposición inicial (que * p * es decidible) debe ser falsa. Por lo tanto, el problema * p * es indecidible.
Ideas y desafíos clave:
* La transformación es clave: La parte más difícil es encontrar una transformación de (h, i) a una instancia de *p *tal que la solución a *p *revela directamente si *h *se detiene *i *. Esto requiere inteligencia y comprensión tanto del problema de detención como del problema *P *.
* Prueba por contradicción: No estás * directamente * demostrando que * p * es indecidible. Estás demostrando que si * p * * fuera * decidible, conduciría a una imposibilidad (resolviendo el problema de detención).
* Generalización: El objetivo es demostrar que *no puede *existir un algoritmo que resuelva *p *para *todas las entradas posibles *. Su reducción debe ser válida para cualquier algoritmo arbitrario *H *y entrada *I *.
Ejemplo:el problema de vacío para las máquinas Turing
El problema de vacío para las máquinas Turing pregunta:Dada una máquina turing *m *, ¿el lenguaje es aceptado por *m *vacío (es decir, *m *acepta *alguna *entrada)? Demostremos que esto es indecidible.
1. Suponga que el vacío es decidible: Suponga que hay un algoritmo `isEtimty (m)` que devuelve `verdadero 'si el lenguaje aceptado por * m * está vacío, y` falso` de lo contrario.
2. Reducción: Crearemos un algoritmo `Halts (H, I)` que usa `isEtimty ()`:
`` `` ``
se detiene (h, i):
1. // Construye una nueva máquina Turing M_HI
// - m_hi toma cualquier entrada w.
// - M_HI primero simula H en I.
// - Si h se detiene en i, entonces m_hi acepta w.
// - Si h no se detiene en i, entonces m_hi loops para siempre.
M_hi =constructtm (h, i)
2. Result =isEmpty (m_hi)
3. Si el resultado ==verdadero:
devolver falso // h no se detiene en i
demás:
devolver verdadero // H se detiene en i
`` `` ``
3. Por qué funciona esto:
*If *h *se detiene *i *, entonces `m_hi` aceptará *cada *entrada` W`. Por lo tanto, el lenguaje aceptado por `m_hi` no está vacío (en realidad es σ*, el conjunto de todas las cadenas). Por lo tanto, `isEmpty (m_hi)` devolverá `falso`, y` se detiene (h, i) `devuelve` verdadero '.
*If *h *no *no *se detiene *i *, entonces `m_hi` buceará para siempre en *cada *entrada` W`. Por lo tanto, el lenguaje aceptado por `m_hi` está vacío. Por lo tanto, `isEtimty (m_hi)` devolverá `verdadero 'y` detiene (h, i) `devuelve` falso'.
4. Contradicción: Hemos creado un algoritmo `Halts (H, I)` que usa `isEtimty ()` para resolver el problema de detención. Pero el problema de detención es indecidible, por lo que esto es una contradicción.
5. Conclusión: Por lo tanto, el problema de vacío para las máquinas Turing es indecidible.
Notas importantes:
* La reducción muestra que el problema * p * es * al menos tan difícil como * el problema de detención. Dado que el problema de detención es indecidible, también lo es *P *.
* Las reducciones a menudo se usan para demostrar la indecidabilidad, pero también se pueden usar para demostrar que la completitud de NP en el contexto de la complejidad computacional.
* El algoritmo `constructtM (h, i)` En el ejemplo anterior es una construcción teórica. En la práctica, en realidad no "construirías" una máquina física de Turing. El punto es que * en principio * es posible describir dicha máquina.
En resumen, la reducción del problema de detención es una técnica de prueba poderosa que nos ayuda a comprender los límites de la computación. Al demostrar que resolver un problema en particular implicaría una solución al problema de detención (que sabemos que es imposible), podemos concluir que el problema es indecidible.