Pages: 1 2 [3]   Go Down
Print
Author Topic: lista esercizi  (Read 8034 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
ɹǝǝ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 #30 on: 20-06-2013, 11:17:36 »

No, non hanno lo stesso output per gli stessi input in generale, ma lo hanno solo su determinati valori.

g1 ristretta ai numeri pari, assume gli stessi valori passatile in input
g2 ristretta ai multipli di 3, assume gli stessi valori passatile in input
...
gn ristretta ai mutipli di (n+1), assume gli stessi valori passatile in input

Ciò vuol dire che su tutti gli altri valori non multipli del (pedice+1), che sono infiniti (altrimenti sarebbe impossibile ottenere la incalcolabilità, nota bene!), hai libertà di scegliere quello che vuoi.
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 #31 on: 21-06-2013, 11:13:28 »

Quote
Ciò vuol dire che su tutti gli altri valori non multipli del (pedice+1), che sono infiniti (altrimenti sarebbe impossibile ottenere la incalcolabilità, nota bene!), hai libertà di scegliere quello che vuoi.

mi dici se questo ragionamento va bene? ho usato g2:

                  y   se "y è un multiplo di 3"
g2(y)=       3   se \phiy+1(y)\downarrow \wedge ymod3 \neq 0
                  3   se \phiy+1(y)\uparrow

In caso di correttezza, mi sorge un dubbio: non dovrei garantire per ogni caso la g2(y) sia diversa da \phi  in almeno un punto?
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 #32 on: 21-06-2013, 13:06:07 »

E se dovessimo essere nel caso in cui "y è un multiplo di 3" e contemporaneamente \fs{3}\phi_{y+1}(y)\uparrow?

Devi imparare a gestire meglio i casi, attualmente non sono mutualmente esclusivi .

Sebbene la strategia sia sempre la stessa, e cioè scegliere, per ogni indice x (y nel tuo caso) di quelli che usiamo per dimostrare solo la parte di incalcolabilità, un altro indice k(x) tale che k sia biunivoca tra il suo dominio (dominio matematico stavolta, non riguardo alle teoria delle funzioni calcolabili) e tutto \fs{3}\mathbb{N}, questa volta la funzione k non è così banale:

In particolare, visto che i valori multipli di 3 (o di n in generale, dalla forma generale degli esercizi di questo tipo) sono esattamente \{{3,\;6,\;9,\;12,\;15,\;\cdots}\} e questi non li possiamo usare per dimostrare l'incalcolabilità (giacché dobbiamo imporre per questi un valore calcolabile, in particolare in quei punti bisogna che f assuma gli stessi valori dell'argomento boh), allora per dimostrare l'incalcolabilità possiamo sfruttare un sottoinsieme infinito dell'insieme dei numeri rimanenti dalla sottrazione insiemistica \fs{3}\mathbb{N}\setminus\{{3,\;6,\;9,\;12,\;15,\;\cdots}\}=\mathbb{N}\setminus\{{x\;:\;x\;\equiv\;0\;\({\text{mod} 3}\)}\}=\{{0,\;1,\;2,\;4,\;5,\;7,\;8,\;10,\;11,\;13,\;14,\;\cdots}\}.

È importante notare che non è necessario che si passi da tutti questi indici x per costruire k(x) suriettiva su \fs{3}\mathbb{N}, ma è sufficiente che si passi da un suo sottoinsieme infinito (dev'essere infinito per forza, se vogliamo che sia suriettiva su tutto \fs{3}\mathbb{N}.

Scegliamo, per esempio, di passare dal sottoinsieme degli indici che sono i numeri precedenti dei multipli di 3, ovvero gli elementi dell'insieme:
 \fs{3}\{{2,\;5,\;8,\;11,\;14,\;...}\}\subseteq\{{0,\;1,\;2,\;4,\;5,\;7,\;8,\;10,\;11,\;13,\;14,\;\cdots}\}=\mathbb{N}\setminus\{{x\;:\;x\;\equiv\;0\;\({\text{mod} 3}\)}\}

Riesci a trovare una funzione biunivoca tra \fs{3}k tra gli insiemi \fs{3}\{{2,\;5,\;8,\;11,\;14,\;...}\}\;{k\over\longleftrightarrow}\;\mathbb{N}?
« Last Edit: 15-07-2013, 20:11:36 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
Mari_C
Apprendista Forumista
**
Offline Offline

Posts: 240


"SmiiiiLe"


« Reply #33 on: 21-06-2013, 14:35:30 »

Quote
Riesci a trovare una funzione biunivoca tra k tra gli insiemi {2, 5, 8, 11, 14, ...} ed ℕ?

Potresti essere più chiaro ,please? Non capisco questo linguaggio formale  boh  
« Last Edit: 21-06-2013, 15:11:59 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 #34 on: 21-06-2013, 15:13:31 »

Quote
Riesci a trovare una funzione biunivoca tra k tra gli insiemi {2, 5, 8, 11, 14, ...} ed ℕ?

Potresti essere più chiaro ,please? Non capisco questo linguaggio formale  boh  
Scusa, c'era un "tra" di troppo: l'ho sbarrato modificando il messaggio:

Quello che voglio chiederti è: sai descrivere una funzione k che associ tutti gli interi precedenti ai multipli di tre, a tutti gli interi in generale, in modo che sia biunivoca (cioè ne esista l'inversa che associa ad ogni naturale uno ed un solo precedente di multiplo di 3)?
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 #35 on: 21-06-2013, 15:56:22 »

mi dispiace ma non riesco a seguirti  testate ....
la mia soluzione era tutta sbagliata? L'ho modificata così:

                  y   se "y è un multiplo di 3"
g2(y)=       3   se \phiy+1(y)\downarrow \wedge ymod3 \neq 0
                  3   se \phiy+1(y)\uparrow \wedge ymod3 \neq 0

Adesso è mutuamente esclusiva? io considero che se y è un multiplo di 3 debba terminare
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 #36 on: 21-06-2013, 16:26:07 »

Si, ok. Tutte le funzioni non calcolabili che dovete proporre devono necessariamente essere totali, quindi dirmi che se è un multiplo di 3 debba terminare è ovvio (deve terminare anche in tutti gli altri casi, cioè sempre).

Correggendo il tuo esercizio, nell'ultimo messaggio stavolta bensì i casi sono mutualmente esclusivi ma, almeno per il caso in cui ϕy+1 termina, devi ulteriormente esplicitare due casi: quello in cui termina con 3 (in cui farai assumere a g2 un valore diverso da 3) e quello in cui termina in un valore diverso da 3 (nel qual caso hai tutto il diritto di far assumere 3 a g2).

In ogni caso, sfruttare l'indice y+1 come codice di funzione calcolabile non ti basta, perché in questo modo, la funzione si comporta secondo la seguente regolarità:

in 0 (non multiplo di 3) si controlla cosa fa ϕ1
in 1 (non multiplo di 3) si controlla cosa fa ϕ2
in 2 (non multiplo di 3) si controlla cosa fa ϕ3
in 3 (multiplo di 3) si restituisce 3
in 4 (non multiplo di 3) si controlla cosa fa ϕ5
in 5 (non multiplo di 3) si controlla cosa fa ϕ6
in 6 (multiplo di 3) si restituisce 3
in 7 (non multiplo di 3) si controlla cosa fa ϕ8
in 8 (non multiplo di 3) si controlla cosa fa ϕ9
in 9 (multiplo di 3) si restituisce 3
in 10 (non multiplo di 3) si controlla cosa fa ϕ11
...

stai notando che non controlliamo mai cosa avviene alle funzioni ϕ0, ϕ4, ϕ7, ϕ10, ecc... (cioè tutte le funzioni calcolabili con codici i successivi dei multipli di tre, e inoltre la funzione con codice 0)?

Tu devi passare da tutte queste funzioni, in un modo o nell'altro!
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 #37 on: 21-06-2013, 17:06:56 »



                  y   se "y è un multiplo di 3"
g2(y)=       3   se \phiy(y)\downarrow\wedge ymod3 \neq 0 \wedge b \neq 3
                  6   se \phiy(y)\downarrow\wedge ymod3 \neq 0 \wedge b=3
                  3   se \phiy(y)\uparrow \wedge ymod3 \neq 0

così? grazie alla tua osservazione ho capito che per passare da tutti gli indici non bisogna piegarla la diagonale!
Dico bene?

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 #38 on: 21-06-2013, 17:38:11 »

così? grazie alla tua osservazione ho capito che per passare da tutti gli indici non bisogna piegarla la diagonale!
Dico bene?
Così sistemi il problema della copertura di tutti i casi (mutualmente esclusivi) possibili, ma ancora non hai manipolato la diagonale.
Perchè, bensì, quando ci vengono imposte condizioni dall'alto su cosa debba restituire la nostra funzione non calcolabile in certi punti, allora abbiamo bisogno di piegare/traslare/estendere/ruotare(?, no ruotare no  nono, scherzavo) la diagonale .

Come prima, osserva dalla seguente regolarità cosa andiamo a controllare e cosa no:

in 0 (non multiplo di 3) si controlla cosa fa ϕ0
in 1 (non multiplo di 3) si controlla cosa fa ϕ1
in 2 (non multiplo di 3) si controlla cosa fa ϕ2
in 3 (multiplo di 3) si restituisce 3
in 4 (non multiplo di 3) si controlla cosa fa ϕ4
in 5 (non multiplo di 3) si controlla cosa fa ϕ5
in 6 (multiplo di 3) si restituisce 3
in 7 (non multiplo di 3) si controlla cosa fa ϕ7
in 8 (non multiplo di 3) si controlla cosa fa ϕ8
in 9 (multiplo di 3) si restituisce 3
in 10 (non multiplo di 3) si controlla cosa fa ϕ10
...

stavolta non controlliamo mai cosa avviene alle funzioni ϕ3, ϕ6, ϕ7, ϕ9, ecc... (cioè tutte le funzioni calcolabili con codici multipli di tre)!

Tu devi passare da tutte queste funzioni, in un modo o nell'altro!
Anche da quelle da cui non stai passando ora.

[...]

Mi sto rendendo conto che un esercizio di questo tipo è troppo complicato anche per me. Stavo per scrivere una soluzione ma mi sono bloccato in un punto oscuro...

Fai finta che questi esercizi non te li abbia mai dati...
In effetti, nemmeno il prof. Cantone aveva mai osato tanto ai tempi in cui la insegnava lui ...

Ho voluto volare con le mie ali di cera fino al Sole, e mi si sono sciolte no!
(no vabbè, è che dovrei studiarci molto di più, molto più di quanto richiesto e possibile nel tempo di un'esame )
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 #39 on: 21-06-2013, 19:51:27 »

 [Emoticon] Rosik Asd tu mi fai impazzire!!!!!!!!!!!!!!!!!!!!!

da un lato sono contenta però... almeno so che se il mio cervello si rifiuta proprio di collaborare vuol dire che la difficoltà è superiore di quella prevista per l'esame! (almeno spero) ... incrocio le dita e posto altre soluzioni... rimai ormai un ultimo week-end nella migliore delle ipotesi!!!!!
Logged
Giuseppe Scollo
Moderator
Forumista Esperto
*****
Offline Offline

Posts: 1.389


« Reply #40 on: 22-06-2013, 11:36:05 »

in 0 (non multiplo di 3) si controlla cosa fa ϕ0
Hmm, qui ci vuole un'aggiustatina: 0 è un multiplo di 3 (il multiplo nullo). Temo che occorrano correzioni analoghe in post precedenti, per esempio 0 ≡ 0 (mod 3).
« Last Edit: 22-06-2013, 11:37:43 by Giuseppe Scollo » Logged
Giuseppe Scollo
Moderator
Forumista Esperto
*****
Offline Offline

Posts: 1.389


« Reply #41 on: 15-07-2013, 14:41:04 »

Quote
Suggerimento: siccome il codominio che vi ho imposto è infinito, non vi basta "traslare" di qualche posizione (un numero finito) la diagonale, ma dovete piegarla!
In particolare, potete fare in modo che nei punti pari la funzione assuma lo stesso valore del punto, e nei dispari ci infilate i valori diversi da tutte le funzioni calcolabili (in modo che si passi da tutte le funzioni calcolabili, e non sia uguale a nessuna di esse, in almeno un punto).

così com'è?

           y                  se y pari
f(y)=  \phi(y-1)/2+1     y dispari \wedge  \phi(y-1)/2\downarrow
          0                   se y dispari \wedge \phi(y-1)/2\uparrow


ormai la disperazione fa parte di me  testate
Perfetto!!!
Hai dimenticato solo di specificare l'argomento delle funzioni \fs{5}\phi_{\frac{y-1}{2}}, che può essere qualsiasi stavolta (y stesso andrà benissimo!) ! Congratulescions!
Non so perché (o forse lo so ma non posso dirlo), mi è tornato in mente questo esercizio, ho riletto questa interessante discussione, e ho scovato la necessità di una piccola correzione. Poiché si impone che l'immagine della funzione sia l'insieme dei numeri pari, occorre non solo che i pari ci siano tutti (e fin qui la soluzione proposta va bene: il "piegamento" della diagonale ne è una rotazione, in termini geometrici), ma anche che la funzione assuma soltanto valori pari, e qui non va bene limitarsi a garantire (ai fini della non calcolabilità) che sui dispari la funzione assuma "valori diversi da tutte le funzioni calcolabili": diversi, certamente, purché comunque pari. Tenendo conto di questo, direi che la correzione della soluzione proposta porta alla seguente:

           y                                                       se y pari
f(y) \phi(y-1)/2(y)+(2 - (\phi(y-1)/2(y) mod 2))    se y dispari \wedge  \phi(y-1)/2(y)\downarrow
           0                                                       se y dispari \wedge \phi(y-1)/2(y)\uparrow
Quote
Poi devi solo fare la solita "tiritera" della non calcolabilità dimostrandola tramite assurdi
A proposito, non è davvero necessaria quella "tiritera": a beneficio del risparmio di tempo, carta e inchiostro, basta dire che la funzione specificata è diversa da ogni funzione calcolabile, pertanto non è calcolabile.

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 #42 on: 17-07-2013, 09:47:25 »

[...] lo so ma non posso dirlo [...]
univ

Grazie per la correzione. In effetti avevo dimenticato di controllare il fatto che i valori assunti dovessero essere pari.
Nella sua soluzione, ha accorpato in un'unica espressione calcolabile ciò che si deve restituire nel caso in cui
\fs{6}y\text{ dispari }\wedge\phi_{\frac{y-1}{2}}\({y}\)\downarrow
mentre normalmente, anche per una più lineare dimostrazione della incalcolabilità, noi studenti degli altri anni siamo stati abituati a separare nettamente i casi in cui \fs{6}\phi_{\frac{y-1}{2}}\({y}\) è pari o dispari .

Ma sottraendo il valore assunto dalla funzione caratteristica del predicato "è dispari" calcolato sull'argomento \fs{6}\phi_{\frac{y-1}{2}}\({y}\), al valore di \fs{6}\phi_{\frac{y-1}{2}}\({y}\) stesso (e sommando 2 per renderlo certamente diverso da esso stesso), si ottiene un valore pari .
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
ɹǝǝ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 #43 on: 13-09-2013, 23:38:05 »

Avanti, ve ne risolvo uno per tutti:

Fissato \fs{3}k\in\mathbb{N}^{+}, dimostrare che esiste una funzione unaria, totale e non calcolabile \fs{4}g tale che \fs{4}g\({kx}\)=kx,\;\forall x\in\mathbb{N}

Si consideri la seguente \fs{4}g


\fs{6}g(x)=\{\begin{matrix}x&&\text{se }k|x\\\phi_{\lfloor{\frac{x}{k}}\rfloor}\({x}\)+1&&\text{se }k\not{|}x\;\wedge\;\phi_{\lfloor{\frac{x}{k}}\rfloor}\({x}\)\downarrow\\0&&\text{se }k\not{|}x\;\wedge\;\phi_{\lfloor{\frac{x}{k}}\rfloor}\({x}\)\uparrow\end{matrix}

Prima di tutto, verifichiamo che una tale funzione rispetti la condizione data.
Ebbene, se \fs{4}k|x (cioè se l'argomento passato è del tipo \fs{4}x=ky,\;y\in\mathbb{N}), allora la funzione assumerà proprio il valore \fs{4}x=ky, come volevasi.

Adesso, invece, asserisco che \fs{4}g è non calcolabile.

Per assurdo, sia \fs{4}g calcolabile. Allora \fs{4}\exists e\in\mathbb{N} tale che \fs{4}\phi_e=g.

Vediamo cosa accade, allora, nel punto \fs{4}x=ke+1.
Per prima cosa, notiamo che \fs{4}x=ke+1\equiv 1\({\text{mod} k}\)\Longrightarrow k\not{|}x e, inoltre, che \fs{4}\lfloor{\frac{x}{k}}\rfloor=\lfloor{\frac{ke+1}{k}}\rfloor=e.

Allora, visto che \fs{4}k\not{|}x, ci sono solo due casi possibili:
  • \fs{4}\phi_e\({ke+1}\)\downarrow. Allora \fs{4}\phi_e\({ke+1}\)=g\({ke+1}\)=\phi_e\({ke+1}\)+1\Longrightarrow 0=1 Assurdo

  • \fs{4}\phi_e\({ke+1}\)\uparrow. Allora \fs{4}\phi_e\({ke+1}\)=g\({ke+1}\)=0\Longrightarrow\phi_e\({ke+1}\)\downarrow Assurdo

In tutti i casi possibili, otteniamo un assurdo. L'assurdo nasce dall'aver supposto che \fs{4}g fosse calcolabile, quindi \fs{4}g è non 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
Pages: 1 2 [3]   Go Up
Print
Jump to: