¿Cómo mostrar que el conjunto de máquinas que aceptan idiomas en , es decidible solo si ?

8

Quisiera su ayuda para probar que el lenguaje es decidible iff .

L={M|L(M)NPP}
P=NP

Si , entiendo que es el lenguaje de las máquinas de Turing vacías. Entonces es un problema de , pero eso no es lo que se pregunta, así que me confundí.P=NPLco-RE

Sé que para mostrar , necesito mostrar el problema que también es y .P=NPNPCP

¿Alguna ayuda? ¡Gracias!

Jozef
fuente

Respuestas:

9

Hay dos casos a considerar.

  1. Suponga que . Entonces . El lenguaje vacío es decidible; Como ninguna palabra le pertenece, es trivial decidir si una palabra le pertenece o no.P=NPL={ML(M)}=

  2. Suponga que . Ahora su resultado se sigue directamente del teorema de Rice .PNP

Dave Clarke
fuente