Mari_C
Apprendista Forumista

Offline
Posts: 240
"SmiiiiLe"
|
 |
« on: 27-05-2013, 17:27:50 » |
|
Ciao raga  Che ne pensate di questa soluzione  Sia P(x)= " x(y) >=2 per ogni y tale che x(y)  " studiare la decidibilità e parziale decibilità di P e della sua negazione. Soluzione:  P(x)="  y [ x(y)  and x(y) <2 ] "  P(x)= (  y ) (  t ) (  z ) ( S(x,y,z,t) and z<2 ) Accorpando sotto un'unica variabile ottengo:  P(x)= (  w ) ( S(x,(w 1),(w 3),(w 2)) and (w 3)<2 ) è parzialmente decidibile. Studio l'indecibilità con Rice A={ x : P(x) } A  0 poichè 2  A A  C 1 poichè 1  C 1 ma 1  A Quindi A non è r.e  P è indicidibile. Grazie!!!!
|
|
|
Logged
|
|
|
|
ɹǝǝuıƃuǝsɹǝʌǝɹ
|
 |
« Reply #1 on: 27-05-2013, 21:10:17 » |
|
30 e lode con bacio in fronte  ! Piccolissimissima, ma essenziale, osservazione sulla notazione: si scrive (w)i e non (wi)!
|
|
|
Logged
|
La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.
In tutto, amare e servire.
✚ | ن | I can deal with ads, I can deal with buffer, but when ads buffer I suffer... |
...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda... ▶ YouTube ❾ 9GAG ⅱ anobii S Steam ☺ T.B.o.I. Wiki [ ] Lezioni private ʼ Albo d'Ateneo Unicode 3.0.1
|
|
|
nairi
Apprendista Forumista

Offline
Posts: 185
|
 |
« Reply #2 on: 27-05-2013, 21:13:24 » |
|
Piccolissimissima, ma essenziale, osservazione sulla notazione: si scrive (w)i e non (wi)! hai ragione! è stata una svista durante la copiatura! lo scriviamo bene per fortuna!!!!! Grazie per il voto.... magari fosse vero!!!!!! Vediamo se con altri es ci smentiamo... ora ne posto qualcuno 
|
|
|
Logged
|
|
|
|
ɹǝǝuıƃuǝsɹǝʌǝɹ
|
 |
« Reply #3 on: 27-05-2013, 21:20:28 » |
|
Altra nota sulla procedura da esibire per le deduzioni: immagino tu (voi?) abbia(te?) fatto le corrette deduzioni, ma devi scriverle anche nell'ordine in cui le hai fatte: Il fatto che A non è r.e. lo capisci perché avvengono le seguenti due cose 1) A non è ricorsivo (P non è decidibile, quindi anche ¬P è indecidibile) e questo lo capisci con il teorema di Rice 2) C 1\A (cioè il complementare di A) è ricorsivamente enumerabile (¬P è parzialmente decidibile) Una volta che sai che ¬P è non-decidibile, ma parzialmente decidibile, allora, dei due (P o ¬P), è necessariamente P ad essere non-parzialmente decidibile. È utile riempire la tabella quadrata solita, dove scrivi sulle colonne P e ¬P, e nelle righe DEC. e PARZ. DEC. e la riempi(te?) con Sì o No a seconda se l'intersezione è vera o no In questo caso, la tabella sarebbe così: | P | ¬P | DEC. | No | No | PARZ. DEC. | No | Sì |
|
|
|
Logged
|
La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.
In tutto, amare e servire.
✚ | ن | I can deal with ads, I can deal with buffer, but when ads buffer I suffer... |
...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda... ▶ YouTube ❾ 9GAG ⅱ anobii S Steam ☺ T.B.o.I. Wiki [ ] Lezioni private ʼ Albo d'Ateneo Unicode 3.0.1
|
|
|
nairi
Apprendista Forumista

Offline
Posts: 185
|
 |
