Informateci

Joker
Sappiamo che R U R = R perchè entrambi si possono decidere in tempo finito. Cosa succede però con l'unione infinita di insiemi ricorsivi?

MindFlyer
Può essere sia ricorsiva che non ricorsiva.
Esempio: l'unione di {n} per ogni n naturale è ovviamente tutto [math]\mathbb N, e quindi ricorsivo.
D'altra parte, l'unione di {n}, per ogni n che appartiene a K è esattamente K, che non è ricorsivo.

Joker
Potrebbe essere anche non-RE (indecidibile)? Stavo pensando di fare lo stesso ragionamento con il complementare di K, ma non sarebbe possibile tirare fuori gli indici o mi sbaglio?

MindFlyer
No, invece puoi fare la stessa cosa con qualunque insieme. Insomma: siccome {n} è ricorsivo per qualunque n, puoi costruire qualunque insieme come unione (finita o infinita) di insiemi ricorsivi. "Tirare fuori gli indici" non è un problema, perché non stai cercando un algoritmo che costruisca questi insiemi, ma stai solo discutendo la loro esistenza.
In definitiva, come dico spesso, si tratta di un "problema troll" alla Degano.