Il Principio di Riduzione

Calcolabilità, modelli di calcolo, complessità, linguaggi formali.

Il Principio di Riduzione

Messaggioda Nihilus il mar 20 gen 2015, 17:31

Dimostrare il cosiddetto Principio di Riduzione:
dati due insiemi ricorsivamente enumerabili $X$ e $Y$ con almeno due elementi ciascuno, esistono dei sottoinsiemi ricorsivamente enumerabili $\hat X \subseteq X$ e $\hat Y \subseteq Y$, disgiunti, tali che $X \cup Y = \hat X \cup \hat Y$.

Sotto un suggerimento.
Una buona idea è definire $\hat X$ e $\hat Y$ come approssimazioni ricorsivamente enumerabili di $X \setminus Y$ e $Y \setminus X$ rispettivamente.
Cadi e non c'è nulla cui aggrapparti; cadi e la libertà è non trattenersi. Che perfezione...
Avatar utente
Nihilus
 
Messaggi: 102
Iscritto il: sab 22 set 2012, 14:05

Torna a Fondamenti dell'Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron