Forum Informatica Unict

LAUREA MAGISTRALE => Teoria della Computabilità, 9 CFU => Topic started by: Vincenzion on 17-05-2011, 09:50:44



Title: prova d'esame del 13/06/2007 (esercizio 1)
Post by: Vincenzion 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"


Title: Re:prova d'esame del 13/06/2007 (esercizio 1)
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ 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 .nono:
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.


.ciaociao


Title: Re:prova d'esame del 13/06/2007 (esercizio 1)
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ 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 .sisi.
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 .sisi.

Buon pomeriggio .smile.


Title: Re:prova d'esame del 13/06/2007 (esercizio 1)
Post by: Vincenzion on 17-05-2011, 17:41:37
grazie mille! |-O