Ogni lingua decidabile $ L $ ha un sottoinsieme decidabile infinito $ s \ sottoinsieme l $ tale che $ l \ setminus s $ è infinito

Question

Dato un linguaggio decidabile infinito $ l $ , quindi se $ s \ subset L $ tale $ l \ setminus s $ è finita, quindi $ s $ deve essere decidabile. Questo è vero da allora dato un decisore di $ l $ Contrapponiamo a una decisione per $ s $ : .

Simula il decisore di $ l $ sull'ingresso, se accetta, vai oltre $ l \ setminus s $ e controlla se è lì, se lo è, rifiutare. Se non è accettato. Se il decisore di $ l $ rifiuta - rifiutare.

Un altro punto è se $ s \ subset L $ è finita quindi $ s $ Deve anche essere decidabile, questo è immediato che ogni linguaggio finita è decidabile.

Ora abbiamo l'ultimo caso in cui $ s $ è infinita e $ l \ setminus s $ è infinito. Sappiamo che ci devono essere alcuni sottoinsiemi $ s $ corrispondente a questo caso che sono indecidenti. Questo è dal momento che ci sono $ \ Aleph $ tali $ s $ ma solo $ \ ALEPH_0 $ DECIDERS. Denota $ d (l)={s \ subset l: | s |= | l \ setminus s |=infty \ wedge s \ testo {è decidabile}} $ < / span>

è vero che per tutte le lingue decidabili infinite $ l $ abbiamo $ d (l) \ neq \ phi $ ?

Se questo è vero allora come conclusione avremo per tutte le lingue decidabili infinite $ l $ una sequenza di lingue decidabili $ L_n $ in modo tale che $ l_0= l $ e $ l_ {n + 1} \ sottoinsieme l_n $ e $ | l_n \ setminus l_ {n + 1} |=INFTY $

Avremo anche un set di limiti $ l_ \ infty={e \ in l: \ forall n \ in \ mathbb {n} \ testo {} e \ in L_n \} $ e può Dicuss se è vuoto / finito / infinito e decimabile o no.

Questo sembra un bel modo di studiare lingue decidabili e curiosi di sapere se questa direzione è davvero interessante e se ci sono articoli pubblicati su queste domande

Grazie per qualsiasi aiuto

Answer 1

se $ l $ ha un alfabeto finito, quindi $ l $ è ricorsivamente enumerabile.

.

Quindi, da tale enumerazione $ w_0, w_1, w_2, ... $ delle parole di $ l$ Puoi prendere $ s={w_0, w_2, w_4, ... \} $ , che sarà anche decidabile.Per verificare se una parola $ w $ è in $ s $ controlla se è in $ L $ .Se viene quindi utilizzato l'enumerazione della $ l $ per verificare se la sua posizione è pari o no.