Cada lenguaje decidible $ L $ tiene un subconjunto decidible infinito $ s \ subconjunto L $ de manera que $ l \ setminus s $ es infinito

Question

Dado un lenguaje decidible infinito $ l $ , luego, si $ s \ subconjunto l $ tal que $ l \ setminus s $ es finito, luego $ s $ debe ser decidible. Esto es cierto, ya que se le da un decidido de $ l $ Contrito un decidero para $ s $ :

Simular el decidido de $ l $ en la entrada, si acepta, vaya a $ l \ setminus s $ y verifique si está ahí, si lo es, rechazar. Si no se acepta. Si el decidido de $ l $ rechazos - Rechazar.

Otro punto es si $ s \ subset l $ es finito y luego $ s $ también debe ser Decidible, esto es inmediato que cada lenguaje finito es decidible.

Ahora tenemos el último caso donde $ s $ es infinito y $ l \ setminus s $ es infinito. Sabemos que debe haber algunos subconjuntos $ s $ correspondientes a este caso que no son decidibles. Esto es que hay desde $ \ aleph $ dicho $ s $ pero solo $ \ aleph_0 $ decididores. Denote $ d (l)={s \ subconjunto L: | s | s |= | l \ setminus s |=infty \ wedge s \ text {es decidible} \} $ < / span>

es cierto que para todos los idiomas decidibles infinitos $ l $ tenemos $ d (l) \ neq \ phi $ ?

Si esto es cierto, entonces, como conclusión, tendremos para todos los idiomas decidibles infinitos $ l $ una secuencia de idiomas decidibles $ L_n $ de tal que $ l_0= l $ y $ l_ {n + 1} \ subconjunto l_n $ y $ | l_n \ setminus l_ {n + 1} |=INFTY $

También tendremos un límite establecido $ l_ \ infty={e \ in l: \ forall n \ in \ mathbb {n} \ texto {} e \ in L_n \} $ y puede DICUSS si está vacío / finito / infinito y descicable o no.

Esto parece ser una forma agradable de estudiar idiomas decidibles, y curiosos por saber si esta dirección es realmente interesante y si hay artículos publicados con respecto a estas preguntas

Gracias por cualquier ayuda

Answer 1

Si $ l $ tiene un alfabeto finito, luego $ l $ es recursivamente enumerable.

Luego, de tal enumeración $ W_0, W_1, W_2, ... $ de las palabras de $ l$ Puede tomar $ s={w_0, w_2, w_4, ... \} $ , que también será decidible.Para comprobar si una palabra $ w $ está en $ s $ Compruebe si está en $ l $ .Si es así, use la enumeración de $ l $ para verificar si su posición es incluso o no.