Pages: [1]   Go Down
Print
Author Topic: prova d'esame del 13/06/2007 (esercizio 1)  (Read 1012 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Vincenzion
Matricola
*
Offline Offline

Gender: Male
Posts: 27



« on: 17-05-2011, 09:50:44 »

Buongiorno colleghi,
ho un dubbio con l'esercizio di cui in oggetto il cui testo è il seguente:

"Sia f : N → N una funzione calcolabile e totale.
Si dimostri che esiste una funzione g non calcolabile e totale tale che g(x) > f(x), per ogni x ∈ N."

Io ho provato a risolverlo, più o meno, così:

Essendo f calcolabile, allora f=ϕa per qualche a ϵ N
quindi pongo g(x)= . f(x)+1 se ϕx(x)↓
                               . 0         altrimenti

-->NOTA g(x) sarà sempre maggiore di f(x) <---

essendo f(x)=ϕx(x) in quanto calcolabile
quindi g(x) diventa

g(x)= .ϕx(x)+1 se ϕx(x)↓
         . 0         altrimenti

e per il teorema di cantor non è calcolabile.....

premetto che non ho potuto sequire le lezioni e sto basandomi su quanto letto sulle slide e qualche dispensa ed esercizi svolti da altri colleghi negli anni passati...
quindi se ho sparato qualche m....... "corrigetemi se sbalio"
Logged

--
i miei rispetti,
Vincenzion

_________

There is a Land far far away, where there is no night there's only day.
Look into the Book of Life and you will see that there's a Land far far away.
_________
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


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


WWW
« Reply #1 on: 17-05-2011, 16:23:44 »

-->NOTA g(x) sarà sempre maggiore di f(x) <---
Quello che tu hai espresso come "nota" in realtà è un fatto che andrebbe dimostrato.
Ti dirò di più: non è vero!
Dimostrazione:
sia \fs{3}k il codice della funzione mai definita \fs{3}f_\emptyset, cioè valga \fs{3}\phi_k=f_\emptyset, allora:
\fs{3}\phi_k\({k}\)\uparrow\Longrightarrow g\({k}\)=0\leq f\({k}\)\Longrightarrow \exists x=k: g\({x}\)\not{>}f\({x}\)
(questa diseguaglianza \fs{3}\uparrow segue da \fs{3}f:\mathbb{N}\to\mathbb{N}, quindi \fs{3}f\({x}\)\geq 0,\forall x\in\mathbb{N}, e anche k\in\mathbb{N}, qualunque sia il suo valore).

Poi c'è quest'altra cosa, che non va bene :
essendo f(x)=ϕx(x) in quanto calcolabile
In questo punto tu hai già stabilito chi è \fs{3}f, anzi l'hai caratterizzata così bene da potergli dare anche un nome famoso noi, essendo calcolabile:
\fs{3}f\({x}\)=\psi\({x,x}\), tuttavia \fs{3}\psi\({x,x}\) non è totale (basta verificare che nel punto \fs{3}k:\phi_k=f_\emptyset essa diverge).

Il resto sarebbe corretto, nel senso che segue dai ragionamenti precedenti, ma siccome i ragionamenti sono sbagliati, anche il resto è inerentemente sbagliato (eredita l'errore di fondo).

Ti do una possibile soluzione:

Si consideri \fs{3}g\({x}\)=\{{\begin{matrix}f\({x}\)+1+\phi_x\({x}\) & \phi_x(x)\downarrow \\f\({x}\)+1 &\phi_x(x)\uparrow \end{matrix}}

Verifichiamo prima di tutto che \forall x\in\mathbb{N}, g\({x}\)>f\({x}\).

\fs{3}\phi_x\({x}\)\downarrow\Longrightarrow g\({x}\)=f\({x}\)+1+\phi_x\({x}\)\geq f\({x}\)+1>f\({x}\) \\\phi_x\({x}\)\uparrow\Longrightarrow g\({x}\)=f\({x}\)+1>f\({x}\)

Adesso provo che \fs{3}g è non calcolabile.
Per assurdo, sia \fs{3}g calcolabile, e sia \fs{3}e:\phi_e=g codice di un programma che la calcola. Allora:
\fs{3}\phi_e\({e}\)\downarrow\Longrightarrow \phi_e\({e}\)=g\({e}\)=f\({e}\)+1+\phi_e\({e}\)\Longrightarrow \phi_e\({e}\)=f\({e}\)+1+\phi_e\({e}\)\Longrightarrow 0=f\({e}\)+1\Longleftrightarrow f\({e}\)=-1
Assurdo poiché \fs{3}f:\mathbb{N}\to\mathbb{N} e \fs{3}-1\not{\in}\mathbb{N}

\fs{3}\phi_e\({e}\)\uparrow\Longrightarrow g\({e}\)\downarrow ma \({\phi_e\({e}\)\uparrow\wedge g\({e}\)\downarrow}\)\Longrightarrow \phi_e\not{=}g. Assurdo perchè era \fs{3}\phi_e=g.


« Last Edit: 17-05-2011, 16:35:53 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
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


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


WWW
« Reply #2 on: 17-05-2011, 16:34:44 »

Aggiungo un piccolo suggerimento su come risolvere questi esercizi di dimostrazione dell'esistenza di funzioni non calcolabili che rispettino certe condizioni.

Siccome si vuole far vedere che per ogni codice di programma, quello è il codice di un programma che non calcola la funzione \fs{3}g che dobbiamo creare, dobbiamo fare in modo che quando \fs{3}\phi_x\({x}\) è definita, allora il valore della funzione \fs{3}g che stiamo definendo sia diverso da \fs{3}\phi_x\({x}\): nel caso in cui la funzione, però, debba essere totale (come in questo caso) o comunque definita in tale caso, si deve far dipendere il suo valore proprio da \fs{3}\phi_x\({x}\) in modo da ottenere una diseguaglianza nel punto \fs{3}e=codice di un assurdamente ipotetico programma che calcola \fs{3}g (siccome non conosciamo il valore di \fs{3}e è opportuno ottenere una diseguaglianza in tutti i punti, cioè qualsiasi sia questo valore di \fs{3}e, che poi scopriremo in realtà non esistere boh), pur ricordandosi di fare in modo che le eventuali condizioni che ci sono state poste dall'alto siano verificate .
In caso contrario, cioè quando \fs{3}\phi_x\({x}\)\uparrow ci è sufficiente assegnare un valore qualsiasi finito (stavolta è l'unico modo per renderla diversa da non-definito): visto che ci è stata imposta una condizione dall'alto, bisogna fare in modo che tale condizione sia verificata .

Buon pomeriggio .
« Last Edit: 17-07-2011, 17:25:22 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
Vincenzion
Matricola
*
Offline Offline

Gender: Male
Posts: 27



« Reply #3 on: 17-05-2011, 17:41:37 »

grazie mille! univ
Logged

--
i miei rispetti,
Vincenzion

_________

There is a Land far far away, where there is no night there's only day.
Look into the Book of Life and you will see that there's a Land far far away.
_________
Pages: [1]   Go Up
Print
Jump to: