Forum Informatica Unict

LAUREA MAGISTRALE => Teoria della Computabilità, 9 CFU => Topic started by: Mari_C on 17-06-2013, 11:20:47



Title: es funzioni calcolabili
Post by: Mari_C on 17-06-2013, 11:20:47
Ciao a tutti!
Ecco un nuovo esercizio:

Si dimostri che se f è una funzione unaria calcolabile, allora anche la seguente funzione è calcolabile:
                                       x2           se f(y)\cdotx è un quadrato perfetto , per qualche y\geq x2

g(x)      \approx

                                      \uparrow    altrimenti

g(x)= x2 + 0 [\mu z (f (z) \cdot x = z2) \wedge z \geq x2]    che è calcolabile

Che ve ne pare?  :-ciao


Title: Re:es funzioni calcolabili
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 17-06-2013, 12:24:55
Sbagliata.

Il testo dice di restituire \fs{3}x^2 se "\fs{3}\exists y\in\mathbb{N}\;:\;f(y)\cdot x" è un quadrato (ma non ti dice di quale numero, sicuramente non puoi costringere tale numero a essere necessariamente uguale a y), equivalentemente se:
\fs{3}\exists y\in\mathbb{N},\;\exists k\in\mathbb{N}\;:\;f(y)\cdot x=k^2

Riprova  :-OK!


Title: Re:es funzioni calcolabili
Post by: Mari_C on 17-06-2013, 15:54:59
Sbagliata.

