Tengo problemas con este problema, sé que todo lenguaje decidible es recursivamente enumerable pero que no todo lenguaje recursivamente enumerable es decidible.
¿Qué pasos hay que seguir para averiguar qué lenguaje recursivamente enumerable es decidible?
Supongamos que E es un alfabeto y que E* se divide en n lenguajes disjuntos L1, L2...,Ln. Si son recursivamente enumerables, demuestre que también son decidibles.
Me gusta la respuesta de Quinn Culver. Sin embargo, quiero ampliarla. Un lenguaje L es decidible si y sólo si L y $\overline{L}$ son ambos recursivamente enumerables. La prueba de esto es por simulación. Consideremos la cadena $\omega$ . Sea $M, \overline{M}$ sean máquinas de Turing que acepten $L, \overline{L}$ respectivamente. Simulamos $M, \overline{M}$ en $\omega$ . Sabemos que $\omega$ está exactamente en uno de estos conjuntos. Así que al menos una de las dos máquinas de Turing se detendrá. Si $M$ se detiene en el estado de aceptación, $\omega \in L$ . Por lo demás, $\overline{M}$ se detendrá en el estado de aceptación, lo que implica que $\omega \in \overline{L}$ .
Los lenguajes decidibles se cierran bajo unas pocas operaciones, como la unión de conjuntos, la intersección de conjuntos, la complementación de conjuntos, la concatenación de cadenas y el cierre de Kleene. Si recuerdas haber tratado problemas en los que se te pedía que decidieras si un lenguaje es regular, la lógica de la decidibilidad es bastante similar.
El siguiente enlace es un buen recurso para leer algo más sobre el tema.
http://www.dreamincode.net/forums/topic/338311-turing-machines-and-formal-languages/
Espero que esto ayude.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
