Insiemi ricorsivamente Enumerabili

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

cgiorgia_93
Salve volevo fare due domande che il Degano ha fatto all'orale e di cui non sono riuscita a dare una risposta esauriente:
1) Sia A un insieme r.e.
Esiste un j0 ⊆ A ricorsivo? Rispondere con opportuno esempio
Esiste un j1 ⊆ A r.e? Rispondere con opportuno esempio
Esiste un j2 ⊆ A co-r.e? Rispondere con opportuno esempio
2) Sia B un insieme r.e. e C ricorsivo
B\C è ricorsivo ? è r.e. ? è non r.e. ? Perché ?
Ringrazio anticipatamente per chi vorrà aiutarmi

MindFlyer
L'aiuto che ti darei è invitarti a ripassare le definizioni, perché non serve molto altro. Sono entrambi problemi estremamente semplici.
Se ci hai già provato e ti sei bloccata (o se vuoi una conferma che la tua soluzione sia corretta), scrivi il tuo approccio e vediamo come andare avanti. Ma spiattellarti una soluzione in mezza riga (perché non ci vuole più di mezza riga per problema) sarebbe inutile.

cgiorgia_93
Riguardando le definizioni mi sono accorta che il Degano non ne fornisce una precisa per gli insiemi non ricorsivamente enumerabili. Sai darmene una te, senza dover chiedere a lui?
comunque rispondendo alle domande
1) Sia A un insieme r.e.
Esiste un j0 ⊆ A ricorsivo? Si. l'insieme vuoto oppure l'insieme di un solo elemento
Esiste un j1 ⊆ A r.e? Si ad esempio se stesso
Esiste un j2 ⊆ A co-r.e? non lo so ma penso no ...
2)Sia B un insieme r.e. e C ricorsivo
B\C è ricorsivo ? No perchè B è ricorsivamente enumerabile e sappiamo per definizione di insieme r.e. che preso un elemento di B/C posso decidere se questo appartiene a B ma non posso decidere se non appartiene a B quindi non può essere ricorsivo
è r.e. ? Si
è non r.e. ? non lo so ...

MindFlyer
Banalmente, un insieme è non ricorsivamente enumerabile quando non è ricorsivamente enumerabile.
Esiste un j2 ⊆ A co-r.e? non lo so ma penso no ...
Il vuoto è co-r.e...
2)Sia B un insieme r.e. e C ricorsivo
B\C è ricorsivo ? No perchè B è ricorsivamente enumerabile e sappiamo per definizione di insieme r.e. che preso un elemento di B/C posso decidere se questo appartiene a B ma non posso decidere se non appartiene a B quindi non può essere ricorsivo
No, dipende dai casi. Per esempio, se B è non ricorsivo e C è vuoto, B\C è non ricorsivo. Ma se B è non ricorsivo e C è tutto N, allora B\C è vuoto, ergo ricorsivo.
è r.e. ? Si
Giusto, ma perché?
è non r.e. ? non lo so ...
Beh. Se al punto precedente dimostri che è r.e., hai automaticamente dimostrato che non può essere non r.e.

cgiorgia_93
nelle dispense del Degano trovo scritto questo che non riesco a capire:
"la scelta del nome non ricorsivamente enumerabile non è molto felice, perchè un insieme (ricorsivo è anche) ricorsivamente enumerabile è anche non ricorsivamente enumerabil

per il punto 2 se B/C è ricorsivamente enumerabile la risposta non puo essere quella che ho dato nel punto 1: perchè B è ricorsivamente enumerabile e sappiamo per definizione di insieme r.e. che preso un elemento di B/C posso decidere se questo appartiene a B ma non posso decidere se non appartiene a B quindi non può essere ricorsivo e quindi è r.e. :/

MindFlyer
nelle dispense del Degano trovo scritto questo che non riesco a capire
Ok, capisco il dubbio che hai. Questa mi sembra una delle tante cazzate delle dispense, e non le darei troppo peso. Forse Degano si confonde per esempio con gli automi deterministici, che sono anche automi non deterministici. Nel contesto degli automi e del nondeterminismo, la cosa ha senso. Ma nel nostro caso ci occupiamo di problemi meta-decisionali, ovvero di decidere se dei programmi decidono classi di altri programmi. Ora, se quello che dice Degano fosse vero, allora dire "linguaggio non r.e." sarebbe la stessa cosa che dire "linguaggio". A noi invece interessa molto stabilire quando un linguaggio non è r.e., e quindi ci fa comodo avere un nome per la classe dei linguaggi che non sono r.e. Nota anche che, secondo la sua "definizione", a qualunque esercizio che chieda se un dato insieme è non r.e., la risposta potrebbe essere solo sì. Quindi vedi bene che c'è qualcosa che non va.

Dovresti ignorare quella frase delirante, che è sicuramente stata frutto di un momento di confusione del povero Degano. Tant'è vero che in tutto il resto della dispensa "non r.e." è usato invece nel modo corretto, e cioè per intendere che un linguaggio non è r.e. (è riferito quasi sempre a [math]).
per il punto 2 se B/C è ricorsivamente enumerabile la risposta non puo essere quella che ho dato nel punto 1
Allora, ci sono tre cose che non vanno.

Primo, la risposta al punto 1 aveva dei problemi, come ho osservato sopra. B\C può essere talora ricorsivo, talora no. Quindi ragionare su quella risposta cercando di rispondere al punto 2 non ha senso.

