Pages: [1] 2   Go Down
Print
Author Topic: Un altro predicato  (Read 4311 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Mari_C
Apprendista Forumista
**
Offline Offline

Posts: 240


"SmiiiiLe"


« on: 27-05-2013, 17:27:50 »

Ciao raga  ciao
Che ne pensate di questa soluzione Huh?

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!!!!
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.453


Più grande è la lotta, e più è glorioso il trionfo


WWW
« 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 [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #2 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 
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.453


Più grande è la lotta, e più è glorioso il trionfo


WWW
« 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) 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
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 [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #4 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 .......
Logged
Mari_C
Apprendista Forumista
**
Offline 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"  girl ma le deduzioni che facciamo sono queste yoh Grazie!
Logged
nairi
Apprendista Forumista
**
Offline 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) \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?
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.453


Più grande è la lotta, e più è glorioso il trionfo


WWW
« 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 [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.453


Più grande è la lotta, e più è glorioso il trionfo


WWW
« 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 nono), 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 univ!
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 [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #9 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  !
 no gli ultimi es sono sempre un disastro!!!!!!
Grazie ancora di tutto!
Logged
Mari_C
Apprendista Forumista
**
Offline Offline

Posts: 240


"SmiiiiLe"


« Reply #10 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
« Last Edit: 03-06-2013, 17:03:27 by Mari_C » Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.453


Più grande è la lotta, e più è glorioso il trionfo


WWW
« 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 (...\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 testate testate testate( )

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. univ
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 [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Giuseppe Scollo
Moderator
Forumista Esperto
*****
Offline Offline

Posts: 1.389


« 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 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.
Logged
Mari_C
Apprendista Forumista
**
Offline 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 una funzione con dominio infinito" .
...
Grazie mille!!!
Logged
nairi
Apprendista Forumista
**
Offline 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)="Wx\subseteq{2n: n\in N}
Scrivo la negazione (mi piace di più   )

\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?
« Last Edit: 21-06-2013, 15:04:05 by reversengineer » Logged
Pages: [1] 2   Go Up
Print
Jump to: