¿Podemos mostrar que un idioma no es computablemente enumerable al mostrar que no hay un verificador para él?

11

Una de las definiciones de un conjunto computablemente enumerable (ce, equivalente a recursivamente enumerable, equivalente a semidecidable) es la siguiente:

AΣ es ce si hay un lenguaje decidible (llamado verificador) st para todos , x Σ VΣxΣ

xA si y sólo si existe una st .x , y VyΣx,yV

Entonces, una forma de mostrar que un lenguaje no es ce es mostrar que no hay un verificador decidible para él. ¿Es útil este método para mostrar que los idiomas no son ce en la práctica?V

Anónimo
fuente
3
¿Qué es ce (quiso decir re?)
Ran G.
No puedo pensar en una situación en la que esto sea útil para probar que un idioma no sea CE. Espero que pueda reemplazar fácilmente con en una reducción de muchos. Si se te ocurre alguna otra reducción, esperaría que "resultados negativos" no significarían mucho, ya que está cuantificado existencialmente. A x , y V yVAx,yVy
Lucas Cook
@RanG., Re es la antigua terminología, en la actualidad, las personas que trabajan en la teoría de la computabilidad suelen llamarla ce. (Si está interesado en el motivo del cambio en la terminología, le sugiero que consulte la página de inicio de Robert Soare.)
Kaveh
@Kaveh gracias. Todos los días uno aprende cosas nuevas ...
Ran G.

Respuestas:

4

En la práctica, generalmente no probamos solo que un idioma es re o no re. Si el lenguaje es re, queremos saber si es recursivo. Si no es re, queremos saber qué tipo de grado de Turing tiene, no solo que el grado de Turing no es re.

Por ejemplo, si es un problema con entonces no es re, pero ese hecho sobre el salto de Turing es más informativo que saber que no es rePPT0PP

Entonces, si bien, en principio, podría mostrar que un idioma no se restablece al demostrar que no hay verificador, en la práctica es más informativo demostrar que el lenguaje no se restablece al mostrar que computa algo que ningún restablecimiento puede calcular; la naturaleza de ese "algo" generalmente brinda información útil sobre el problema que se estudia.

Carl Mummert
fuente
3

Para aclarar la terminología, uso claro: decidable = recursivo = computable, semidecidable = recursivamente enumerable = computablemente enumerable, co-semidecidable = co-recursivamente enumerable = co-computablemente enumerable.

En la práctica, un método común para mostrar que un lenguaje no es semidecidable es mostrar que no es decidible y que es co-semidecidable. Luego hace uso del hecho de que cualquier lenguaje que sea semidecidable y co-semidecidable también es decidible para concluir que su idioma no es semidecidable. (tenga en cuenta que esto solo funciona en una dirección: un lenguaje no puede ser semidecidable ni co-semidecidable, en cuyo caso necesita algún otro método)

Como ejemplo: sabemos que decidir si un es ambiguo es indecidible, pero es fácil co-semidecidir: simplemente se da una cadena que tiene dos análisis diferentes. Esto implica que no es semidecida si un es ambiguo.CFGCFG

Otro método es mostrar que el lenguaje está completo para algún nivel superior de la jerarquía aritmética .

Por supuesto, es posible demostrar directamente que no hay verificador, pero esto a menudo es tedioso, ya que generalmente repite la prueba de que el problema de detención es indecidible. Sin embargo, tenga en cuenta que el argumento anterior prueba esencialmente de manera implícita que no puede haber verificador, por lo que supongo que podría decir que es un método para demostrar que no hay verificador, pero luego podría considerar cualquier prueba de no semidecidibilidad como prueba de que existe sin verfier.

Alex ten Brink
fuente
Hay un defecto en tu idioma. Un lenguaje no puede ser semidecidible ni co-semidecidable. Los idiomas indecidibles son tales lenguajes.
Dave Clarke el
@DaveClarke: agregué algunas definiciones de terminología. ¿Es correcto ahora?
Alex ten Brink
No ( semidecidible ) no (decidable) co-semidecidable.
Dave Clarke
@DaveClarke: agregué una nota diciendo que solo funciona en una dirección.
Alex ten Brink
3
No estoy convencido de que esta sea una técnica que cualquiera usaría. ¿Por qué no reducir el problema a un problema conocido "no semidecidible"?
Dave Clarke