« Reply #4 on: 27-05-2013, 21:26:05 » |
|
immagino tu (voi?) abbia(te?) fatto le corrette deduzioni, ma devi scriverle anche nell'ordine in cui le hai fatte: ![[Emoticon] Asd](http://forum.informatica.unict.it/Smileys/asd/[Emoticon] Asd.gif) si si!!!! la cosa su cui ci concentriamo per ora (e che scriviamo sul forum tralasciando il resto) è l'impostazione, perchè sbagliata quella il resto dell'es va tutto a rotoli! ovviamente per ogni tipologia di es facciamo le giuste deduzioni!! Grazie per le tue attenzioni!!!! Ps: noi  .......
|
|
|
Logged
|
|
|
|
Mari_C
Apprendista Forumista

Offline
Posts: 240
"SmiiiiLe"
|
 |
« Reply #5 on: 27-05-2013, 21:27:30 » |
|
si si a volte negli esercizi che postiamo mancano le famose "tiritere"  ma le deduzioni che facciamo sono queste  Grazie!
|
|
|
Logged
|
|
|
|
nairi
Apprendista Forumista

Offline
Posts: 185
|
 |
« Reply #6 on: 27-05-2013, 22:35:59 » |
|
ultimo predicato( per oggi ) : Si studi la decidibilit`a e la parziale decidibilità del predicato P(x)  “|N \W x| = 2” e della sua negazione. Soluzione: Scrivo la negazione del predicato:  P(x)=“|N \W x|  2” In particolare ho supposto che l'insieme contenesse almento tre elementi (ma non ne sono troppo sicura)  P(x)=(  y 1)(  y 2)(  y 3)(  t):|{y 1,y 2,y 3}|=3  H(x,y 1,t)  H(x,y 2,t)  H(x,y 3,t) è P.D. (bisogna dedurlo dicendo che le varie parti sono d e che infine con il quantificatore esistenziale è pd in breve) Domanda bisogna necessariamente accorpare le variabili in una o è solo una questione di eleganza? Cmq non ci vuole molto a farlo :p Andando avanti studi l'indecidibilità con Rice Sia A={ x :  P(x)} A  0 poichè la funzione 0 A (o anche  x.0= 0) A  C 1 poichè f   c 1 ma f   A Quindi A non è RE  P(x) è indecidibile Da questi risultati ricaviamo gli altri due ovvero P(x) non è pd nè d è corretto?
|
|
|
Logged
|
|
|
|
ɹǝǝuıƃuǝsɹǝʌǝɹ
|
 |
« Reply #7 on: 27-05-2013, 22:56:53 » |
|
È esattamente il contrario di come hai capito tu, quando hai scritto ¬P.
La scrittura P(x) ≡ "|N\Wx|=2" indica il predicato che è vero quando Φx va in loop in esattamente due valori.
La scrittura ¬P(x) ≡ "|N\Wx|≠2" indica il predicato che è vero quando Φx va in loop in esattamente 0 (cioè mai) oppure esattamente 1 oppure almeno 3 valori.
Se ci pensi, se ti venisse dato un x che rende vero P oppure ¬P, verificare ciascuno dei due predicati richiederebbe un lavoro infinito: - nel caso di P, perché dovresti dimostrare che esistono esattamente due valori (facile) in cui dopo qualsiasi numero di passi (lavoro infinito!) la computazione non è ancora terminata! - nel caso di ¬P, perché dovresti dimostrare che: - la funzione non va mai in loop (provare che per tutti i valori termina, tutti? lavoro infinito!) OPPURE - la funzione va in loop in un solo punto (dimostrare già questo è un lavoro infinito, ma anche vedendola nel modo equivalente che in infiniti punti -tranne uno- la funzione termina, è sempre un lavoro infinito!) OPPURE - la funzione va in loop in almeno 3 punti (stesso problema preciso di verificare che vale per 2, cioè P)
Intuiamo, quindi, che sia P sia ¬P sono non-parzialmente decidibili.
Per dimostrare che sia P sia ¬P sono non-parzialmente decidibili, c'è solo un modo! Bisogna applicare il Teorema di Rice-Shapiro sia a P sia a ¬P.
Provate a fare questo.
|
|
|
Logged
|
La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.
In tutto, amare e servire.
✚ | ن | I can deal with ads, I can deal with buffer, but when ads buffer I suffer... |
...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda... ▶ YouTube ❾ 9GAG ⅱ anobii S Steam ☺ T.B.o.I. Wiki [ ] Lezioni private ʼ Albo d'Ateneo Unicode 3.0.1
|
|
|
ɹǝǝuıƃuǝsɹǝʌǝɹ
|
 |
« Reply #8 on: 27-05-2013, 23:02:27 » |
|
Domanda: bisogna necessariamente accorpare le variabili in una o è solo una questione di eleganza? Cmq non ci vuole molto a farlo :p A lezione, vi è stato spiegato solo un modo di dimostrare la parziale decidibilità di predicati che si basano su esistenziale applicato a predicato decidibile. Se conosci altre dimostrazioni (un numero infinito di dimostrazioni! visto che non sai mai quante sono le variabili in gioco  ), usa una di quelle  . Ovviamente è sarcasmo: dovete usare quello che vi è stato spiegato, cioè a usare l'esistenziale con una sola variabile, perché se ricordate la dimostrazione costruttiva si basa sul fatto che tale possibilità è garantita dall'operatore di minimalizzazione: infatti, dimostrare l'esistenza di una certo valore per una variabile per cui un certo predicato decidibile è vero EQUIVALE a cercare tale valore tramite una minimalizzazione non-limitata su quella stessa variabile applicata allo stesso predicato decidibile, che itera da 0 a infinito finché non lo trova (se esiste lo trova e termina, se non esiste non può trovarlo e va in loop, da cui la sola parziale decidibilità, non necessariamente totale). Non avete mai introdotto una minimalizzazione su più variabili, e siccome una tale minimalizzazione si può ricondurre a quella a una sola tramite gli opportuni accorpamenti, usate quelli  !
|
|
|
Logged
|
La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.
In tutto, amare e servire.
✚ | ن | I can deal with ads, I can deal with buffer, but when ads buffer I suffer... |
...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda... ▶ YouTube ❾ 9GAG ⅱ anobii S Steam ☺ T.B.o.I. Wiki [ ] Lezioni private ʼ Albo d'Ateneo Unicode 3.0.1
|
|
|
nairi
Apprendista Forumista

Offline
Posts: 185
|
 |
« Reply #9 on: 27-05-2013, 23:22:27 » |
|
Non avete mai introdotto una minimalizzazione su più variabili, e siccome una tale minimalizzazione si può ricondurre a quella a una sola tramite gli opportuni accorpamenti, usate quelli Sei stato chiarissimo grazie!!! Sull'ultimo es sono un po' confusa... ora leggendo con la tua spiegazione ho capito la "cantonata" presa nell'interpretazione.... devo stare molta attenta! domani a mente fresca svolgerò l'es seguendo le tue indicazioni e vediamo che succede  !  gli ultimi es sono sempre un disastro!!!!!! Grazie ancora di tutto!
|
|
|
Logged
|
|
|
|
Mari_C
Apprendista Forumista

Offline
Posts: 240
"SmiiiiLe"
|
 |
« Reply #10 on: 29-05-2013, 21:07:33 » |
|
Si studi la decidibilit`a e la parziale decidibilità del predicato P(x) = “|N \Wx| = 2” e della sua negazione. Vediamo se ho capito bene durante il ricevimento di oggi, Considero A={x  C 1:  P(x) } Prendendo  = f  A esiste un estensione calcolabile di  tale che |N \Wx| = 2 cioè una funzione che va in loop in esattamente due valori, ad esempio come:  se x=0 or x=1 f(x)= x altrimenti f(x) è calcolabile Quindi {x |  P(x) } non è r.e  P(x) non è p.d Ora studio A={x  C 1: P(x) } A non contiene alcuna funzione con dominio finito ,cioè non può esistere una restrizione finita di un dominio infinito Quindi {x | P(x) } non è r.e  P(x) non è p.d Nella tabellina riassuntiva: D PD P No No P No No .ciao
|
|
« Last Edit: 03-06-2013, 17:03:27 by Mari_C »
|
Logged
|
|
|
|
ɹǝǝuıƃuǝsɹǝʌǝɹ
|
 |
« Reply #11 on: 29-05-2013, 22:00:16 » |
|
Bene. L'impostazione è corretta. Alcune note: Per come è scritto A sembra essere un insieme di funzioni calcolabili unarie (...  ...), però poi si usa  come se fosse un intero (... ) ...)! Dovete fare molta attenzione a questi dettagli: o scegliete di dimostrare la non ricorsiva-enumerabilità di insiemi di funzioni calcolabili unarie (cosa che suggerisco caldamente), oppure (equivalentemente) scegliete di dimostrare la non ricorsiva-enumerabilità di insiemi di codici di programmi che calcolano funzioni unarie, ma a patto che tale insieme sia estensivo (nel senso che se  , allora  valga  , cioè che se esiste in A il codice k di un programma che calcola  , allora A deve contenere i codici z di TUTTI gli altri programmi che calcolano la stessa funzione!). Come vedete, troppo stress... limitatevi a considerare insiemi di funzioni calcolabili unarie  , ma scriveteli bene  (  ) Quindi scrivete cose come: }\}) oppure, più semplicemente visto che abbiamo già definito }=f_{P_x}^{\({1}\)}) , vi basta scrivere: }\}) Il teorema di Rice-Shapiro, poi, afferma che se un insieme è r.e., allora esso è esprimibile come unione di un certo numero (finito o infinito) di "coni" che "si basano" su vertici che sono funzioni con dominio finito. In effetti, se non ci sono, all'interno dell'insieme, funzioni con dominio finito, allora è impossibile che sia r.e.  Ma se aveste voluto sfruttare esplicitamente uno dei due Corollari al Teorema di Rice-Shapiro, potevate esibire una funzione (evidentemente con dominio infinito) che fa parte dell'insieme considerato, e dimostrare che, per ogni sua restrizione finita (possibile candidato a essere "base" del "cono" o "dei coni" che contiene la funzione esibita), tale restrizione finita non appartiene all'insieme stesso: in questo caso, ogni restrizione finita di qualsiasi funzione (a maggior ragione, le restrizioni finite della funzione esibita), non fa parte dell'insieme, giacché non ne contiene, perciò avete centrato l'obiettivo del Corollario, e dimostrato che quell'insieme non è r.e. 
|
|
|
Logged
|
La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.
In tutto, amare e servire.
✚ | ن | I can deal with ads, I can deal with buffer, but when ads buffer I suffer... |
...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda... ▶ YouTube ❾ 9GAG ⅱ anobii S Steam ☺ T.B.o.I. Wiki [ ] Lezioni private ʼ Albo d'Ateneo Unicode 3.0.1
|
|
|
Giuseppe Scollo
|
 |
