Forum Informatica Unict

LAUREA MAGISTRALE => Teoria della Computabilità, 9 CFU => Topic started by: nairi on 17-06-2013, 21:51:48



Title: alcuni esercizi misti!
Post by: nairi on 17-06-2013, 21:51:48
Ciao!!! posto qui qualche esercizio fatto oggi per vedere se sono giusti o no, dato che mi sono arruginita xD ....

Ecco il primo:
Si stabilisca se la seguente funzione è calcolabile:
           x    se x\in  Wy\bigcapEy
f(x,y)=\uparrow  altrimenti

Soluzione:

f(x,y)=x\cdot 1[\muz(H(y,x,z) \wedge S(y,x,x,z))]

è calcolabile perchè i predicati H(...) ed S(...) sono calc;
l'and tra predicati calc è calc;
l'operatore di minimalizzazione applicato a funz calc è calc;
la moltiplicazione con la funz cost unaria è calc e anche quella per x
Quindi calcolabile!
è giusto? Anche se l'ho scritto in breve vorrei porre un po' d'attenzione sulla famosa "tiritera" che faccio sempre a voce ed ho paura che a farci l'abitudine poi sbaglio con i termini!

grazie ;)


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 17-06-2013, 23:03:25
f(x,y)=x . 1(μz(H(y,x,z) ∧ S(y,x,x,z)))
C'è un errore nell'argomento che ti ho evidenziato in rosso.
La frase \fs{3}x\in W_y\cap E_y indica, oltre al fatto correttamente interpretato che \fs{3}\exists t\;:\;H(y, x, t), anche (e questo l'hai sbagliato) che \fs{3}\exists t, k\;:\;S(y, k, x, t)!!! Cioè, nella seconda parte, devi fare attenzione perché \fs{3}\phi_y deve bensì restituire x, ma grazie a un qualsiasi valore k (esistente) passatole come argomento! (tu invece lo hai bloccato di nuovo su x tale valore, rendendo falsi tutti gli altri casi in cui era diverso da k, cosa del tutto possibile .huh)

Ora passiamo agli errori della "tiritera"
è calcolabile perchè i predicati H(...) ed S(...) sono calc DEC;
l'and tra predicati calc DEC è calc DEC;
l'operatore di minimalizzazione applicato a funz calc PRED. DEC. è calc (?!*);
(*qui in realtà devi scrivere o
"l'operatore di minimalizzazione ...blablabla... dà luogo a funz. calcolabili"
oppure equivalentemente "la (operazione di) minimalizzazione ...blablabla... è calc."
la moltiplicazione con la funz cost unaria è calc e anche quella per x)
...Hai dimenticato di dire che l'applicazione della funzione 1 costante al valore di una funzione calcolabile è calcolabile per composizione...

Quindi calcolabile!


Title: Re:alcuni esercizi misti!
Post by: nairi on 17-06-2013, 23:10:06
grazie mille per le correzioni!!

Ps: inavvertitamente hai scambiato S con H!!!! ;)


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 17-06-2013, 23:11:13
grazie mille per le correzioni!!

Ps: inavvertitamente hai scambiato S con H!!!! ;)
Sì, scusa, correggo subito!


Title: Re:alcuni esercizi misti!
Post by: nairi on 17-06-2013, 23:20:24
ecco il secondo esercizio:
Dimostrare che esistono due funzioni totali e non calcolabili f,g:N\rightarrowN :
f(x)\cdotg(x) sia calcolabile

(Parziale) Soluzione:

definisco f(x) nel seguente modo:
          \phix(x) +1     se  \phix(x)\downarrow
f(x)= 1    altrimenti

f(x) non è calcolabile (salto la parte della dim della non calcolabilità perchè mi è chiara ma si fa per assurdo...)

Adesso definisco g(x) nel seguente modo:

g(x)=1/f(x)
ma non riesco a dimostrare che sia non calcolabile  .penso...
Aiutandomi con esercizi fatti in precedenza dovrei usare una composizione k(x)=... ma non so che composizione usare!

Ad ogni modo dimostrate che sia f(x) che g(x) sono non calcolabili, se le ho definite nel modo giusto, il loro prodotto dovrebbe essere calcolabile perchè :
f(x)\cdotg(x)=f(x)\cdot(1/f(x))=1 quindi è calcolabile!

che ne dici? sono un caso perso  .arrossisco ?


Title: Re:alcuni esercizi misti!
Post by: Giuseppe Scollo on 18-06-2013, 01:23:36
[...]
Dimostrare che esistono due funzioni totali e non calcolabili f,g:N\rightarrowN :
f(x)\cdotg(x) sia calcolabile

[...]
Adesso definisco g(x) nel seguente modo:

g(x)=1/f(x)
Che roba è questa? Le funzioni di cui si tratta sono sui numeri naturali, non sui razionali. È vero che la nozione di calcolabilità si può estendere al dominio dei razionali, essendo questi un insieme effettivamente enumerabile, ma non c'è davvero necessità di andar tanto lontano, e comunque l'esercizio vuole due funzioni di tipo ℕ → ℕ. L'esercizio ha (tantissime) soluzioni semplici semplici se si considera che anche le funzioni caratteristiche di predicati sono funzioni totali: la caratteristica totale di un predicato è calcolabile sse il predicato è decidibile, perciò per trovarne una non calcolabile basta prendere un quasiasi predicato indecidibile. Poi, il prodotto delle funzioni caratteristiche di due predicati è la funzione caratteristica del loro prodotto logico (AND), perciò non è difficile trovare due predicati indecidibili tali che il loro prodotto logico sia decidibile, per esempio basta assicurare che sia costante... Può bastare come dritta?



Title: Re:alcuni esercizi misti!
Post by: Mari_C on 18-06-2013, 15:35:44
Si studi la decidibilità e la parziale decidibilità del predicato unario Rc(x)="|Wx|\geqc" e della sua negazione al variare del parametro c \inN

Qualche dritta per questo predicato??  :pray


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 00:20:50
Sì, ecco una dritta:
quando ti si dice che bisogna studiare (...) al variare del parametro, significa che evidentemente c'è una certa regolarità fra certi valori speciali e/o generali del valore c.

In realtà, quindi, non stai studiando un solo predicato, ma tanti quanti sono i gruppi di valori di c per cui il predicato unario parametrizzato con c (e la sua negazione) ha una stessa caratteristica di decidibilità e parziale decidibilità.


Title: Re:alcuni esercizi misti!
Post by: Mari_C on 19-06-2013, 08:44:37
Sì, ecco una dritta:
quando ti si dice che bisogna studiare (...) al variare del parametro, significa che evidentemente c'è una certa regolarità fra certi valori speciali e/o generali del valore c.

In realtà, quindi, non stai studiando un solo predicato, ma tanti quanti sono i gruppi di valori di c per cui il predicato unario parametrizzato con c (e la sua negazione) ha una stessa caratteristica di decidibilità e parziale decidibilità.

provo a rifletterci  con questa dritta,Grazie!!!!!! .smile

A proposito di predicati, che ne pensi di questo?  .rido

Sia P il seguente predicato unario P(x)= "Wx \cap {1,3,5,7...}\neq\empty" Si studi la decidibilità e la parziale decidibilità del predicato e della sua negazione.

\negP(x)= \exists t,y: [H(x,y,t) \wedge "y è pari"]
accorpo in una variabile, \negP(x) è parzialmente decidibile.
Per studiare l'indecidibilità con Rice considero
A={\phix\inC1 : \negP(x) }
A è non banale perchè A \neq 0 poichè tutte le funzioni unarie, totali e calcolabili appartengono ad A
A \neq C1 perchè la f\empty\in C1 ma f\empty\notin A
Quindi A non è r.e \Rightarrow \negP(x) è indecidibile

Ho dunque studiato
         D     PD
P      NO    NO
\negP(x)   NO    SI


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 10:43:06
Noto che vi buttate spesso a studiare direttamente la negazione del predicato ... .penso, e non capisco perché.

In particolare, in questo esercizio, farlo peggiora le cose, giacché il predicato è abbastanza facile vedere che è p.d.
Inoltre, la tua negazione è pure sbagliata .poverinoi.

Se \fs{3}P(x)\;\equiv\;"W_x\cap\{{1,\;3,\;5,\;7,\;\cdots}\}\not{=}\emptyset"
allora \fs{3}\neg P(x)\;\equiv\;"W_x\cap\{{1,\;3,\;5,\;7,\;\cdots}\}=\emptyset"\;\equiv\;"\forall y\in\{{1,\;3,\;5,\;7,\;\cdots}\},\;\phi_x(y)\uparrow"
che si vede subito essere un predicato per verificare il quale (su un valore x che siamo sicuri lo soddisfi) serve un lavoro infinito! (quindi è candidato a essere non p.d.)

Invece \fs{3}P(x) è p.d. e, se ci venisse data una istanza di x che lo rende vero, dimostrarlo è piuttosto semplice, e richiede una semplice ricerca illimitata di un valore dispari k, (il più piccolo magari .arrossisco) per cui la funzione \fs{3}\phi_x(k)\downarrow, cioè un valore dispari k e un numero di passi t sufficientemente grande ovviamente che rendano vero il predicato \fs{3}H\({x, k, t}\).

Ora hai tutti gli ingredienti per iniziare la tua dimostrazione formale  :-OK!


Title: Re:alcuni esercizi misti!
Post by: nairi on 19-06-2013, 19:35:25
Quote
In realtà, quindi, non stai studiando un solo predicato, ma tanti quanti sono i gruppi di valori di c per cui il predicato unario parametrizzato con c (e la sua negazione) ha una stessa caratteristica di decidibilità e parziale decidibilità.

Dire che |Wx|\geqc vuol dire che nel dominio devono esserci almeno c elementi, per cui bisogna riformulare il predicato P(x) a secondo del valore di c; se ho capito bene es suppongo c=2 allora:
P(x)=\exists t, c1,c2:(H(x,c1,t)\wedge H(x,c2,t) \wedge c1\neqc2)
Così dovrei aggiungere tante condizioni quanto vale c.
P(x) è P.D.

Per l'indedicidilità uso Rice:
A={\phix\in C1: P(x)}
dovrei usare la funzione modulo  per dire che A\neq\empty e la funzione mai definita (la nostra amica) invece per dire che non appartiene ad A quindi A non è tutto C1.

Ho preso una "cantonata"? (giusto per rimanere in tema .rido)


Title: Re:alcuni esercizi misti!
Post by: Mari_C on 19-06-2013, 19:43:07

Ora hai tutti gli ingredienti per iniziare la tua dimostrazione formale  :-OK!

Grazie ai tuoi suggerimenti ho dedotto che P(x) è parzialmente decidibile ma per l'indecidibilità vorrei capire se ho ragionato bene....  :boh
Studio  l'indecidibilità in questo modo:
A={\phix\in C1: P(x)}

A\neq \empty perchè ad es contiene la funzione successore con dominio i numeri dispari
A\neq C1 perchè f\empty\inC1 ma f\empty\notin A \Rightarrow {x|P(x)} non è ricorsivo\Rightarrow P(x) è indecidibile.


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 22:03:06
Yeah! :-OK

Oppure potevi prendere la funzione definita su un solo numero dispari, tipo \fs{3}f(x)=\mu_z(x=1) sempre per dimostrare che \fs{3}A\not{=}\emptyset:boh


Title: Re:alcuni esercizi misti!
Post by: nairi on 19-06-2013, 22:10:16
ma della risp mia che ne pensi?  .penso


Title: Re:alcuni esercizi misti!
Post by: Mari_C on 19-06-2013, 22:14:32
Yeah! :-OK

Oppure potevi prendere la funzione definita su un solo numero dispari, tipo \fs{3}f(x)=\mu_z(x=1) sempre per dimostrare che \fs{3}A\not{=}\emptyset:boh

  |-O

Mi controlleresti anche questo??   .arrossisco

Dimostrare che esiste una f totale e calcolabile t(x) tale che Wt(x)={0,x+1,2(x+1)....} e Et(x)={0,1,2....x}

f(x,y)= \muz(y=z(x+1) \wedge z\leqx)
E poi usare il t.smn


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 22:31:43
Dire che |Wx|\geqc vuol dire che nel dominio devono esserci almeno c elementi, per cui bisogna riformulare il predicato P(x) a secondo del valore di c; se ho capito bene es suppongo c=2
Ecco, quello che ho evidenziato in rosso grassetto sottolineato è un procedimento mentale logico ragionevole e che ho fatto pure io... ma nella mia testa!

Guai a scriverla nel compito una cosa del genere!

Se ti dico (ricalcando il testo dell'esercizio) che bisogna studiare tutti i gruppi di casi, evidentemente non puoi prendere un solo singolo valore e studiare lì. A meno che quel singolo valore sia l'unico del suo gruppo (questo sono costretto a dirlo come aiutino perché c'è un gruppo singoletto tutto particolare .whistling), ma 2 non è l'unico del suo gruppo, e, dato c fissato (chiunque esso sia), esiste (almeno) una forma generale di controllare che n predicati uguali nella forma ma diversi negli argomenti passati (in questi caso l'argomento spazia su una sequenza lineare di valori, per vostra fortuna), ed è quella di manipolare correttamente i valori interi restituiti dalle funzioni caratteristiche dei predicati decidibili che vi servono (visto che si parla di terminazione, evidentemente ci starà di mezzo il predicato decidibile H)...

Se vi arrendete vi propongo due soluzioni semplici semplici, ma non ve le spiego e ve le studiate da voi xD.


Title: Re:alcuni esercizi misti!
Post by: nairi on 19-06-2013, 22:37:22
Quote
Se vi arrendete vi propongo due soluzioni semplici semplici, ma non ve le spiego e ve le studiate da voi xD.


Io noto che in questi esercizi ho difficoltà nel capire il testo! Quindi se sei così gentile da darci una soluzione, sarei felice di studiarne il ragionamento!

Più passano i giorni più mi allontano dalla "diritta via"  .poverinoi


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 22:40:49
Mi controlleresti anche questo??   .arrossisco

Dimostrare che esiste una f totale e calcolabile t(x) tale che Wt(x)={0,x+1,2(x+1)....} e Et(x)={0,1,2....x}

f(x,y)= μz(y=z(x+1) ∧ z ≤ x)
E poi usare il t.smn
Questo è quasi giusto.

Hai correttamente espresso la prima condizione col minimo (y=z(x+1)) perché hai individuato che a generare tutti i valori del dominio è proprio la funzione λz.z(x+1), però ti sei confusa con la seconda condizione, che non va posta.

Se ci pensi, se metti quella condizione, limiti il dominio di f (equivalentemente limiti Wt(x) nel passaggio successivo) ad avere un numero finito di elementi, che sono appunti esattamente x+1 (da 0 a x inclusi), mentre ad avere un numero finito di elementi dev'essere l'insieme dei valori assunti da f (equivalentemente l'insieme Et(x)), quindi devi cercare di costringere i valori assunti a fare parte dell'insieme {0, 1, 2, ..., x}.
Un modo già lo conosci, ed è di ripetere ciclicamente i valori tramite funzione resto (rm) della divisione modulo (x+1) (in modo che anche x, che è il numero precedente a x+1, sia restituito), oppure puoi prendere la funzione min a cui passi due argomenti: uno è il valore z restituito, e l'altro è x (così se z è minore o uguale a x, verrà restituito z, mentre se lo supera verrà restituito il minimo, cioè x).


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 22:50:46
Quote
Se vi arrendete vi propongo due soluzioni semplici semplici, ma non ve le spiego e ve le studiate da voi xD.


Io noto che in questi esercizi ho difficoltà nel capire il testo! Quindi se sei così gentile da darci una soluzione, sarei felice di studiarne il ragionamento!

Più passano i giorni più mi allontano dalla "diritta via"  .poverinoi
Ecco le due formulazioni equivalenti (che dimostrano la parziale decidibilità di Rc, in generale).

\fs{5}\displaystyle R_c(x)\;\equiv\;|{W_x}|\geq c\\\equiv\;\exists k\;:\;\[{\({\prod_{i<c+1}{C_H\({x,\;\({k}\)_i,\;\({k}\)_{c+1}}\)}}\)=1}\]\\\equiv\;\exists k\;:\;\[{\({\sum_{i<c+1}{C_H\({x,\;\({k}\)_i,\;\({k}\)_{c+1}}\)}}\)=c}\]

ove \fs{3}C_H è la funzione caratteristica (calcolabile) del predicato (infatti decidibile) di stop H, che vale quindi solo 0 (predicato falso) oppure 1 (predicato vero).

Se non capite perché funziona, ho pronta la spiegazione dettagliata del perché questa forma generale funziona, dovete solo dirmi se la volete.
In ogni caso, qui non sto trattando il valore speciale che vi dicevo prima (e che -aiutino- rende il predicato anche DEcidibile per quella speciale classe di valori -uno solo vabbè :boh-), mentre lascia non parzialmente decidibile le altre (l'altra?) classi (classe?) di valori x.


Title: Re:alcuni esercizi misti!
Post by: nairi on 19-06-2013, 22:55:42
certo che queste soluzioni sono da shock o.O .... a mente fresca proveremo a capirle e in caso ti faremo sapere! grazie  .wink


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 23:26:23
Ma quale shock? :[Emoticon] Turpiloquio Asd:

E dire che le abbiamo già viste in passato, anche piuttosto recente (per esempio >>qui<< (http://goo.gl/P1uUh)) :-)|

Mi preme fare notare che \fs{3}R_c(x) non è un solo predicato, ma tutta una infinità numerabile di predicati.

Il vantaggio è che si si possono studiare tutti insieme studiandone la forma generale, così da poterne capire il comportamento di tutti senza doverli effettivamente studiare tutti uno per uno...


Title: Re:alcuni esercizi misti!
Post by: nairi on 19-06-2013, 23:30:25
Quote
E dire che le abbiamo già viste in passato, anche piuttosto recente

Hai ragione! ma sono pur sempre uno shock per chi (come me) non è ancora entrato nell'ottica di queste cose  :boh ... mea culpa!


Title: Re:alcuni esercizi misti!
Post by: Mari_C on 21-06-2013, 14:32:07
Ciao!!!
 :[Emoticon] PC Asd: ecco un predicato con una possibile soluzione che spero sia corretta

Si studi la dec e parz dec del predicato unario P(x)="La funzione \phix è iniettiva nel suo dominio di definizione" e della sua negazione

\negP(x)="La funzione \phix non è iniettiva nel suo dominio di definizione"
\negP(x)=\exists x1,x2: \phi x(x1)=\phi x(x2) \wedge x1\neq x2
ciò vuol dire che
\negP(x)=\exists x1,x2,z,t: ( x1\neq x2 \wedge S(x,x1,z,t) = S(x,x2,z,t)
Accorpando in un unica variabile il \negP(x) è p.d
Ora studio l'indecidibilità con Rice
A={\phix\in C1: P(x)}
A\neq\empty poichè la funzione identità f(x)=x \inA
A\neqC1 poichè le funzioni costanti unarie e totali \inC1 ma \notinA
Quindi {x|P(x)} non è ricorsivo \Rightarrow P(x) è indecidibile
           D    PD
P(x)    NO   No 
\negP(x) No   SI


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-06-2013, 15:16:48
 :-OK Sei l'orgoglio del tuo insegnante!


Title: Re:alcuni esercizi misti!
Post by: nairi on 21-06-2013, 15:37:02
 :yoh ....

è un ottimo risultato, peccato che si suggeriva di evitare di  usare il t di Rice; ma come si fa a dim l'indec senza di esso?


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-06-2013, 16:27:23
Hai tanti modi: una bella diagonalizzazione rispetto alla funzione caratteristica del predicato, oppure una riduzione a un altro problema indecidibile, per esempio, oppure ancora un'applicazione del Teorema di Rice-Shapiro (ad esso o alla sua negazione: dimostrando che esso o la sua negazione non è p.d., allora nemmeno il predicato in sé è dec.)


Title: Re:alcuni esercizi misti!
Post by: nairi on 21-06-2013, 21:01:57
Problema con il seguente predicato  .poverinoi :
si studi la decidibilità e la parziale decidibilità del predicato unario
P(x) =“Wx è infinito e Ex è finito”
e della sua negazione.

(parte di soluzione):

Da una prima riflessione ho intuito che i predicati P(x) e \negP(x) NON sono PD in quanto richiedono un lavoro infinito...

Uso il t di Rice-Shapiro per P(x)
Sia A={\phix \in C1: P(x)}

A\subseteq C1.
Considero la funzione modulo (che ha dominio infinito) che \inA ma trovo anche la la restrizione \theta= f\empty \subseteq f \not\subseteq A
Quindi {x| P(x)} non è R.E. \Rightarrow P(x) non pd

Adesso per dire che \negP(x)  non è pd dovrei prima formularlo e poi usare di nuovo Rice-Shapiro giusto?
Se studiassi solo P(x) dicendo che è indecidibile non otterrei nulla su \negP(x) giusto?

e quindi ecco \negP(x)="“Wx è finito o Ex è infinito
Assumendo che sia corretto non riesco a continuare!
un aiutino?  .arrossisco


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 22-06-2013, 01:10:10
Problema con il seguente predicato  .poverinoi :
si studi la decidibilità e la parziale decidibilità del predicato unario
P(x) =“Wx è infinito e Ex è finito”
e della sua negazione.

(parte di soluzione):

Da una prima riflessione ho intuito che i predicati P(x) e \negP(x) NON sono PD in quanto richiedono un lavoro infinito...
...per dimostrare la veridicità almeno delle sole istanze di x che rendono vero il predicato (rispettivamente esso o il suo negato). Corretto .smile.

Uso il t di Rice-Shapiro per P(x)
Sia A={\phix \in C1: P(x)}

A\subseteq C1.
Considero la funzione modulo (che ha dominio infinito) che \inA ma trovo anche la la restrizione \theta= f\empty \subseteq f \not\subseteq A
Quindi {x| P(x)} non è R.E. \Rightarrow P(x) non pd
Sì, questo è vero che vale per la funzione mai definita (che ha dominio banalmente finito), ma in ogni caso tu devi dimostrare che vale per qualsiasi restrizione finita della funzione resto.
Ma è banale vedere che qualsiasi restrizione finita non appartiene ad A, perché, proprio per il fatto che ha dominio finito, una restrizione con dominio finito non rende vera una delle clausole poste in congiunzione (and), cioè che avevamo imposto che dovevano avere dominio infinito! :boh

Nota: proprio la funzione resto la eviterei, nella sua forma consueta, poiché è una funzione binaria, mentre noi abbiamo costruito A perché contenesse funzioni unarie. Se però blocchi il dividendo su un numero non nullo qualsiasi, ecco che puoi usare questa nuova funzione resto modificata, per il tuo scopo .smile.
Puoi riciclare il ragionamento di prima con questa nuova funzione resto modificata :-OK.


Adesso per dire che \negP(x)  non è pd dovrei prima formularlo e poi usare di nuovo Rice-Shapiro giusto?
Se studiassi solo P(x) dicendo che è indecidibile non otterrei nulla su \negP(x) giusto?
Giusto, sapresti solo che anche la negazione di P è indecidibile :boh, ma non sapresti se è anche p.d. o non p.d.

e quindi ecco \negP(x)="“Wx è finito o Ex è infinito
Assumendo che sia corretto non riesco a continuare!
un aiutino?  .arrossisco
È corretto, e tu sai come continuare! |-O

Le funzioni dell'insieme A={ϕx:¬P(x)} sono tutte quelle che hanno o dominio finito o range infinito. Puoi scegliere di considerare uno dei due casi quindi, a tuo piacimento (o anche tutti e due per raddoppiare inutilmente il lavoro :-)|).

Caso 1) si consideri una funzione in A con dominio finito e facciamo vedere che non tutto il cono di funzioni che si basano (essendo esse estensioni di) sulla nostra funzione considerata, è contenuto in A.
Per es. scegliamo la funzione mai definita. Essa sicuramente ha dominio finito, e questo ci basta per infilarla dentro A. Ma qualsiasi altra funzione diversa da questa, è una estensione della funzione mai definita, e quindi qualsiasi funzione calcolabile unaria deve fare parte di A, tuttavia almeno una scappa fuori. Per es. una funzione con dominio infinito e range finito, tipo tutte le funzioni costanti che sono totali (dominio infinito) e per il fatto che sono costanti hanno il range finito (con cardinalità esattamente 1 elemento, e 1 è finito :boh): di queste funzioni ce ne sono abbastanza (tante quanti sono i naturali, quindi almeno 1, e questo ci basta :boh) quindi in questo caso otterremmo che A non è r.e., cioè ¬P non è p.d.

Caso 2) se durante il compito non riuscissimo a trovare una funzione adatta per il caso 1, proviamo col caso di una funzione che ha range infinito, e poi facciamo vedere che qualsiasi restrizione finita di essa non apparterrà ad A.
Consideriamo la funzione identità: ha range infinito, quindi sta in A, tuttavia qualsiasi sua restrizione finita, avrà appunto un dominio finito (non rende vera la prima clausola in disgiunzione (OR)), e inoltre, poiché il suo dominio è finito, necessariamente tale sarà il range (cioè è falsa anche la seconda condizione in disgiunzione). La disgiunzione di due falsità, è ancora falso, quindi qualsiasi restrizione finita della funzione identità non appartiene ad A, quindi A è non r.e., cioè ¬P non è p.d.


Title: Re:alcuni esercizi misti!
Post by: nairi on 22-06-2013, 08:42:57
 .applausi grazie!!!!! sei un genio  .wink !!


Title: Re:alcuni esercizi misti!
Post by: Mari_C on 22-06-2013, 14:09:19
 :pray per questo predicato binario!!!

Si studi la dec e par dec del predicato binario
P(x,y)= "Wx\cap{0,1...y}=\empty"
P(x,y) è vero se e solo se \phi(x) non è definita su alcun argomento minore o uguale a y

P(x,y)=\phix(y)\downarrow \forallx>y
Allora ho pensato di usare
P(x,y)=\existst:{[\prod_{x>y} CH(x,y,t)]=1}
dove CH è la funzione caratteristica del predicato di stop H
Quindi P(x,y) è P.D.
ora devo accorpare in un unica variabile per usare il teorema di Rice
R(z)=P(((z)1),((z)2))
A={\phix\inC1: R(z)}
e qui avrei bisogno di un aiuto per le osservazioni giuste per dire che A non è banale(ammesso che quello sopra vada bene .rido)....


Title: Re:alcuni esercizi misti!
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 22-06-2013, 14:43:09
:pray per questo predicato binario!!!

Si studi la dec e par dec del predicato binario
P(x,y)= "Wx∩{0,1...y}=∅"
P(x,y) è vero se e solo se ϕ(x) non è definita su alcun argomento minore o uguale a y

P(x,y)=ϕx(y)↓ ∀x>y
Caso mai volevi scrivere:
P(x,y)=ϕx(k)↓ ∀k>y
che sarebbe comunque sbagliato.

P dice un'altra cosa, in particolare è:

P(x, y)=∀k≤y, ϕx(k)↑

Intuisco che non è p.d. lui, ma lo è il suo negato:
- perché se ci dessero una coppia (x, y) in input che rende vero il predicato, per dimostrarlo dovremmo verificare che su un certo insieme finito di numeri k compresi tra 0 e y, si abbia che dopo 0, 1, 2, ..., n, ... passi la computazione di  ϕx(k) non si è ancora fermata (il numero di verifiche per ogni k è infinito)
- perché ¬P(x, y)=∃k≤y, ϕx(k)↓ cioè ¬P(x, y)=∃w (H (x, (w)1, (w)2) ∧ (w)1≤y)

Però... non ricordo (e non ricordo di averli visti, almeno): come si tratta lo studio dei predicati binari .penso?
Avrei in mente l'idea di bloccare un parametro e studiare quello che ottengo studiando un altro predicato che è lo stesso di prima ove una variabile è fissata (tipo che è una costante), e poi generalizzare.


Title: Re:alcuni esercizi misti!
Post by: Mari_C on 22-06-2013, 20:47:10
Quote
Però... non ricordo (e non ricordo di averli visti, almeno): come si tratta lo studio dei predicati binari ?

L'abbiamo trovato in un compito del 2005  :-)|
cmq grazie per le correzioni!!