Secondo, dire "non posso ragionare come al punto 1, quindi la conclusione del punto 1 è falsa" è un errore logico. La conclusione del punto 1 potrebbe essere vera, ma dimostrabile con ragionamenti diversi. Per esempio, io posso dimostrare che 463454 + 94912830 è un numero pari dicendo che è somma di due numeri pari. Se invece ho 3492789 + 2731947, la dimostrazione precedente non vale (perché i numeri non sono pari), ma questo non vuol dire che la somma non sia pari! La somma è ancora pari, ma la dimostrazione è diversa.

Terzo, dire "non può essere ricorsivo e quindi è r.e." non ha senso. Gli insiemi non ricorsivi possono anche essere non r.e. (per esempio il solito [math]).

Per risolvere il punto 2 devi dimostrare che B\C è r.e., e per farlo dovresti far vedere come semi-decidere B\C, supponendo che B sia semi-decidibile e C sia decidibile (qui uso le parole "semi-decidibile" e "decidibile" come sinonimi più intuitivi di "r.e." e "ricorsivo").
Immagina di avere un input e di dover semi-decidere se è in B\C. Se è in B\C, vuoi terminare dicendo "sì", e se non lo è vuoi non terminare. Hai a disposizione un programma che fa esattamente questa cosa per B, e un programma che invece decide completamente C, ovvero termina sempre con un sì o con un no. Come puoi usare questi due programmini per costruire il tuo?

cgiorgia_93
Abbiamo quindi due programmi:
il prima che termina se un elemento appartiene a B
il secondo se appartiene a C .
devo costruire un terzo programma che quando gli do un input si comporti come il primo programma e controlla se sta in B, Se la risposta e si allora controlla che non stia in C.. a questo punto restituisco 1 se l'input sta in B e non in C, 0 altrimenti . Scusami probabilmente avrò sbagliato e queste sono domande banalissime, ma mi perdo un sacco :(

MindFlyer
A grandi linee devi fare quello (anche perché c'è poco altro che si possa fare), ma la correttezza o meno della soluzione sta nei dettagli.

Diciamo che il programma B termina (con 1) se l'input è in B, altrimenti non termina.
Il programma C termina con 1 se l'input è in C, altrimenti termina con 0.
(Nota la differenza tra i due programmi: il secondo termina sempre, il primo no. Questo per definizione di r.e. e ricorsivo.)

Adesso costruiamo il programma per B\C.
Abbiamo un input x.
Simuliamo l'esecuzione di B su x.
Se l'esecuzione termina, simuliamo l'esecuzione di C su x.
Se il risultato è 0, terminiamo restituendo 1.
Altrimenti non terminiamo (e.g., cicliamo all'infinito senza fare niente).

Ovviamente il programma qui sopra è calcolabile, perché simula programmi calcolabili e procede oltre solo dopo che sono (eventualmente) terminati.

Vediamo perché questo programma semi-decide B\C. Abbiamo tre casi: x non è in B, x è in B e non in C, x è in B e in C.

* Se x non è in B, il programmino inizia a simulare B, e non termina mai. Questo è corretto, perché se x non è in B, non è neanche in B\C.

* Se x è in B e non in C, allora la simulazione di B termina, dichiarando che x è in B. Poi la simulazione di C termina con 0. A questo punto possiamo concludere che x è in B\C, e giustamente terminiamo restituendo 1.

* Se x è in B e in C, allora la simulazione di B termina, dichiarando che x è in B. Poi la simulazione di C termina con 1. A questo punto sappiamo che x non è in B\C, e giustamente non terminiamo (ciclando "apposta").

In tutti i casi, il programma termina se e solo se x è in B\C, e quindi semi-decide correttamente B\C, dimostrando che B\C è r.e. Non era necessario scrivere tutta questa roba in una soluzione... Bastavano un paio di righe, ma andavano dette le cose giuste in modo che fosse chiaro dove e come si stavano usando le ipotesi.

Per chiarire meglio la soluzione del problema 2, risolvi questo problema simile:

Siano B e C insiemi r.e.
B\C è ricorsivo? r.e.? Non r.e.?


Insomma lo stesso problema, ma con C r.e. anziché ricorsivo.

cgiorgia_93
scusami ma all'inizio hai detto che l'insieme vuoto è co-RE quindi non ricorsivamente enumerabile , ma non dovrebbe esserlo invece ? essendo l'insieme vuoto ricorsivo per il teorema che dice che se I è ricorsivo allora è r.e.?

MindFlyer
No, io ho solo detto che il vuoto è co-r.e.
Da quello dovevi dedurre che la risposta al quesito era sì.

andreRondo
Siano B e C insiemi r.e.
B\C è ricorsivo? r.e.? Non r.e.?
E' non-RE.
Per fare in modo che x stia in B/C, vuol dire che x deve stare in B (il programma B quindi termina) e che x non sta in C (ma questa cosa non si può fare in quanto, se x non sta in C, il programma C non termina)

MindFlyer
Per dire che un insieme non è RE, non basta far vedere che un particolare algoritmo non lo semi-decide. Bisogna far vedere che nessun algoritmo lo semi-decide. Per quanto l'intuizione sia corretta, come dimostrazione non regge.
Diamo una risposta più completa. A seconda di come si scelgono B e C ricorsivamente enumerabili, la loro differenza B\C può essere ricorsiva, RE e non ricorsiva, o non RE. Un esempio in cui è non RE è semplice: se B è tutto N e C è K, allora B\C è il complementare di K, che sappiamo essere non RE.
Rispondi

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