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

Posts: 136


« 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?
Logged

Con la concorrenza di Java hanno ucciso 40 anni di computer science
ɹǝǝ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: 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. ∎
« Last Edit: 23-04-2011, 01:31: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
denote
Apprendista Forumista
**
Offline Offline

Posts: 136


« Reply #2 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?
« Last Edit: 23-04-2011, 08:17:37 by denote » Logged

Con la concorrenza di Java hanno ucciso 40 anni di computer science
ɹǝǝ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 #3 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 ...
« Last Edit: 23-04-2011, 08:20:47 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
denote
Apprendista Forumista
**
Offline Offline

Posts: 136


« Reply #4 on: 23-04-2011, 08:19:27 »

Ah ok perfetto. Certo devo poi formalizzare
Logged

Con la concorrenza di Java hanno ucciso 40 anni di computer science
ɹǝǝ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 #5 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}) .

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 .
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
denote
Apprendista Forumista
**
Offline Offline

Posts: 136


« Reply #6 on: 23-04-2011, 08:44:37 »

Ok hai ragione . Grazie mille ho corretto
« Last Edit: 23-04-2011, 08:47:22 by denote » Logged

Con la concorrenza di Java hanno ucciso 40 anni di computer science
Pages: [1]   Go Up
Print
Jump to: