Unione infinita di R (Gennaio 2015)

Rispondi
Avatar utente
andrea.tosti
Messaggi: 15
Iscritto il: 02/10/2018, 9:20

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], 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.
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”