Classificare insieme I={ x | #Wx = 1}

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

Ciao a tutti,
Chiedo aiuto per la risoluzione del seguente esercizio che era nello scritto di Luglio di Turini e che temo mi richiederà all'orale:

Classificare il seguente insieme:
I = { x | #Wx = 1}
dove # = cardinalità
Wx = dominio della funzione con indice x

Io sono arrivato a dire (spero giustamente) che essendo I un index set non banale esso è non ricorsivo per il teorema di Rice.
Non sono riuscito ad andare oltre e dire se I è RE o non RE.

Ogni input in merito è ben accetto ;)


MindFlyer
Pensandoci un attimo, vedi subito che intuitivamente non è RE. Per dimostrarlo, dovresti ridurre da qualche altro problema che sai non essere RE. Quali di questi problemi conosci?

Federico
Ciao e grazie mille per la risposta, posso chiederti come fai intuitivamente a capire che non è RE?

Penso che sia perché teoricamente presa una funzione andrebbero provati tutti gli input possibili per vedere che effettivamente converga solo per uno di essi e quindi abbia cardinalità del dominio = 1 giusto?

Per quanto riguarda problemi non RE abbiamo visto principalmente K complementare, ovvero l'insieme degli indici x tale che Fx(x) diverge.

Saresti spiegarmi come ridurre K complementare a questo insieme I?

Grazie mille

MindFlyer
Intuitivamente, è difficile sia capire che una funzione è nel tuo insieme, sia capire che non lo è. Per capire che è nel tuo insieme, non ti basta trovare un input su cui la funzione converga (se esiste, è una cosa che puoi scoprire in tempo finito), ma devi anche essere sicuro che non termini su tutti gli altri input (cosa che non puoi fare semplicemente simulandoli). D'altra parte, per capire che una funzione non è nel tuo insieme, dovresti o trovare almeno due input su cui converge (che è una cosa facile, se esistono), oppure essere sicuro che non termina su alcun input (cosa che invece non puoi fare).

Da questo ragionamento qualitativo, puoi già sospettare che l'insieme sia molto poco RE (ovvero, probabilmente non è RE nemmeno il complementare!).

Hai giustamente individuato un insieme (K complementare) che non è RE, ma penso che il candidato migliore per fare la riduzione sia un altro: l'insieme degli indici delle funzioni calcolabili che non terminano su alcun input (chiamiamolo NULL). Sai dimostrare che NULL è non RE (suggerimento: ragiona sul complementare...), e che inoltre NULL si riduce al tuo insieme?

Federico
intuitivamente mi torna, ma ho delle difficoltà (non sono un genio in questi ambiti più teorici/matematici purtroppo) nel formalizzarlo.

Dunque:
- Chiamo NULL = insieme degli indici delle funzioni ovunque indefinite
- Il complementare di NULL sarà dunque TOT = insieme degli indici delle funzioni totali (definite su ogni input)

- So dimostrare che K complementare si riduce a NULL
--> NULL è non RE

- A questo punto se riuscissi a ridurre NULL al mio insieme I potrei dire che anche I è non RE
Non riesco però a fare questa riduzione pur rendendomi conto che NULL e I sono molto simili.

Infatti NULL raccoglie gli indici delle funzioni indefinite per ogni input, mentre I quelli delle funzioni indefinite su ogni input fatta eccezione per un certo input.
Mi confonde il fatto che questo unico input su cui le funzioni di I sono definite non è lo stesso per tutte le funzioni (ad esempio y=10) ma può essere diverso per ciascuna funzione il cui indice è raccolto in I.

Se tu potessi aiutarmi a capire come ridurre NULL a I te ne sarei veramente grato! :D

MindFlyer
- Il complementare di NULL sarà dunque TOT = insieme degli indici delle funzioni totali (definite su ogni input)
Attenzione, il complemetnare di NULL non è TOT, ma è l'insieme degli indici di funzioni che sono definite su almeno un input (non necessariamente su tutti!).
- So dimostrare che K complementare si riduce a NULL
In che modo?
- A questo punto se riuscissi a ridurre NULL al mio insieme I potrei dire che anche I è non RE
Non riesco però a fare questa riduzione pur rendendomi conto che NULL e I sono molto simili.
Infatti NULL raccoglie gli indici delle funzioni indefinite per ogni input, mentre I quelli delle funzioni indefinite su ogni input fatta eccezione per un certo input.
Questo non importa, visto che le funzioni del tuo insieme puoi costruirle come vuoi! Nota che in una riduzione da A a B non devi costruire tutte le istanze di B. Ti basta che ogni istanza di A sia mandata in in una qualche istanza di B. Quindi, se non ti piace che le funzioni del tuo insieme siano definite su un unico input qualsiasi, puoi limitarti a considerare solo quelle che sono definite, diciamo, solo su input 0.

Ora fare la riduzione dovrebbe essere più facile...

Federico
Hai straragione, cretino io xD


Per mostrare che K compl. si riduce a NULL definirei una funzione F sfruttando il teo s-m-n che:
- diverge se x appartiene a K compl
- restituisca 12 se x non appartiene a K compl

In questo modo penso di poter affermare che:
- se x appartiene a K compl -> F diverge -> s(x) appartiene a NULL
- se x non appartiene a K compl -> F restituisce 12 -> s(x) non appartiene a NULL
--> K compl si riduce a NULL --> NULL è non r.e.

La funzione di riduzione di NULL a I dovrebbe quindi essere qualcosa del genere (ma dubito altamente che sia corretta o che abbia anche solo senso):
funzione F che
- diverge se x appartiene a NULL
- converge se x non appartiene a NULL e x=a (con ad esempio a=0)
- diverge se x non appartiene a NULL e x!=0

Mi dispiace abusare della tua disponibilità, come vedi ci capisco ben poco ahah

MindFlyer
Beh... Ricordo che le riduzioni dovrebbero essere funzioni ricorsive, e le tue non lo sono. Per esempio, come fai a controllare che x appartenga a K complementare? Non puoi mica farlo con una funzione ricorsiva! Stesso discorso per l'altra riduzione.

Cerca di costruire funzioni ricorsive che facciano quella riduzione.

Cioè, in verità per dimostrare che NULL è non RE non occorre fare riduzioni, ma conviene seguire il mio consiglio iniziale, ovvero ragionare sul complementare di NULL.

Altro suggerimento: mostra che sia NULL che il complementare non sono ricorsivi, e ricorda il teorema che dice che, se un insieme e il suo complementare sono RE, allora...

Prima che sia troppo tardi, posto uno sketch di soluzione.

1) NULL e il complementare non sono ricorsivi, per il teorema di Rice.

2) Il complementare di NULL è RE. Infatti, se una funzione non è in NULL (ovvero se è definita su almeno un input), possiamo scoprirlo in tempo finito simulandola su ogni input un passo alla volta "a spina di pesce", finché un'esecuzione termina.

3) NULL non è RE. Infatti, se lo fosse, sia NULL che il suo complementare sarebbero RE, e quindi sarebbero ricorsive, il che contraddirebbe il punto 1.

4) L'insieme I dell'esercizio è non RE per riduzione da NULL. Data una funzione calcolabile f (sotto forma di indice), costruiamo (l'indice di) una funzione f', che su input x fa le seguenti cose:

se x=0, f' termina (con un output qualsiasi);
se x>0, f' simula f su input x-1.

Questa riduzione è calcolabile: intuitivamente, c'è un algoritmo che, dato il "programma" di f, scrive il "programma" di f'.
Inoltre, se f è in NULL, allora f non termina su alcun input, e quindi f' termina solo su input 0, e quindi f' è in I.
Viceversa, se f non è in NULL, allora termina su almeno un input x, il che significa che f' termina almeno sugli input 0 e x+1, e quindi f' non è in I.
Rispondi

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