« Reply #12 on: 30-05-2013, 00:43:53 » |
|
Bene. L'impostazione è corretta.
Sostanzialmente sì, ma sono da correggere: 1) la svista sul fatto che A dovrebbe essere un insieme di funzioni (calcolabili), non l'insieme dei loro codici, che sono numeri, 2) l'argomento: "non può esistere una restrizione finita di un dominio infinito" è impreciso, andrebbe precisato così: "non può esistere in A una restrizione finita di un a funzione con dominio infinito" . È invece del tutto corretta la conclusione "{x | ¬P(x) } non è r.e.", che viene tratta usando la contrapositiva del teorema di Rice-Shapiro, e qui devo invece correggere il suggerimento: o scegliete di dimostrare la non ricorsiva-enumerabilità di insiemi di funzioni calcolabili unarie perché nella terminologia di riferimento (quella del testo di Cutland) la ricorsività e l'enumerabilità ricorsiva sono proprietà di sottoinsiemi di ℕ, non di insiemi di funzioni. È vero cha la terminologia si può generalizzare, ma nei limiti di ciò che si è studiato tale generalizzazione non è considerata. Infatti, nell'enunciato del teorema di Rice-Shapiro come proposto nel testo di Cutland, dall'ipotesi che l'insieme di funzioni (unarie calcolabili) A abbia insieme di codici r.e., ovvero che {x | φ x ∊ A} sia r.e., consegue la tesi che valga la ben nota doppia implicazione relativa all'appartenza di funzioni all'insieme A. La connessione con la semidecidibilità di predicati viene semplicemente dalla definizione di enumerabilità ricorsiva: un sottoinsieme di ℕ è r.e. sse il suo predicato di appartenza è s.d.; perciò, nell'uso del teorema di Rice-Shapiro, è lecito sostituire l'insieme {x | φ x ∊ A} con l'insieme {x | P(x) } purché P(x) sia il predicato di appartenza (di numeri) all'insieme dei codici di funzioni in A; questa condizione ovviamente implica che tale insieme di codici sia estensivo. Ora, in pratica, i predicati di cui si propone di studiare la (semi)decidibilità in questa tipologia di esercizi caratterizzano sempre insiemi estensivi di codici (questo lo si vede subito dalla forma del predicato, per esempio un predicato quale "E x ⊆ W x" caratterizza l'"insieme dei codici x di funzioni unarie calcolabili la cui immagine è inclusa nel dominio", la cui estensività è ovvia). In conclusione, vale la pena affrontare questo tipo di esercizi concentrandosi inizialmente sul significato del predicato, nel senso di stabilire subito una risposta a questa domanda: quale classe di funzioni è caratterizzata "via insieme dei codici" dal predicato? Cioè: letteralmente, il predicato caratterizza un insieme di numeri, ma questo è l'insieme dei codici di una classe di funzioni... quali funzioni ci stanno? Quali non possono starci? Dopodiché, se si hanno buone ragioni di sospettare che il predicato non sia s.d., occorre solo mostrare che la suddetta doppia implicazione è falsa per la classe in questione, così come esemplificato nella soluzione di questo esercizio.
|
|
|
Logged
|
|
|
|
Mari_C
Apprendista Forumista

Offline
Posts: 240
"SmiiiiLe"
|
 |
« Reply #13 on: 30-05-2013, 21:26:13 » |
|
Bene. L'impostazione è corretta.
Sostanzialmente sì, ma sono da correggere: 1) la svista sul fatto che A dovrebbe essere un insieme di funzioni (calcolabili), non l'insieme dei loro codici, che sono numeri, 2) l'argomento: "non può esistere una restrizione finita di un dominio infinito" è impreciso, andrebbe precisato così: "non può esistere in A una restrizione finita di un a funzione con dominio infinito" . ...  Grazie mille!!!
|
|
|
Logged
|
|
|
|
nairi
Apprendista Forumista

Offline
Posts: 185
|
 |
« Reply #14 on: 21-06-2013, 14:49:54 » |
|
Ciao!!! sfrutto questo post per non invertarne 3000 nuovi  Si studi la D e PD del predicato unario P(x)="W x {2n: n  N} Scrivo la negazione (mi piace di più  )  P(x)="W x {2n: n  N}  P(x)=  y 1,  : ( H(x,y 1,t)  "y 1 dispari") Accorpo in un'unica variabile:  P(x)=  w:( H(x,(w) 1,(w) 2)  "(w) 1 dispari") è PD perchè H(...) è un predicato decidibile, "..." è un predicato decidibile, l'and tra predicati D è D, l'esistenziale di predicati D dà luogo a predicati PD Ora studio l'indecidibilità con Rice A={ x C 1: P(x)} A   poichè 0  A A  C 1 poichè f  C 1 ma f   A Quindi {x|  P(x)} non è ricorsivo  P(x) è indecidibile D PD P(x) NO No  P(x) No SIè corretto? 
|
|
« Last Edit: 21-06-2013, 15:04:05 by reversengineer »
|
Logged
|
|
|
|
|