Pages: [1]   Go Down
Print
Author Topic: funzione non calcolabile :)  (Read 2101 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« on: 05-06-2013, 20:56:38 »

ecco un nuovo esercizio  :

Si dimostri che esiste una funzione f:N \rightarrowN totale e non calcolabile tale che:
a) f(x)\geq\forall x\inN
b) x divide f(x) \forall x\geq1

Soluzione:

        \phix(x)+1        se "div(x,\phix(x)) \wedge x\geq1" (oppure è meglio dirlo a parole?)
f(x)=
        2                  altrimenti

l'impostazione è corretta?
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.450


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


WWW
« Reply #1 on: 05-06-2013, 21:33:18 »

f dev'essere tale che x divida f(x)   (ma solo per ogni x maggiore o uguale a 1, ovviamente questo poiché se fosse 0, 0 non dividerebbe nessun numero!)

In nessuno dei tuoi casi si ha che x divide f(x) .

Devi fare in modo, cioè, che f(x) assuma sempre, come valore, un multiplo di x (almeno per x non nullo), e ovviamente diverso da \fs{3}\phi_x(x) (per ottenere l'incalcolabilità boh).

Riprova!
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: 06-06-2013, 00:32:22 »

Quote
Riprova!


certamente! grazie per la dritta!
Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #3 on: 17-06-2013, 15:59:15 »

Quote
Devi fare in modo, cioè, che f(x) assuma sempre, come valore, un multiplo di x (almeno per x non nullo), e ovviamente diverso da ϕx(x) (per ottenere l'incalcolabilità

      \phix(x)\cdot(\phix(x)/x)    se rm(\phix(x), x)=0 \wedge x \geq1 \wedge \phix(x)\geq2
f(x)=
      x se ....

Va bene così il primo caso? Nel secondo caso va bene che restituisco x? A quale condizione?
Ho molti dubbi ancora sul testo
« Last Edit: 17-06-2013, 21:07:21 by reversengineer » Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.450


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


WWW
« Reply #4 on: 17-06-2013, 21:13:09 »

No, no, stai confondendo quello che, in questo esercizio, ti è richiesto di imporre dopo ai valori assunti da f, da quello che invece, negli altri compiti, è richiesto di valutare prima di far assumere un valore a f...

Tu stavolta devi imporre che , per ogni x maggiore di 0 (condizione da valutare prima) f assuma un valore multiplo di x (condizione da imporre dopo).

Inoltre, ti è richiesto che il valore assunto sia sempre non inferiore a 2 (siccome, per ogni x maggiore di 0, i suoi multipli sono infiniti e uno più grande del precedente, esisterà certamente un tale valore assumibile multiplo di x e maggiore o uguale a 2), e che non sia mai uguale a ϕx(x) (un modo grossolano, impreciso, ma per quello che ti serve sufficiente, di dire che non dev'essere calcolabile).
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 #5 on: 17-06-2013, 22:00:23 »

scusa ma questo esercizio non mi è proprio entrato in testa!

non è scattata la scintilla   
       
         2\cdot\phix(x)\cdotx     se \phix(x) \downarrow   \wedge x>0
f(x)=  \phix(x)\cdotx  altrimenti
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.450


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


WWW
« Reply #6 on: 17-06-2013, 22:31:02 »

non è scattata la scintilla  
E allora non sarà amore  pray!

Comunque, ci sei andata molto vicina.
Visto che sei stressata, ti do io una soluzione, ma solo per stavolta univ:

\fs{3}f(x)=\{\begin{matrix}3&&\text{se }x=0\;\wedge\;\phi_x(x)\downarrow 2\\2&&\text{se }x=0\;\wedge\;\({\phi_x(x)\uparrow\;\vee\;\({\phi_x(x)\downarrow k\;\wedge\;k\not{=}2}\)}\)\\\({\lfloor{\text{qt}\({x,\; \phi_x(x)}\)}\rfloor+1}\)\cdot x&&\text{se }x>0\;\wedge\;\phi_x(x)\downarrow\\2x&&\text{se }x>0\;\wedge\;\phi_x(x)\uparrow\end{matrix}

La spiegazione di come nasce una funzione di questo tipo è molto semplice, sebbene non lo sembri la sua espressione:

i due casi più evidenti con cui confrontarci sono
1) x=0
2) x>0

Nel caso 1), l'unica imposizione che ci viene dall'alto è che f sia maggiore o uguale di 2, perciò banalmente se \fs{3}\phi_x(x) termina e fa proprio due, ci mettiamo 3 (così è diverso da \fs{3}\phi_x(x));
se non termina oppure termina in un numero diverso da 2, stavolta banalmente gli facciamo assumere il valore 2, che è certamente diverso da \fs{3}\phi_x(x) (se \fs{3}\phi_x(x)\uparrow, la diversità è banale, se \fs{3}\phi_x(x)\downarrow, sappiamo che il valore in cui termina non è 2, perciò 2 ci va bene); in entrambi i casi è un valore diverso e maggiore o uguale a due;


Nel caso 2, stavolta x non è nulla, quindi esistono una infinità di multipli di x tutti diversi. Ne dobbiamo scegliere uno che sia a) maggiore o uguale di 2 e contemporaneamente b) diverso da \fs{3}\phi_x(x) (caso in cui \fs{3}\phi_x(x) è definita).
Allora noi facciamo così: tentiamo di fare la divisione intera \fs{3}\frac{\phi_x(x)}{x}: se il risultato è ancora intero (cioè \fs{3}\phi_x(x) era già un multiplo, diciamo il k-esimo multiplo, di x), il floor non ci crea problemi, e sommando una unità e rimoltiplicando per x, otteniamo sostanzialmente il successivo multiplo (il (k+1)-esimo, che è maggiore di \fs{3}\phi_x(x) (e quindi anche diverso da esso, ottenendo l'incalcolabilità) e che possiamo dimostrare (ma non lo faccio) in pochi passi anche essere maggiore o uguale a 2;
se invece il \fs{3}\phi_x(x) non era multiplo, allora il floor della divisione ci dà quel numero k che, se moltiplicato per x, è ancora ovviamente un multiplo di x ed è il più grande dei multipli di x che non superano \fs{3}\phi_x(x). Se a questo k sommiamo uno, il prodotto di (k+1) per x ci darà, quindi, un multiplo di x (ovvio) che supera strettamente \fs{3}\phi_x(x) (e quindi ne è anche diverso, ottenendo la incalcolabilità), e che, quindi, non è inferiore a 2 (anche questo si può dimostrare con una piccola catena di passaggi).
Il caso 2), quando \fs{3}\phi_x(x) è indefinita, ci permette di scegliere un qualsiasi valore finito (per ottenere la diversità da \fs{3}\phi_x(x) e quindi la incalcolabilità) che sia multiplo di x non inferiore a 2: banalmente 2x è multiplo di x e vale \fs{3}x\geq 1\;\Rightarrow\;2x\geq 2, quindi possiamo assegnarlo .

È molto più lungo da spiegare che da scrivere pc, non trovi?
« Last Edit: 17-06-2013, 22:47:31 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 #7 on: 17-06-2013, 22:51:21 »

Quote
È molto più lungo da spiegare che da scrivere pc, non trovi?

 pray grazie!
 domani ne farò uno simile che già avevo visto oggi...  vedremo se ho imparato qualcosa!
Logged
Pages: [1]   Go Up
Print
Jump to: