Siguiente: Problema de totalidad (PT)
Un nivel arriba: Reducción de problemas al
Anterior: Reducción de problemas al
Instancia:
Solución:
Proposición 3.3
PA es irresoluble.
Demostración: Si pudiéramos decidir cuándo dos lenguajes libres de contexto tienen intersección no-vacía, al considerar los lenguajes L1 y L2 de la proposición anterior podríamos decidir si la máquina M posee una computación terminal a partir de
.
Así pues resolveríamos el Problema de la Parada para máquinas de Turing. Como esto es imposible, PA es irresoluble.
Guillermo Morales-Luna
2000-07-10