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

Posts: 49


« on: 27-02-2014, 18:28:51 »

Salve a tutti,

"Usando la tecnica della diagonalizzazione, opportunamente adattata, si costruisca una funzione totale, unaria e non calcolabile f:N->N tale che f(2x + 1) = f(2x)".

\fs{3}f(x) = \{\begin{matrix}\2*\phi_{x/2} (x)+1&&&\text{se }x\;\text{e' pari }\wedge\;\phi_{x/2} (x) \downarrow\\ \2*\phi_{x/2} (x)&&&\text{se }x\;\text{e' dispari }\wedge\;\phi_{x/2} (x) \downarrow\\ x+1&&&\text{se }x\;\text{e' pari }\wedge\;\phi_{x/2} (x) \uparrow\\ x-1&&&\text{se }x\;\text{e' dispari }\wedge\;\phi_{x/2} (x) \uparrow\\\end{matrix}

Quanto sono ancora lontano dalla soluzione?

Grazie in anticipo.
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: 27-02-2014, 18:45:48 »

Wow, era nell'ultimo compito !

Allora, dobbiamo intenderci su alcuni problemi: quando x è dispari, una scrittura come \fs{4}\frac{x}{2} come va interpretata ? Giacchè su URM non abbiamo i numeri con la virgola, né (spero!!!) tu vuoi usare tecniche di adattamento di dominio in questo caso.

Inoltre, raddoppiare un numero non rende il prodotto necessariamente diverso dal numero di partenza (pensa allo zero univ!).

Questo dovrebbe essere sufficiente per farti capire come correggere la tua funzione...

Ricordo che, se hai bisogno di un aiuto più incisivo e dedicato, magari in vista del prossimo appello (quandunque sarà), io faccio lezioni private su questa materia 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 #2 on: 27-02-2014, 18:56:58 »

Allora:

- per ovviare al problema di x/2 posso aggiungere il floor?
- per sistemare il caso dello zero posso aggiungere un altro caso (scusa il gioco di parole)?

Per il resto, intanto incrociamo le dita per domani... (:

Grazie ancora.
Logged
student
Matricola
*
Offline Offline

Posts: 49


« Reply #3 on: 27-02-2014, 19:47:59 »

Nel frattempo posto anche questa, che ho finito di fare poco fa:

"Usando la tecnica della diagonalizzazione, opportunamente adattata, si costruisca una funzione parziale, unaria e non calcolabile f:N->N il cui dominio sia l'insieme dei multipli di 3 maggiori di 3".

\fs{3}f(x) = \{\begin{matrix}\phi_{x/3} (x)+1&&&\text{se }x\;\phi_{x/3} (x)\downarrow&\wedge\;&x = 3k&\text{con } k > 1 \in N\\ 0&&&\text{se }x\;\phi_{x/3} (x)\uparrow\\ \uparrow&&&\text{altrimenti}\end{matrix}

Vediamo dove ho sbagliato...
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 #4 on: 27-02-2014, 22:33:13 »

intanto incrociamo le dita per domani... (:
Domani?! No no, non ci arrivo a farti lezioni private allora, non per domani almeno nono...

Dunque...

- per ovviare al problema di x/2 posso aggiungere il floor?
Sì, ma è preferibile evitare di queste soluzioni: dimostrano che non si ha capito bene come sistemare la questione; se la si è ben capita, risulta naturale giocare con x per avere un intero senza bisogno di simili sotterfugi.

- per sistemare il caso dello zero posso aggiungere un altro caso (scusa il gioco di parole)?
Sì, potresti. Ma sarebbe superfluo.

Piuttosto, devi capire come manipolare il valore che deve restituire f.

A mente sgombra (anche dal tuo modo di risolvere l'esercizio, sbagliato...) considera questo:
oltre all'ovvio fatto tipico di questi esercizi, cioè che f deve essere (dimostrabilmente) non calcolabile, ti viene imposta "dall'alto" anche una ulteriore condizione: f(2x+1)=f(2x), ∀x

Quasi sicuramente hai bisogno di ulteriore allenamento nel capire cosa significhino queste frasi formali, nel linguaggio colloquiale; ebbene, dire ∀x, f(2x+1)=f(2x) significa semplicemente dire che la tua f, per ogni coppia di numeri (x, x+1) (ove x è pari), deve assumere il medesimo valore.
Più spicciolo f(0)=f(1), f(2)=f(3), f(4)=f(5), e così via... a coppie.

Per esempio potrebbe assumere (da 0 in poi) i seguenti valori: 5, 5, 10, 10, ↑, ↑...

Fra le proposte di risoluzione di questo esercizio, c'è quella di riciclare la prima funzione che avete studiato e dimostrato essere non calcolabile e... estenderne il grafico orizzontalmente (allargandolo di fatto).

Cioè, se per esempio tale funzione (la prima studiata non calcolabile) si chiamasse g, la vostra funzione potrebbe benissimo essere f(x)=g(⌊x/2⌋) !

Una tale f banalmente rispecchia la seconda condizione imposta dall'alto (∀x, f(2x+1)=f(2x)) e in più ha una struttura di regolarità e ricorsività intrinsecamente non-calcolabile (proviene mappando un'altra funzione non calcolabile sui suoi stessi punti!), ma questo non è banale e bisogna dimostrarlo.

Purtroppo per voi, vi si chiede di usare la "diagonalizzazione" (esplicitamente), mentre in questo caso ciò che volevo fare io sarebbe una specie di "riduzione"... quindi pur di non buttare via l'idea da me suggerita, vi conviene esplicitare la scrittura g(⌊x/2⌋) nei rispettivi casi in cui avevate suddiviso la definizione di g a lezione.



La tua proposta di soluzione del secondo esercizio:
------ cut here -------
\fs{3}f(x) = \{\begin{matrix}\phi_{x/3} (x)+1&&&\text{se }x\;\phi_{x/3} (x)\downarrow&\wedge\;&x = 3k&\text{con } k > 1 \in N\\ 0&&&\text{se }x\;\phi_{x/3} (x)\uparrow\\ \uparrow&&&\text{altrimenti}\end{matrix}
------ cut here -------
è ben impostata, ma ha alcuni problemi:
  • prendendo, come codice di ϕ, il valore x/3, a partire da x=3k con k>1, significa partire da x=6, per continuare poi nell'insieme {6, 9, 12, 15, ...}, dunque non scendi mai sotto 6, dunque x/3 non scende mai sotto 6/3=2; a te è richiesto che, nella argomentazione, tu dimostri che qualsiasi valore (fosse anche 0 e 1!, entrambi minori di 2!) ti ritrovi come codice di programma (che per ipotesi assurda esiste e calcola la funzione considerata/creata), tu giunga ad un assurdo: è evidente che, con tale formulazione, da 0 e 1 non ci passi mai: e se, per caso, la funzione cercata avesse proprio 0 o 1 come codici? In questo caso hai due scelte: la prima è di rivedere la definizione di f; la seconda è di costruire una ulteriore argomentazione riguardo al fatto che, per esempio, se il codice fosse 0 o 1, sicuramente ne troveresti un altro programma con codice maggiore o uguale a 2 che calcola la stessa funzione, dunque dovresti rinforzare la condizione sul codice di programma che calcola la funzione considerata/creata (e che esiste in virtù dell'ipotesi assurda) dicendo qualcosa come:
    Quote
    “sia e codice di programma che calcola f; senza perdita di generalità, consideriamo un tale e ≥ 2”

  • non è ben chiaro se il secondo punto abbia, come criterio di definizione per casi, il fatto che x sia multiplo di 3 maggiore di 3: per come è scritto, non è una condizione obbligata, dunque si incappa nell'errore di far assumere 0 anche ai valori non-multipli di 3 e ai valori multipli di 3 non maggiori di 3 (quindi a 0 -in qualche modo- e 3), cosa che è errata: in quei punti, infatti, la f deve assumere il valore indefinito ↑
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 #5 on: 28-02-2014, 22:52:38 »

Beh, grazie per la pazienza con la quale hai approfondito il problema. Effettivamente ora è tutto un po' più chiaro. Si tratta, effettivamente, di imbeccare la strada giusta, poi la formalizzazione della funzione viene da sè.

Grazie ancora.
Logged
Pages: [1]   Go Up
Print
Jump to: