Un altro predicato

[Mari_C]

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₁),(w₃),(w₂)) and (w₃)<2 )
è parzialmente decidibile.

Studio l'indecibilità con Rice
A={ _x : P(x) }
A 0 poichè 2 A
A C₁ poichè 1 C₁ ma  1 A
Quindi A non è r.e P è indicidibile.

Grazie!!!!

[ɹǝǝuıƃuǝsɹǝʌǝɹ]

30 e lode con bacio in fronte !

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

[nairi]

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 

[ɹǝǝuıƃuǝsɹǝʌǝɹ]

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₁\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ì

[nairi]

immagino tu (voi?) abbia(te?) fatto le corrette deduzioni, ma devi scriverle anche nell'ordine in cui le hai fatte:

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

[Mari_C]

si si a volte negli esercizi che postiamo mancano le famose "tiritere"  ma le deduzioni che facciamo sono queste Grazie!

[nairi]

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₁)(y₂)(y₃)(t):|{y₁,y_2,y₃}|=3 H(x,y₁,t) H(x,y₂,t) H(x,y₃,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)}
A0  poichè la funzione 0A  (o anche x.0=0)
AC₁ poichè fc₁ ma  fA
Quindi A non è RE P(x) è indecidibile

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

è corretto?

[ɹǝǝuıƃuǝsɹǝʌǝɹ]

È esattamente il contrario di come hai capito tu, quando hai scritto ¬P.

La scrittura P(x) ≡ "|N\W_x|=2" indica il predicato che è vero quando Φ_x va in loop in esattamente due valori.

La scrittura ¬P(x) ≡ "|N\W_x|≠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.

[ɹǝǝuıƃuǝsɹǝʌǝɹ]

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 !

[nairi]

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!

[Mari_C]

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={xC₁: 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={xC₁: 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

[ɹǝǝuıƃuǝsɹǝʌǝɹ]

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

[Giuseppe Scollo]

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

[Mari_C]

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

[nairi]

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₁,:( H(x,y₁,t) "y₁ dispari")

Accorpo in un'unica variabile:

P(x)= w:( H(x,(w)₁,(w)₂) "(w)₁ 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₁: P(x)}

A poichè 0 A

AC₁ poichè f C₁ ma fA

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

è corretto?