Forum Informatica Unict

LAUREA MAGISTRALE => Teoria della Computabilità, 9 CFU => Topic started by: Mari_C on 27-05-2013, 17:27:50



Title: Un altro predicato
Post by: Mari_C on 27-05-2013, 17:27:50
Ciao raga  :-ciao
Che ne pensate di questa soluzione ???

Sia P(x)= " \phix(y) >=2 per ogni y tale che \phix(y) \downarrow  "
studiare la decidibilità e parziale decibilità di P e della sua negazione.
Soluzione:
\neg P(x)="\exist y [ \phix(y)\downarrow and  \phix(y) <2 ] "
\neg P(x)= ( \exist y ) ( \exist t ) ( \exist z )  ( S(x,y,z,t) and z<2 )
Accorpando sotto un'unica variabile ottengo:
\neg P(x)= ( \exist w ) ( S(x,(w1),(w3),(w2)) and (w3)<2 )
è parzialmente decidibile.

Studio l'indecibilità con Rice
A={ \phix : P(x) }
A \neq 0 poichè 2 \in A
A \neq C1 poichè 1 \in C1 ma  1 \notinA
Quindi A non è r.e \rightarrow P è indicidibile.

Grazie!!!!


Title: Re:Un altro predicato
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 27-05-2013, 21:10:17
30 e lode con bacio in fronte .wink!

Piccolissimissima, ma essenziale, osservazione sulla notazione:
si scrive (w)i e non (wi)!


Title: Re:Un altro predicato
Post by: nairi on 27-05-2013, 21:13:24
Quote
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  .wink


Title: Re:Un altro predicato
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ 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) C1\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.
NoNo
PARZ. DEC.No


Title: Re:Un altro predicato
Post by: nairi on 27-05-2013, 21:26:05
Quote
immagino tu (voi?) abbia(te?) fatto le corrette deduzioni, ma devi scriverle anche nell'ordine in cui le hai fatte:

 :[Emoticon] Asd: 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  :-ciao .......


Title: Re:Un altro predicato
Post by: Mari_C on 27-05-2013, 21:27:30
si si a volte negli esercizi che postiamo mancano le famose "tiritere"  8:-) ma le deduzioni che facciamo sono queste :yoh Grazie!


Title: Re:Un altro predicato
Post by: nairi on 27-05-2013, 22:35:59
ultimo predicato( per oggi ) :
Si studi la decidibilit`a e la parziale decidibilità del predicato
P(x) \equiv“|N \Wx| = 2”
e della sua negazione.

Soluzione:
Scrivo la negazione del predicato:
\negP(x)=“|N \Wx| \neq 2”
In particolare ho supposto che l'insieme contenesse almento tre elementi (ma non ne sono troppo sicura)
\negP(x)=(\existy1)(\existy2)(\existy3)(\existt):|{y1,y2,y3}|=3 \wedge H(x,y1,t)\wedge H(x,y2,t)\wedge H(x,y3,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={\phix : \negP(x)}
A\neq0  poichè la funzione 0\inA  (o anche \lambdax.0=0)
A\neqC1 poichè f\emptyset\inc1 ma  f\emptyset\notinA
Quindi A non è RE \rightarrow \negP(x) è indecidibile

Da questi risultati ricaviamo gli altri due ovvero P(x) non è pd nè d

è corretto?


Title: Re:Un altro predicato
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ 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.


Title: Re:Un altro predicato
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ 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 :nono), usa una di quelle .smile.

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 |-O!


Title: Re:Un altro predicato
Post by: nairi on 27-05-2013, 23:22:27
Quote
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  .wink !
 :-)L gli ultimi es sono sempre un disastro!!!!!!
Grazie ancora di tutto!


Title: Re:Un altro predicato
Post by: Mari_C on 29-05-2013, 21:07:33
Quote
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\inC1: \negP(x) }
Prendendo \sigma= f\empty \in A   esiste un estensione calcolabile di \sigma tale che |N \Wx| = 2 cioè una funzione che va in loop in esattamente due valori,
ad esempio come:
                    \uparrow se x=0 or x=1
f(x)=
                     x altrimenti
f(x) è calcolabile
Quindi {x |  \negP(x) } non è r.e \rightarrow  \negP(x) non è p.d

Ora studio A={x\inC1: 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 \rightarrow P(x) non è p.d

Nella tabellina riassuntiva:
                                 D                 PD
P                               No                No
\negP                             No                No

 .ciao


Title: Re:Un altro predicato
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ 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 (...\fs{3}x\in C_1...), però poi si usa \fs{3}x come se fosse un intero (...\fs{3}:\neg P(x)...)!

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 \fs{3}k\in A, allora \fs{3}\forall z:\phi_z=\phi_k valga \fs{3}z\in A, cioè che se esiste in A il codice k di un programma che calcola \fs{3}\phi_k, 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 :-OK, ma scriveteli bene :-)| :-)| :-)|( .arrossisco)

Quindi scrivete cose come: A=\{{\phi_x\in C_1\;:\;P(x)}\} oppure, più semplicemente visto che abbiamo già definito \fs{3}\phi_x=\phi_x^{\({1}\)}=f_{P_x}^{\({1}\)}, vi basta scrivere: A=\{{\phi_x\;:\;P(x)}\}

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. :-OK

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. |-O


Title: Re:Un altro predicato
Post by: Giuseppe Scollo 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 una 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 "Ex ⊆ Wx" 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.


Title: Re:Un altro predicato
Post by: Mari_C 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 una funzione con dominio infinito" .
...
.arrossisco Grazie mille!!!


Title: Re:Un altro predicato
Post by: nairi on 21-06-2013, 14:49:54
Ciao!!! sfrutto questo post per non invertarne 3000 nuovi  .applausi

Si studi la D e PD del predicato unario P(x)="Wx\subseteq{2n: n\in N}
Scrivo la negazione (mi piace di più  .smile )

\negP(x)="Wx\not\subseteq{2n: n\in N}

\negP(x)=\exists y1,t:( H(x,y1,t) \wedge "y1 dispari")

Accorpo in un'unica variabile:

\negP(x)=\exists w:( H(x,(w)1,(w)2) \wedge "(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={\phix\in C1: P(x)}

A\neq\empty poichè 0 \inA

A\neqC1 poichè f\empty \inC1 ma f\empty\notinA

Quindi {x|\negP(x)} non è ricorsivo \Rightarrow \negP(x) è indecidibile
   D    PD
P(x)    NO   No  
\negP(x) No   SI

è corretto? .whistling


Title: Re:Un altro predicato
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-06-2013, 15:08:57
è corretto? .whistling
Sì. Hai solo dimenticato di mettere una negazione davanti a P(x) quando definisci l'insieme A nelle righe:
Quote
Ora studio l'indecidibilità con Rice
A={
ϕx:P(x)}
:-OK


Title: Re:Un altro predicato
Post by: nairi on 21-06-2013, 15:39:23
merci  .arrossisco


Title: Re:Un altro predicato
Post by: Mari_C on 21-06-2013, 16:00:15
Si studi la decidibilità e parziale dec del predicato binario
P(x,y)= "la funzione \phix è una restrizione della funzione \phiy "

help help help! che significa? qualche suggerimento??  .penso



Title: Re:Un altro predicato
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-06-2013, 16:11:19
Si studi la decidibilità e parziale dec del predicato binario
P(x,y)= "la funzione \phix è una restrizione della funzione \phiy "

help help help! che significa? qualche suggerimento??  .penso


Devi fare riferimento alla parte di programma in cui si parla di "restrizioni" (finite o no) di altre funzioni, nozione propedeutica per almeno esporre l'enunciato del Teorema di Rice-Shapiro.

Semplicemente, date le funzioni f e g, diremo che f è restrizione di g se ∀x:f(x)↓ vale f(x)=g(x).
Ad esempio, la funzione mai definita f è restrizione di qualsiasi altra funzione, perché in ogni punto in cui è definita (cioè in nessuno :boh) la funzione assume gli stessi valori di qualsiasi altra funzione, mentre non ci dobbiamo preoccupare di capire cosa avviene a g quando f è non definita .nono.