Forum Informatica Unict

LAUREA MAGISTRALE => Teoria della Computabilità, 9 CFU => Topic started by: denote on 23-03-2011, 12:16:03



Title: Esercizio su funzione non calcolabile
Post by: denote on 23-03-2011, 12:16:03
Salve ragazzi e professore. Sono imbattuto in un esercizio che dice :
Esiste una funzione totale monotona crescente non calcolabile?
Io ho fatto cosi':

f(x) =

\varphi_{x} (x)+1 + f(x-1)
se x > 0 e  \varphi_{x} (x) e' definita

0
se x=0 se \varphi_{0} (0) e' definita

x
altrimenti

Secondo voi e' giusto?


Title: Re:Esercizio su funzione non calcolabile
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 23-04-2011, 01:27:56
Hai espresso f\(x\) in un modo in qualche modo ricorsivo, senza però formalizzare la ricorsione.

Io avrei risposto così a questo esercizio:


Consideriamo \fs{4}f\(x\)=\{{\begin{matrix} \phi_x\({x}\)+1 & \text{se }\phi_x(x)\downarrow \\1 & \text{se }\phi_x(x)\uparrow \end{matrix}}

Questa funzione è non calcolabile.
Per assurdo, se \fs{4}f fosse calcolabile, sia \fs{4}e il codice di un programma che la calcola.
Allora avremmo che:
- se \fs{4}\phi_e(e)\downarrow, allora: \fs{4}\phi_e(e)=_a\;f(e) =_b\;\phi_e(e)+1\Rightarrow \phi_e(e)=\phi_e(e)+1\Rightarrow 0=1 Assurdo.
- se \fs{4}\phi_e(e)\uparrow, allora: \fs{4}\phi_e(e)=_a\;f(e) =_b\;1, ma \fs{4}\({\phi_e(e)\uparrow \wedge f(e)\downarrow}\)\Rightarrow \phi_e\neq f Assurdo (poiché \fs{4}e era il codice di un prog. che calcola \fs{4}f).

\fs{4}=_a: perché \fs{4}e è codice di un programma che calcola \fs{4}f;
\fs{4}=_b: per definizione di \fs{4}f;

In entrambi i casi, otteniamo un assurdo: l'assurdo proviene dall'unica ipotesi fatta arbitrariamente, cioè che \fs{4}f fosse calcolabile, di conseguenza \fs{4}f non è calcolabile.

Dimostrato ciò, consideriamo la funzione \fs{4}h(x)=\sum_{y<x+1}{f(y)}
Poiché \fs{4}f è totale, allora la somma di un numero finito di valori assunti da essa è finito, perciò anche \fs{4}h è totale; inoltre, osserviamo la regolarità:
\fs{4}h(0)=f(0) \\h(1)=f(0)+f(1)=h(0)+f(1) \\h(2)=f(0)+f(1)+f(2)=h(1)+f(2) \\h(3)=f(0)+f(1)+f(2)+f(3)=h(2)+f(3) \\ \vdots \\h(n)=f(0)+f(1)+...+f(n)=h({n-1})+f(n)

La funzione possiamo riassumerla in questa definizione, quindi:
\fs{4}\{{h(0)=f(0) \\h(n)=h({n-1})+f(n),\;n\geq 1}

Cambiando punto di vista, notiamo che anche \fs{4}f può essere espressa in funzione di \fs{4}h, così:
\fs{4}\{{f(0)=h(0) \\f(n)=h(n)-h({n-1}),\;n\geq 1}

Supponiamo, per assurdo, che \fs{4}h sia calcolabile.
Allora, la funzione \fs{4}f(x)=\{{\begin{matrix} h(x) & \text{se }x=0 \\ h(x)-h({x-1}) & \text{se }x\geq 1 \end{matrix}} è calcolabile, poiché definita per casi ove i due casi sono mutualmente esclusivi e la loro disgiunzione esclusiva è vera (esattamente uno dei casi è vero), i due casi sono legati a predicati decidibili e il valore in ciascun caso si trova mediante una funzione calcolabile (direttamente nel primo caso e come composizione di funzioni calcolabili nel secondo caso)

Tuttavia, avevamo prima dimostrato che \fs{4}f non era calcolabile \fs{4}\Rightarrow Assurdo.
L'assurdo proviene dall'unica ipotesi arbitraria che abbiamo sfruttato, cioè che \fs{4}h fosse calcolabile, di conseguenza abbiamo provato che \fs{4}h non è calcolabile.

Ora, studiando la funzione \fs{4}h ci si accorge che essa è monotona crescente.
Infatti, una funzione \fs{4}g è monotona crescente in un insieme di punti \fs{4}X\Leftrightarrow \forall x_1, x_2\in X, x_1<x_2\Rightarrow g(x_1)<g(x_2)
Siano, allora, \fs{4}x_1, x_2\in\mathbb{N}, x_1<x_2
Per definizione si ha che:
\bullet \fs{4}h(x_1)=\sum_{y<x_1+1}{f(x)}
\bullet \fs{4}h(x_2)=\sum_{y<x_2+1}{f(x)}=\sum_{y<x_1+1}{f(x)}+\sum_{y=x_1+1}^{x_2}{f(x)}=h(x_1)+\sum_{y=x_1+1}^{x_2}{f(x)}

Siccome \fs{4}\forall x\in\mathbb{N} f(x)\geq 1, allora \fs{4}\sum_{y=x_1+1}^{x_2}{f(x)}\geq x_2-x_1-1+1=x_2-x_1>0\Leftrightarrow x_2>x_1che è vera per ipotesi.

Perciò, \fs{4}\sum_{y=x_1+1}^{x_2}{f(x)}>0\Rightarrow h(x_2)=h(x_1)+\sum_{y=x_1+1}^{x_2}{f(x)}>h(x_1) cioè \fs{4}h(x_2)>h(x_1) da cui la monotona crescenza di \fs{4}h. ∎


Title: Re:Esercizio su funzione non calcolabile
Post by: denote on 23-04-2011, 08:03:16
Capisco che ti sei impegnato e ti ringrazio per la tua soluzione il mio problema era però sapere se la mia soluzione fosse corretta .

Perché secondo te non ho "formalizzato la ricorsione". E cosa significa?


Title: Re:Esercizio su funzione non calcolabile
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 23-04-2011, 08:18:17
L'intuizione del tuo ragionamento è giusto, però per essere corretto, l'esercizio richiede di argomentare adeguatamente i risultati ottenuti, cioè dovresti includere una dimostrazione formale che la tua funzione \fs{2}f è totale, monotona crescente e non calcolabile .penso...


Title: Re:Esercizio su funzione non calcolabile
Post by: denote on 23-04-2011, 08:19:27
Ah ok perfetto. Certo devo poi formalizzare


Title: Re:Esercizio su funzione non calcolabile
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 23-04-2011, 08:31:57
Anzi no, ho trovato un punto sbagliato.

Nella definizione per casi, nessuno ti garantisce che se ti trovi nel caso in cui \fs{3}\phi_x(x)\uparrow (o comunque nel generico "altrimenti") e, quindi, restituisci il valore \fs{3}f(x)=x, allora tale valore sia maggiore di \fs{3}f({x-1}) .nono.

Con una dimostrazione formale, saresti arrivato alla stessa conclusione, ma ti ho anticipato un passaggio.
Devi riconsiderare questo caso e cambiare \fs{3}f opportunamente.

Ciao ciao .ciaociao.


Title: Re:Esercizio su funzione non calcolabile
Post by: denote on 23-04-2011, 08:44:37
Ok hai ragione . Grazie mille ho corretto