Toda linguagem decidível $L$ tem um subconjunto decidível infinito $S \subset L$ tal que $L \setminus S$ é infinito

Question

Dada uma linguagem decidível infinita $L$, então se $S \subconjunto L$ de tal modo que $L\setminus S$ é finito, então $S$ deve ser decidível.Isto é verdade, uma vez que dado um decisor de $L$ construímos um decisor para $S$:

Simular o decisor de $L$ na entrada, se aceitar, passe por cima $L\setminus S$ e verifique se está lá, se estiver, rejeite.Se não for aceite.Se o decisor de $L$ rejeita - rejeita.

Outro ponto é se $S \subconjunto L$ é finito então $S$ também deve ser decidível, é imediato que toda linguagem finita é decidível.

Agora temos o último caso em que $S$ é infinito e $L\setminus S$ é infinito.Sabemos que deve haver alguns subconjuntos $S$ correspondentes a este caso que são indecidíveis.Isto porque existem $\alef$ tal $S$ se apenas $\alef_0$ decisores.Denotar $D(L) = \{ S \subconjunto L :|S|= |L \setminus S|=\infty \wedge S ext{ é decidível} \}$

É verdade que para todas as linguagens infinitas decidíveis $L$ Nós temos $D(L) eq \phi$?

Se isso for verdade, então como conclusão teremos para todas as infinitas linguagens decidíveis $L$ uma sequência de linguagens decidíveis $L_n$ de tal modo que $L_0=L$ e $L_{n+1} \subconjunto L_n$ e $ | L_n setminus l_ {n+1} | = Infty $

Teremos também um limite definido $L_\infty = \{ e \in L :\forall n \in \mathbb{N} ext{ } e \in L_n \}$ e pode discutir se é vazio/finito/infinito e decicável ou não.

Esta parece ser uma boa maneira de estudar linguagens decidíveis, e curioso para saber se essa direção é realmente interessante e se existem artigos publicados sobre essas questões

Obrigado por qualquer ajuda

Answer 1

Se $L$ tem um alfabeto finito, então $L$ é recursivamente enumerável.

Então, a partir de tal enumeração $w_0,w_1,w_2,...$ das palavras de $L$ Tu podes levar $S=\{w_0,w_2,w_4,...\}$, que também será decidível.Para verificar se uma palavra $w$ é em $S$ verifique se está dentro $L$.Se for, então use a enumeração de $L$ para verificar se sua posição é par ou não.