Il testo dice di restituire \fs{3}x^2 se "\fs{3}\exists y\in\mathbb{N}\;:\;f(y)\cdot x" è un quadrato (ma non ti dice di quale numero, sicuramente non puoi costringere tale numero a essere necessariamente uguale a y), equivalentemente se:
\fs{3}\exists y\in\mathbb{N},\;\exists k\in\mathbb{N}\;:\;f(y)\cdot x=k^2
b

 g(x) = x2+ 0 [\muz(f(z)1 \cdotx =(z)22 \wedge (z)2\geqx2 ]
Così che ne dici?


Title: Re:es funzioni calcolabili
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 17-06-2013, 21:16:58
Sì, ci siamo.

Devi, però, fare ancora molta attenzione a come scrivi le espressioni:
in particolare, devi correggere la scrittura
f(z)1 x
con la corretta:
f((z)1)x


Title: Re:es funzioni calcolabili
Post by: Mari_C on 17-06-2013, 21:34:34
 ok :-OK grazie!

te ne propongo un altro dello stesso tipo:

Data una funzione f unaria e calcolabile ,si dimostri che la seguente funzione è calcolabile
                                f(x2)      se x2=f(x2+y2) per qualche y

g(x)\simeq
                                \uparrow altrimenti

g(x)= f(x2) 1 [\muz(x2=f(z)2 \wedge (z)2=x2+((z)1)2]
che mi dici di questa?  .whistling


Title: Re:es funzioni calcolabili
Post by: nairi on 18-06-2013, 15:37:06
 .quoto


Title: Re:es funzioni calcolabili
Post by: nairi on 18-06-2013, 22:32:50
L'esame si avvicina e i dubbi aumentano....  :-)| ma com'è possibile??!??!  :pray  Ecco l'ennesimo esercizio:

Sia h: N  \rightarrow N una funzione calcolabile totale. Si dimostri che esiste una funzione f totale e non calcolabile tale che
- f(2x)=h(x) , \forall x\in N
- f(y) \geqy \forall y \inN dispari

Soluzione:

          h(x)          se \phix(y)\downarrow \wedge y=2x
f(x)=  y+1           se y è dispari(y=2x+1) \wedge \phix(y)\downarrowy
          y             se( y è dispari(y=2x+1) \wedge \phix(y)\downarrowk con k \neqy)\vee(\phix(y)\downarrow)

come va questa impostazione?


Title: Re:es funzioni calcolabili
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 00:47:06
Male.

Una possibile soluzione è:

\fs{3}f(x)=\{\begin{matrix}h\({\text{qt}\({2,\;x}\)}\)&&\text{se }x\text{ pari}\\\min\({\phi_{\frac{x-1}{2}}\({x}\),\;x-1}\)+1&&\text{se }x\text{ dispari}\;\wedge\;\phi_{\frac{x-1}{2}}\({x}\)\downarrow\\x&&\text{se }x\text{ dispari}\;\wedge\;\phi_{\frac{x-1}{2}}\({x}\)\uparrow\end{matrix}

Qui si vede che la diagonale è stata opportunamente dilatata in modo che non passi mai da due colonne consecutive, ma giustamente passi solo dalle colonne etichettate con valori dispari (quelli su cui abbiamo libertà di far assumere a f un valore diverso da quello della funzione calcolabile di codice \fs{3}\frac{x-1}{2} il quale codice è, se fai due calcoli, uguale a tutti i numeri naturali, uno alla volta).


Title: Re:es funzioni calcolabili
Post by: Mari_C on 19-06-2013, 08:32:35
Grazie reverse per il tuo aiuto  .arrossisco

Ecco un altro esercizio:
Dim che esiste una funzione totale calcolabile k(x) tale che |Wk(x)|=x e Ek(x)={x}
Una possibile soluzione potrebbe essere questa?

f(x,y)=x+ 0 [ \muz(y=x+z+1)mod(x+1)]
f(x,y) è calcolabile e poi uso il teorema del parametro...


Title: Re:es funzioni calcolabili
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 10:45:03
f(x,y)=x+ 0 [ μz(y=x+z+1)mod(x+1)]
Riscrivi questa cosa con le parentesi giuste che così com'è non si può leggere .nono...

E sopratutto non fare confusione tra il simbolo che indica una relazione di congruenza in matematica (mod) e la funzione calcolabile rm :-)|!!!


Title: Re:es funzioni calcolabili
Post by: nairi on 19-06-2013, 21:26:03
Quote
Data una funzione f unaria e calcolabile ,si dimostri che la seguente funzione è calcolabile
                                f(x2)      se x2=f(x2+y2) per qualche y

g(x)\simeq
                                \uparrow altrimenti

g(x)= f(x2) 1 [\muz(x2=f(z)2 \wedge (z)2=x2+((z)1)2]
che mi dici di questa?

Devo dedurre che sia corretto dato che non ci sono state osservazioni?  .coolio


Title: Re:es funzioni calcolabili
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 22:01:25
No, sbagliatissima quella è.

Molto più banalmente, una soluzione è data da:

\fs{3}g(x)=f(x^2)\cdot\underline{1}\({\mu_y\({x^2=f(x^2+y^2}\)}\)

Non vi dovete fare confondere dalla scrittura (che sinceramente a me non piace proprio, la trovo decisamente fuorviante rispetto ai normali quantificatori) "per qualche y" post-fissa alla frase, che si traduce con "esiste y tale che" pre-fissa alla frase.

In ogni caso, fate ancora sempre lo stesso errore di scrittura, cioè scrivere cose come
f(z)2, che non significa nulla, mentre la scrittura corretta (presumo) deve essere f((z)2)

Se proprio non vi piace la sintassi di mettere una variabile (o una espressione generica) tra parentesi e dopo fare il pedice, e trattare IL TUTTO come unica espressione (nel vostro caso avreste dovuto, quindi, mettere IL TUTTO tra parentesi tonde di nuovo prima di passarlo a f, come vi ho esemplificato prima), inventatevi un altro nome del tipo
esponenteDiANellaFattorizzazioneDiB(a, b) così non sbagliate più .nono... (ovviamente sono sarcastico qua, NON dovete fare una cavolata del genere)


Title: Re:es funzioni calcolabili
Post by: nairi on 19-06-2013, 22:09:32
grazie!!!
Non lo facciamo apposta a dimenticarci le parentesi, ma fai bene a farcelo notare! speriamo di non dover ripetere più quest'errore!!!   :"-(


Title: Re:es funzioni calcolabili
Post by: nairi on 19-06-2013, 22:43:49
Quote
Dim che esiste una funzione totale calcolabile k(x) tale che |Wk(x)|=x e Ek(x)={x}

Sempre riguardo a quest'esercizio, io non ho ancora capito cosa vuol dire il testo  .penso ...

Dire che la cardinalità del dominio è x vuol dire che ci sn x elementi nel dominio giusto?
e quindi come faccio a trovare una soluzione a tale problema?
anche se aggiustiamo le parentesi penso che quella fornita da noi sia la soluzione sbaglaita vero?
cmq la minimalizzazione era applicata a y=x+z+1 e poi se ne fa il modulo (x+1)


Title: Re:es funzioni calcolabili
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 23:09:38
Quote
Dim che esiste una funzione totale calcolabile k(x) tale che |Wk(x)|=x e Ek(x)={x}

Sempre riguardo a quest'esercizio, io non ho ancora capito cosa vuol dire il testo  .penso ...

Dire che la cardinalità del dominio è x vuol dire che ci sn x elementi nel dominio giusto?
Giusto :boh.
e quindi come faccio a trovare una soluzione a tale problema?
In generale, siccome la funzione andrà fatta passare attraverso il teorema di parametrizzazione, e che quindi la funzione dopo si chiamerà \fs{3}\phi_{k(x)}(y), quindi una funzione della sola variabile \fs{3}y, devi fare in modo che f (equivalentemente dopo \fs{3}\phi_{k(x)} si fermi esattamente su \fs{3}x (parametro fissato) valori fra tutti quelli che \fs{3}y può assumere.

Quindi, banalmente, ti scegli \fs{3}x valori distinti dentro \fs{3}\mathbb{N} e poi fai in modo che se \fs{3}y è uno di quei valori, allora tutta la funzione restituisce, se no cicla all'infinito (operatore di minimalizzazione!).
Posso sceglierli io x valori semplici semplici da riconoscere?
Bene: i numeri da 0 a x-1  :boh

anche se aggiustiamo le parentesi penso che quella fornita da noi sia la soluzione sbaglaita vero?
cmq la minimalizzazione era applicata a y=x+z+1 e poi se ne fa il modulo (x+1)
Sì, era sbagliata anche in questa forma (che avevo intuito, ma per la quale aspettavo la vostra certezza, che ora è arrivata).
Se prima cerchi quel minimo, e poi gli applichi il modulo (ma anche se non gli applichi il modulo per ottenere il resto), tale funzione si fermerà su tutti i valori \fs{3}y>x (che sono esattamente \fs{3}|\mathbb{N}|-(x+1)=|\mathbb{N}|=\aleph_0, cioè fin troppi per voi (che ne dovevate contare solo x), e quelli in cui va in loop sono x+1 quindi; dovete fare in modo che, invece, siano x quelli in cui si ferma, come suggerito poco sopra ora (potete riciclare quella condizione manipolandola un po').
Visto che tanto il valore ottenuto viene passato alla simpatica funzione costante nulla (0) non serve che facciate alcun modulo (quel modulo è un residuo di errore della malinterpretazione precedente).


Title: Re:es funzioni calcolabili
Post by: nairi on 19-06-2013, 23:18:21
Quote
i numeri da 0 a x-1

ok questo l'avevo capito (per fortuna) anche se non sono riuscita ad esprimerlo bene!

e se mettessi la condizione z<x? che ne pensi?

cioè:

f(x,y)=x+o(\muz(y=x+z+1) \wedge z<x)


Title: Re:es funzioni calcolabili
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 23:49:24
Penso bene, benissimo .smile.

A parte un errore (che devi imparare a non fare più :-)|) di sbagliare la parentesizzazione (la condizione z<x va messa dentro alla minimalizzazione, giustamente in AND con l'altra), in questo modo hai fatto in modo che f sia definita esattamente nei valori per cui vale z<x, ovvero (in riferimento all'argomento libero di f, cioè l'unico di \fs{3}\phi_{k(x)}, cioè y) i valori y=x+z+1 con z=0, 1, ..., x-1, e cioè ancora i valori y=x+1, x+2, x+3, ..., 2x. Se i valori di z sono esattamente x (e lo sono) per il fatto che hai verificato che y fosse un valore proveniente da una funzione iniettiva dei suoi (di z) valori (λz.x+z+1 assume sempre valori diversi |-O, per ogni z, mai lo stesso per due z diversi), allora necessariamente anche i valori di y che hai scelti saranno x.

Ma se non ne siamo sicuri, controlliamo: allora, la sequenza per y è di valori tutti consecutivi, inizia da x+1 e finisce a 2x. Quanti sono i numeri nell'intervallo chiuso [a, b]? Sono esattamente b-a+1. Quindi: quanti sono i numeri nell'intervallo chiuso [x+1, 2x]? Sono esattamente (2x)-(x+1)+1=2x-x-1+1=2x-x=(2-1)x=1x=x  :-OK!!!

Ottimo lavoro!