Demostraciones de Indecidibilidad y Complejidad Computacional: Reducciones y Clases P y NP
Enviado por Chuletator online y clasificado en Filosofía y ética
Escrito el en
español con un tamaño de 3,8 KB
Demostración de Indecidibilidad: HALTTM
Suponemos que INFTM es decidible. Sea R un decisor para INFTM. Construimos un decisor S para HALTTM:
S(<M,w>):
- Construye una máquina M' que, sobre la entrada x, realiza lo siguiente:
- a) Simula M sobre w durante x pasos.
- b) Si M ha parado en esos x pasos, ACCEPT.
- c) Si M no ha parado en esos x pasos, REJECT.
- Ejecuta R(<M'>).
- Si R acepta, ACCEPT.
- Si R rechaza, REJECT.
Análisis de casos
- Caso 1: M para sobre w. La máquina M' acepta x, por lo que R acepta y S acepta. M' aceptaría en t pasos y existen infinitas cadenas con longitud mayor o igual que t; por tanto, L(M') es infinito.
- Caso 2: M' nunca ve a M parar en x pasos. M' rechaza toda entrada x. L(M') no es infinito. R rechaza y S rechaza.
Como S decidiría... Continuar leyendo "Demostraciones de Indecidibilidad y Complejidad Computacional: Reducciones y Clases P y NP" »
catalán con un tamaño de 3,07 KB