Pages: [1]   Go Down
Print
Author Topic: Esercizi con diagonalizzazione di Cantor  (Read 2815 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
student
Matricola
*
Offline Offline

Posts: 49


« on: 05-12-2013, 15:23:38 »

Questa volta sono alle prese con la diagonalizzazione.

"Utilizzando il metodo diagonale di Cantor, si dimostri che esiste una funzione f:N->N totale e non calcolabile avente come codominio l'insieme {0, 1, 2, ..., 9}".

Io ho provato a risolvere così:

f(x) = { rm(10, y) se \phi x (x) \downarrow y \geq 9
\phi x (x) + 1 altrimenti}

Può funzionare?

Grazie,
lg
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.446


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


WWW
« Reply #1 on: 05-12-2013, 16:45:59 »

Può funzionare?
No. Ci sono tanti motivi per cui non funziona.

Ma quello più evidente è che la funzione è mal definita: tu hai scritto che se la funzione \fs{3}\phi_x(x) è definita ED assume un valore maggiore o uguale a 9, allora viene un certo numero dipendente da quello, altrimenti è il valore di \fs{3}\phi_x(x)+1, ma ALTRIMENTI equivale a dire "se è definita e assume un valore minore di 9 OPPURE se non è definita", quindi comprende anche il caso in cui non sia definita, e se non è definita (cioè va in loop) come puoi sommarci un valore??? La risposta è: no, non puoi. È mal definita. testate
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
student
Matricola
*
Offline Offline

Posts: 49


« Reply #2 on: 05-12-2013, 19:25:54 »

Ok, procediamo per gradi. Sdoppio il secondo caso della definizione:

\fs{4}f(x) = \{\begin{matrix}\text{rm}(10, y)&&&\text{se }\phi_x (x) \downarrow y \geq \9 \\0&&&\text{se }\phi_x (x) \uparrow \\ \phi_x (x) + 1&&&\text{altrimenti}\end{matrix}

Così siamo più vicini alla soluzione?

Grazie ancora,
lg

EDIT del mod.: corretta formulazione in latex
« Last Edit: 05-12-2013, 21:45:10 by ɹǝǝuıƃuǝsɹǝʌǝɹ » Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.446


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


WWW
« Reply #3 on: 05-12-2013, 21:56:23 »

Hai certamente risolto l'ambiguità della mal-definizione.

Ora quella è una funzione ben precisa con la sua dignità .

Ma invece di dirti se ora è corretto oppure no, ti invito a continuare la risoluzione dell'esercizio accludendo la necessaria opportuna dimostrazione di correttezza.

In particolare, in questo esercizio, devi:

  • dimostrare che il codominio (range) della funzione costruita è effettivamente l'insieme {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, e cioè che ciascuno dei valori di quell'insieme viene assunto da f in almeno un punto (un buon modo di dimostrare questa cosa è esibire un x tale che f(x) sia quel numero, per ognuno di loro, o esibire una riccorenza che faccia la stessa cosa )

  • dimostrare che la funzione f non è calcolabile (solita tiritera -termine preso in prestito da tue colleghe molto simpatiche che studiavano questa materia a suo tempo- della diagonalizzazione )

La totalità e unarietà della funzione è auto-evidente dalla sua formulazione per casi  ok
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
student
Matricola
*
Offline Offline

Posts: 49


« Reply #4 on: 06-12-2013, 12:11:57 »

Mi sono accorto che c'è un piccolo errore, perché nel primo caso, per y = 9, RM(10, 9) = 10 \notin {0, ... , 9}. Potrei risolvere così?

\fs{4}f(x) = \{\begin{matrix}\text{rm}(10, y)&&&\text{se } \phi_x (x) \downarrow y \geq \10 \\0&&&\text{se }\phi_x (x) \uparrow \\ \text{rm}(9, \phi_x (x))&&&\text{altrimenti}\end{matrix}

Abbiamo anche formulato un'altra versione, che forse potrebbe andare:

\fs{4}f(x) = \{\begin{matrix}\phi_x (x) + 1&&&\text{se } \0 \leq \phi_x (x) \leq \8 \\0&&&\text{se } \phi_x (x) \downarrow y \geq \9 \\ \1&&&\text{altrimenti}\end{matrix}

Ho anche qualche dubbio sui suggerimenti dei punti a) e b).

a) Non è troppo "rudimentale" dire che (nel caso, ad esempio, della prima formalizzazione della f), per x che va da 10 a 19 copro l'immagine con il primo caso?

b) Si tratta di applicare il teorema secondo cui «Esiste una funzione totale e unaria che non è calcolabile»? In questo caso, è sufficiente dire che, data la definizione di funzione appena esposta, f \neq \phi_x (x) \forall x \inN, e quindi la f è banalmente totale e non calcolabile?

Grazie,
lg
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.446


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


WWW
« Reply #5 on: 06-12-2013, 15:28:32 »

Mi sono accorto che c'è un piccolo errore, perché nel primo caso, per y = 9, RM(10, 9) = 10 \notin {0, ... , 9}.
Falso.

RM(10, 9)=9

Ma hai comunque centrato parzialmente un problema, che non è quello esposto da te...

Potrei risolvere così?

\fs{4}f(x) = \{\begin{matrix}\text{rm}(10, y)&&&\text{se } \phi_x (x) \downarrow y \geq \10 \\0&&&\text{se }\phi_x (x) \uparrow \\ \text{rm}(9, \phi_x (x))&&&\text{altrimenti}\end{matrix}
Sì, esatto.

Abbiamo anche formulato un'altra versione, che forse potrebbe andare:

\fs{4}f(x) = \{\begin{matrix}\phi_x (x) + 1&&&\text{se } \0 \leq \phi_x (x) \leq \8 \\0&&&\text{se } \phi_x (x) \downarrow y \geq \9 \\ \1&&&\text{altrimenti}\end{matrix}
Sì, anche così è corretta, ma la forma con il resto la trovavo più elegante .

Ho anche qualche dubbio sui suggerimenti dei punti a) e b).

a) Non è troppo "rudimentale" dire che (nel caso, ad esempio, della prima formalizzazione della f), per x che va da 10 a 19 copro l'immagine con il primo caso?
Non solo è rudimentale, ma è potenzialmente sbagliato. Chi ti garantisce che nei casi da x=10 a x=19 la funzione f assumerà i valori da 0 a 9? Tu non sai cosa accade a ϕx (x) nei casi da x=10 a x=19 .

b) Si tratta di applicare il teorema secondo cui «Esiste una funzione totale e unaria che non è calcolabile»? In questo caso, è sufficiente dire che, data la definizione di funzione appena esposta, f \neq \phi_x (x) \forall x \inN, e quindi la f è banalmente totale e non calcolabile?
No. Bisogna fare vedere, tramite dimostrazione per assurdo, che se f fosse (appunto, per assurdo) calcolabile, allora avrebbe almeno un codice di programma associato a un programma che la calcola. Qualsiasi sia questo codice, ci porta ad un assurdo. Questa dimostrazione dipende fortemente da come è stata definita la funzione, o meglio dai "casi" tramite cui è stata definita la funzione f.
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
Giuseppe Scollo
Moderator
Forumista Esperto
*****
Offline Offline

Posts: 1.383


« Reply #6 on: 06-12-2013, 15:49:16 »

Mi sono accorto che c'è un piccolo errore, perché nel primo caso, per y = 9, RM(10, 9) = 10 \notin {0, ... , 9}. Potrei risolvere così?

\fs{4}f(x) = \{\begin{matrix}\text{rm}(10, y)&&&\text{se } \phi_x (x) \downarrow y \geq \10 \\0&&&\text{se }\phi_x (x) \uparrow \\ \text{rm}(9, \phi_x (x))&&&\text{altrimenti}\end{matrix}

Abbiamo anche formulato un'altra versione, che forse potrebbe andare:

\fs{4}f(x) = \{\begin{matrix}\phi_x (x) + 1&&&\text{se } \0 \leq \phi_x (x) \leq \8 \\0&&&\text{se } \phi_x (x) \downarrow y \geq \9 \\ \1&&&\text{altrimenti}\end{matrix}

Ho anche qualche dubbio sui suggerimenti dei punti a) e b).

a) Non è troppo "rudimentale" dire che (nel caso, ad esempio, della prima formalizzazione della f), per x che va da 10 a 19 copro l'immagine con il primo caso?
Bisogna intendersi sulla terminologia, innanzitutto. Se si richiede che {0, ... , 9} sia il codominio della f, allora entrambe le soluzioni vanno bene perché la f non può assumere valori estranei a questo intervallo, ma ritengo che la formulazione del problema non sia esatta. Penso invece che si voglia che l'intervallo {0, ... , 9} sia l'immagine (ingl. range) della f, il che naturalmente complica il problema. La difficoltà che vedo per la dimostrazione del punto (a), con entrambe le varianti proposte per la f, è che l'immagine della f dipende da come è definita l'enumerazione delle funzioni calcolabili: cosa ci garantisce che con le definizioni date si ottengano tutti i valori 0,...,9 come immagini della f, per una data (quale?) enumerazione della classe delle funzioni unarie calcolabili? Francamente non lo so, e direi comunque che sarebbe meglio risolvere il problema indipendentemente da qualsiasi enumerazione particolare. Per far questo, è sufficiente far assumere alla f i dieci valori desiderati in una porzione finita del dominio, e renderla diversa da ciascuna funzione calcolabile in almeno un punto della rimanente porzione (infinita) del dominio, avendo cura che comunque non si estenda la sua immagine al di fuori di quella desiderata. Per esempio: f(x) = x per x < 10, mentre per x > 9 basta una piccola traslazione della diagonale per adattare ciascuna delle due definizioni proposte, avendo cioè cura di sostituire l'indice x (e non l'argomento!) della φ con x-10.
Quote
b) Si tratta di applicare il teorema secondo cui «Esiste una funzione totale e unaria che non è calcolabile»? In questo caso, è sufficiente dire che, data la definizione di funzione appena esposta, f \neq \phi_x (x) \forall x \inN, e quindi la f è banalmente totale e non calcolabile?
Non vedo a che serva invocare un teorema quando qui basta dire che la f non può essere calcolabile perché differisce in almeno un punto da qualsiasi funzione calcolabile. Infatti (con la traslazione suggerita): f(10) ≠ φ0(10), f(11) ≠ φ1(11) ecc., ovvero in generale f(x+10) ≠ φx(x+10) per ogni x, quindi f ≠ φx per ogni x.
« Last Edit: 06-12-2013, 15:52:05 by Giuseppe Scollo » Logged
student
Matricola
*
Offline Offline

Posts: 49


« Reply #7 on: 06-12-2013, 15:53:24 »

Falso.

RM(10, 9)=9

Hai ragione, non so perché avevo invertito le variabili. La formulazione iniziale di RM dovrebbe andare.

Ma hai comunque centrato parzialmente un problema, che non è quello esposto da te...

Riguardava il terzo caso?

Non solo è rudimentale, ma è potenzialmente sbagliato. Chi ti garantisce che nei casi da x=10 a x=19 la funzione f assumerà i valori da 0 a 9? Tu non sai cosa accade a ϕx (x) nei casi da x=10 a x=19 .

Allora ho capito male. Cosa intendevi prima per «un buon modo di dimostrare questa cosa è esibire un x tale che f(x) sia quel numero, per ognuno di loro»?

No. Bisogna fare vedere, tramite dimostrazione per assurdo, che se f fosse (appunto, per assurdo) calcolabile, allora avrebbe almeno un codice di programma associato a un programma che la calcola. Qualsiasi sia questo codice, ci porta ad un assurdo. Questa dimostrazione dipende fortemente da come è stata definita la funzione, o meglio dai "casi" tramite cui è stata definita la funzione f.

Ci rifletto. Mi sembra che ci fosse un apposito teorema in merito.

Grazie,
lg
Logged
student
Matricola
*
Offline Offline

Posts: 49


« Reply #8 on: 06-12-2013, 15:59:04 »

Bisogna intendersi sulla terminologia, innanzitutto. Se si richiede che {0, ... , 9} sia il codominio della f, allora entrambe le soluzioni vanno bene perché la f non può assumere valori estranei a questo intervallo, ma ritengo che la formulazione del problema non sia esatta. Penso invece che si voglia che l'intervallo {0, ... , 9} sia l'immagine (ingl. range) della f, il che naturalmente complica il problema. La difficoltà che vedo per la dimostrazione del punto (a), con entrambe le varianti proposte per la f, è che l'immagine della f dipende da come è definita l'enumerazione delle funzioni calcolabili: cosa ci garantisce che con le definizioni date si ottengano tutti i valori 0,...,9 come immagini della f, per una data (quale?) enumerazione della classe delle funzioni unarie calcolabili? Francamente non lo so, e direi comunque che sarebbe meglio risolvere il problema indipendentemente da qualsiasi enumerazione particolare. Per far questo, è sufficiente far assumere alla f i dieci valori desiderati in una porzione finita del dominio, e renderla diversa da ciascuna funzione calcolabile in almeno un punto della rimanente porzione (infinita) del dominio, avendo cura che comunque non si estenda la sua immagine al di fuori di quella desiderata. Per esempio: f(x) = x per x < 10, mentre per x > 9 basta una piccola traslazione della diagonale per adattare ciascuna delle due definizioni proposte, avendo cioè cura di sostituire l'indice x (e non l'argomento!) della φ con x-10.

A questo punto la domanda non è banale: il prof. Cantone, dai cui compiti abbiamo tratto questo esercizio, parla sempre di codominio. Premesso che, per quanto ne so io, range = immagine \neq codominio, quando Cantone parla di codominio, dobbiamo tradurre con immagine?

lg
Logged
student
Matricola
*
Offline Offline

Posts: 49


