Pages: [1] 2 3   Go Down
Print
Author Topic: alcuni esercizi misti!  (Read 6246 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



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

Gender: Male
Posts: 4.446


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


WWW
« Reply #1 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 )

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!
« Last Edit: 17-06-2013, 23:11:35 by reversengineer » 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: 17-06-2013, 23:10:06 »

grazie mille per le correzioni!!

Ps: inavvertitamente hai scambiato S con H!!!! Wink
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.446


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


WWW
« Reply #3 on: 17-06-2013, 23:11:13 »

grazie mille per le correzioni!!

Ps: inavvertitamente hai scambiato S con H!!!! Wink
Sì, scusa, correggo subito!
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: 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  ...
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  ?
Logged
Giuseppe Scollo
Moderator
Forumista Esperto
*****
Offline Offline

Posts: 1.382


« Reply #5 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?

Logged
Mari_C
Apprendista Forumista
**
Offline Offline

Posts: 240


"SmiiiiLe"


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

Gender: Male
Posts: 4.446


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


WWW
« Reply #7 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à.
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
Mari_C
Apprendista Forumista
**
Offline Offline

Posts: 240


"SmiiiiLe"


« Reply #8 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!!!!!!

A proposito di predicati, che ne pensi di questo? 

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

Gender: Male
Posts: 4.446


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


WWW
« Reply #9 on: 19-06-2013, 10:43:06 »

Noto che vi buttate spesso a studiare direttamente la negazione del predicato ... , 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 .

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 ) 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!
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 #10 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 )
Logged
Mari_C
Apprendista Forumista
**
Offline Offline

Posts: 240


"SmiiiiLe"


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

Gender: Male
Posts: 4.446


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


WWW
« Reply #12 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{=}\emptysetboh
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 #13 on: 19-06-2013, 22:10:16 »

ma della risp mia che ne pensi? 
Logged
Mari_C
Apprendista Forumista
**
Offline Offline

Posts: 240


"SmiiiiLe"


« Reply #14 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{=}\emptysetboh

  univ

Mi controlleresti anche questo??   

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
Logged
Pages: [1] 2 3   Go Up
Print
Jump to: