Pages: [1] 2   Go Down
Print
Author Topic: es funzioni calcolabili  (Read 3546 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Mari_C
Apprendista Forumista
**
Offline Offline

Posts: 240


"SmiiiiLe"


« 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
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, 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!
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 #2 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?
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, 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
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 #4 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? 
Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #5 on: 18-06-2013, 15:37:06 »

 
Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #6 on: 18-06-2013, 22:32:50 »

L'esame si avvicina e i dubbi aumentano....  testate 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?
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: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).
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:32:35 »

Grazie reverse per il tuo aiuto 

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

E sopratutto non fare confusione tra il simbolo che indica una relazione di congruenza in matematica (mod) e la funzione calcolabile rm testate!!!
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, 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? 
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 #11 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ù ... (ovviamente sono sarcastico qua, NON dovete fare una cavolata del genere)
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 #12 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!!!   cry
Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #13 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  ...

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)
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 #14 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  ...

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