« Reply #9 on: 06-12-2013, 16:27:37 »

Bisogna intendersi sulla terminologia, innanzitutto. Se si richiede che {0, ... , 9} sia il codominio della f, allora entrambe le soluzioni vanno bene perché la f non può assumere valori estranei a questo intervallo, ma ritengo che la formulazione del problema non sia esatta.

Noto adesso un'altra cosa. Il testo chiede di dimostrare che esiste una funzione f:N\rightarrowN, quindi nel nostro caso (correggetemi se sbaglio) il codominio dovrebbe essere N e l'immagine {0, ... ,9}. Quindi la nostra f non può assumere valori diversi da {0, ... ,9} (che sono un sottoinsieme del codominio N), giusto?
Anche perché noi le soluzioni le avevamo formulate considerando {0, ... ,9} come l'immagine della f:N\rightarrowN.
lg
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.446


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


WWW
« Reply #10 on: 06-12-2013, 16:52:06 »

A questo punto la domanda non è banale: il prof. Cantone, dai cui compiti abbiamo tratto questo esercizio, parla sempre di codominio. Premesso che, per quanto ne so io, range = immagine \neq codominio, quando Cantone parla di codominio, dobbiamo tradurre con immagine?

lg
Sì, in effetti per il prof. Cantone, codominio=range boh, lui la intendeva così .

Basta chiarire prima dell'esame il significato di ciò, e siete a posto ok.

Allora, diciamo che va bene la vostra formulazione, ma dovete dimostrare che ciò che dite è corretto.

Suggerimento: potete evitare di traslare la diagonale di 10 posizioni (come suggerito dal professore, e come anche io ho inizialmente pensato per una forma-mentis ormai consolidata) considerato che, per ogni funzione costante, esiste almeno un codice ... qualunque godelizzazione usiamo ! Ma non dico altro nono...  Il resto spetta a voi! Se non capite questo suggerimento, usate quello del professore pray...
No. Bisogna fare vedere, tramite dimostrazione per assurdo, che se f fosse (appunto, per assurdo) calcolabile, allora avrebbe almeno un codice di programma associato a un programma che la calcola. Qualsiasi sia questo codice, ci porta ad un assurdo. Questa dimostrazione dipende fortemente da come è stata definita la funzione, o meglio dai "casi" tramite cui è stata definita la funzione f.

Ci rifletto. Mi sembra che ci fosse un apposito teorema in merito.
No, non mi pare proprio nono...
Il "teorema" te lo devi inventare tu, di volta in volta, mostrando come in ogni caso di definizione, qualsiasi sia il valore supposto esistente (per assurdo) del codice del (di un) programma che calcola f, esso porta ad un assurdo. Almeno, il prof. Cantone voleva si facesse così questa dimostrazione ...
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
Giuseppe Scollo
Moderator
Forumista Esperto
*****
Offline Offline

Posts: 1.383


« Reply #11 on: 06-12-2013, 20:06:13 »

Sì, in effetti per il prof. Cantone, codominio=range boh, lui la intendeva così .
La terminologia è andata assestandosi nel corso degli anni... Peraltro a me pare che non sia del tutto assestata. Consideriamola con riguardo al dominio: le funzioni di nostro interesse sono tutte di tipo N → N, ma diciamo che quelle parziali hanno come dominio un sottoinsieme di N. In altri testi si direbbe che hanno dominio N, e dominio di esistenza (o campo di esistenza, o dominio di definizione ecc.) quello che noi chiamiamo dominio. La nostra terminologià è consistente con quella relazionale che vuole che una relazione binaria r ⊆ A ⨯ B abbia come dominio il sottoinsieme di A costituito dai suoi elementi a tali che, per qualche b in B, (a,b) ∈ r (una funzione è un particolare tipo di relazione binaria), tuttavia ciò non significa che questa sia la terminologia ottimale: per uniformità linguistica, se "codominio" è determinato dal tipo della funzione, mentre "immagine" lo è dal suo comportamento, allora sembrerebbe meglio associare anche "dominio" al tipo e usare un altro termine per il suo sottoinsieme determinato dal comportamento.
Quote
Basta chiarire prima dell'esame il significato di ciò, e siete a posto ok.
Tranquilli, in tutti i testi di esame di quest'anno si usano i termini "dominio" e "immagine" come detto sopra. E comunque, in caso di dubbio basta chiedere (anche in sede di esame).
Quote
considerato che, per ogni funzione costante, esiste almeno un codice ... qualunque godelizzazione usiamo
vuole suggerire che ogni costante incontra comunque la diagonale, no? Qualunque sia l'enumerazione... Potenza della geometria!
Logged
Pages: [1]   Go Up
Print
Jump to: