Mostra che una lingua è re o ricorsiva

Question

Considera queste 2 lingue:

• $ L _ { ge5} = Left { Left <M Right>: m text {accetta almeno 5 stringhe} a destra } $

• $ L _ {<5} = Left { Left <M Right>: m text {accetta meno di 5 stringhe} a destra } $

Sono questi set ricorsivi, re o non re (lingue)?

Direi che non sono ricorsivi, in base alle applicazioni del teorema di Rice.

• Per il primo caso $ l_ {e} = left { left <m a destra>: l (m) = vuoto a destra } notin l _ { ge5} $ e $ l _ { ge5} $ sono non vuoto. Ad esempio, definisco $ l = Left { Left <M Right>: m text {accetta tutti i palindromi} a destra } $, che non è set limitato e accetta un numero infinito di stringhe.

• Per il secondo caso farei la stessa cosa. Ho $ l_ {e} = left { left <m a destra>: l (m) = vuoto a destra } in l _ {<5} $ e $ l = Left { Left < M Right>: m text {accetta tutti i palindromes} destro } notin l _ {<5} $

Quindi direi che entrambi non sono ricorsivi. Il mio ragionamento è corretto?

Ora sulla re delle lingue non ho un'idea di come posso dimostrarlo, questo dovrebbe essere l'inizio (se L non è re non può essere ricorsivo), come posso verificare se sono re o no ?

Dalla definizione: "$ l $ è $ iff $ esiste un tm $ m $ che accetta $ l $", quindi devo solo definire una TM che accetta ogni lingua?