Forum Informatica Unict

LAUREA MAGISTRALE => Teoria della Computabilità, 9 CFU => Topic started by: nairi on 17-05-2013, 13:57:05



Title: lista esercizi
Post by: nairi on 17-05-2013, 13:57:05
Ciao raga! Sono i cerca di esercizi "nuovi" per esercitarmi in vista dell'appello che spero supereremo tutti!!!!! :) ... qualcuno di voi può postare es relativi alla parte di computabilità? magari degli anni precedenti... io dal 2009 in poi non ho nulla!!!! ma nessuno ha fatto esami?!?!?!? ... questa materia è un mistero  :-)|


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 17-05-2013, 21:57:27
Te ne creo qualcuno nuovo di zecca ora sul momento:

  • Dimostrare che esiste una funzione unaria totale e non calcolabile \fs{3}f tale che \fs{3}\text{Ran}(f)=\{{y: y\text{ e' pari}}\}.

  • Dimostrare che esiste una funzione unaria totale e non calcolabile \fs{3}g_1 tale che \fs{3}g_1(2x)=2x,\;\forall x\in\mathbb{N}.

  • Dimostrare che esiste una funzione unaria totale e non calcolabile \fs{3}g_2 tale che \fs{3}g_2(3x)=3x,\;\forall x\in\mathbb{N}.

  • Generalizzando:
    Fissato \fs{3}k\in\mathbb{N}, dimostrare che esiste una funzione unaria totale e non calcolabile \fs{3}g tale che \fs{3}g(kx)=kx,\;\forall x\in\mathbb{N}.

  • Dimostrare che esiste una funzione calcolabile totale e unaria \fs{3}k(x) tale che
    \fs{3}W_{k(x)}=\{{p_i\;|\;i\in\mathbb{N}^+}\} ed \fs{3}E_{k(x)}=\{{p_1,\;p_1+p_2,\;p_1+p_2+p_3,\;...,\;p_1+p_2+...+p_{x+1}}\}

  • Dimostrare che esiste una funzione calcolabile totale e unaria \fs{3}k(x) tale che
    \fs{3}W_{k(x)}=\{{x, x^2, x^3, ...}\} ed \fs{3}E_{k(x)}=\{{p_i\;|\;i\in\mathbb{N}^+}\}

Ricordo che \fs{3}p_i è l'\fs{3}i-esimo numero primo.

Divertitevi :[Emoticon] PC Asd:...


Title: Re:lista esercizi
Post by: nairi on 17-05-2013, 22:26:21

Divertitevi :[Emoticon] PC Asd:...
ahahahahhah... sicuramente!!!!! grazie mille ;)


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 18-05-2013, 11:00:52
Aggiungo alcuni esercizi molto semplici riguardo il teorema di parametrizzazione:

Dimostrare che esiste una funzione calcolabile totale e unaria \fs{3}k(x) tale che:

  • \fs{3}W_{k(x)}=\{{2,\;4,\;6,\;8,\;10,\;\cdots}\} e \fs{3}E_{k(x)}=\{{x,\;x^3,\;x^5,\;x^7,\;x^9,\;\cdots}\}

  • \fs{3}W_{k(x)}=\{{2,\;4,\;8,\;16,\;32,\;\cdots}\} e \fs{3}E_{k(x)}=\{{1,\;11,\;21,\;31,\;41,\;\cdots}\}

  • \fs{3}W_{k(x)}=\{{1,\;2,\;\cdots,\;x^2}\} e \fs{3}E_{k(x)}=\{{1,\;2,\;\cdots,\;x}\}

  • \fs{3}W_{k(x)}=\{{150,\;250,\;350,\;450,\;550,\;\cdots}\} e \fs{3}E_{k(x)}=\{{23,\;65,\;896}\}

Magari cominciate da questi per poi proseguire con quelli del messaggio precedente .smile.

Ora alcuni esercizi di ragionamento:
  • Si consideri una funzione \fs{3}f dai naturali ai naturali, monotonicamente non-crescente. È possibile che esista una tale funzione e che sia non-calcolabile? Se sì, esibirne un esempio e dimostrarne la non-calcolabilità; se no, dimostrare perché.

  • Si consideri una funzione \fs{3}f dai naturali ai naturali, monotonicamente non-decrescente. È possibile che esista una tale funzione e che sia non-cacolabile? Se sì, esibirne un esempio e dimostrarne la non-calcolabilità; se no, dimostrare perché.

  • Si dimostri l'esistenza di due funzioni totali, unarie e non-calcolabili \fs{3}f_1,\;f_2 dai naturali ai naturali, tali che la funzione composta \fs{3}g(x)=\text{rm}\({f_1(x),\;f_2(x)}\) (cioè il resto della divisione \fs{3}\frac{f_2(x)}{f_1(x)} sia calcolabile.


Title: Re:lista esercizi
Post by: nairi on 20-05-2013, 19:06:22
Ciao!!! abbiamo provato a fare la seconda lista di esercizi ma non abbiamo capito il 4, non siamo riusciti a trovare una corrispondenza fra dominio e codominio... qualche suggerimento?  .whistling
Invece volevamo chiederti un parere per il 3 (sempre della stessa serie di es):
Abbiamo definito la funzione per casi con predicati decidibili e mutuamente esclusivi:

            y           se y<x
f(x,y)=  y2          se y=x
            \uparrow          se y>x

così definita possiamo dire che è calcolabile per i motivi sopraelencati?


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 20-05-2013, 21:55:15
Ciao!!! abbiamo provato a fare la seconda lista di esercizi ma non abbiamo capito il 4, non siamo riusciti a trovare una corrispondenza fra dominio e codominio... qualche suggerimento?  .whistling
Sì. Mi aspettavo questa osservazione, a dire il vero: è stata inserita provocatoriamente .coolio.

Considerate che il dominio è esprimibile con ricorrenza, e il codominio no... almeno apparentemente (Lagrange insegna che per un certo numero finito \fs{3}n di punti, è sempre possibile costruire un polinomio di grado \fs{3}n-1 che li attraversa tutti).
In ogni caso, non è richiesto che vi ricordiate un così complicato teorema costruttivo, vi basta costruire la funzione per casi :boh. In un caso restituite il primo (23), in un altro il secondo (65) e in un terzo (896), e in tutti gli altri casi restituite uno qualsiasi di quei tre (o di nuovo tutti e tre ciclando, è indifferente...).

Invece volevamo chiederti un parere per il 3 (sempre della stessa serie di es):
Abbiamo definito la funzione per casi con predicati decidibili e mutuamente esclusivi:

            y           se y<x
f(x,y)=  y2          se y=x
            \uparrow          se y>x

così definita possiamo dire che è calcolabile per i motivi sopraelencati?
Certo. La funzione è perfettamente calcolabile. Ma applicandovi il teorema di parametrizzazione S-m-n (forma semplice) non riuscite a dimostrare l'esistenza della funzione richiesta .nono.

Fra i tanti errori, ve ne indico uno: la vostra funzione \fs{3}f va in loop quando \fs{3}y>x; equivalentemente, una volta applicato il teorema di parametrizzazione S-m-n (forma semplice) vi accorgerete che la vostra funzione \fs{3}k(x) sarà tale che \fs{3}W_{k(x)}=\{{1,\;2,\;\cdots,\;x}\}
che non va bene!

Potreste mostrarmi le soluzioni agli altri così vediamo se avete fatti errori simili o se sono giuste .penso?


Title: Re:lista esercizi
Post by: nairi on 20-05-2013, 22:54:24
Quote
Potreste mostrarmi le soluzioni agli altri così vediamo se avete fatti errori simili o se sono giuste  .penso ?
grazie per le correzioni... ecco gli altri :-OK
1)soluzione:

              x(y-1)             se "y è pari" \wedge y>0
 f(x,y)=  \uparrow                    altrimenti

scrivo f(x,y)=\muz(y=2z \wedge>0)*1*x(y-1)

che è calcolabile(bisogna fare la tiritera del discorso della calcolabilità)
e poi uso il t smn.


2)soluzione:
         
            (x-1)*10+1           se "y è una potenza di 2" \wedge y>0
f(x,y)= \uparrow                           altrimenti

Scrivo f(x,y)=[\muz(y=2z \wedge y>0)-1]*10+1

Che è calcolabile (bisogna fare la tiritera del discorso della calcolabilità)
e poi uso il t smn.


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 20-05-2013, 23:16:19
1)soluzione:

              x(y-1)             se "y è pari" ∧ y>0
 f(x,y)=       ↑               altrimenti
Corretto.

scrivo f(x,y)=μz(y=2z ∧ y>0)*1*x(y-1)

che è calcolabile(bisogna fare la tiritera del discorso della calcolabilità)
e poi uso il t smn.
C'è un errore di sintassi nella formula: quell'1 sottolineato immagino sia la funzione costante che vale sempre 1. In tal caso, va usata a sinistra del suo argomento, che suppongo sia tutto il minimo che invece è a sinistra (e tale argomento va inserito tra parentesi); con tale correzione, sarebbe corretto.

2)soluzione:
        
            (x-1)*10+1           se "y è una potenza di 2" ∧ y>0
f(x,y)=          ↑                   altrimenti
Stavolta c'è un errore, nella prima espressione (quella sopra) di definizione di f. Considera che quel (x-1) che moltiplichi per 10, nella espressione che hai scritta sotto per estesa (e che è corretta al 95% :pray) è invece "il numero che, usato come esponente di una potenza a base 2, ci dà y", cioè "l'esponente da dare a 2 per ottenere y", cioè ancora matematicamente parlando "il logaritmo di y in base 2", che non dipende assolutamente da x (men che meno nella forma di x-1).

Scrivo f(x,y)=[μz(y=2z ∧ y>0)-1]*10+1
EDIT: Come dicevo poche righe sopra, corretto.
Mi ha fatto riflettere l'osservazione del prof. Scollo fatta sotto, e in effetti va corretta la sola parte:
"y>0" in "z>0". Infatti, a essere maggiore di zero (cioè da 1 in poi) è l'esponente da dare a 2 per avere y, di modo che, poi, una volta trovato (se esistente), va ridotto di una unità (cosa fatta correttamente con il "-1" prima della parentesi quadra chiusa) e poi moltiplicato per 10 e incrementato di 1 unità. .arrossisco

Che è calcolabile (bisogna fare la tiritera del discorso della calcolabilità)
TIRITERA??? Ma che stiamo raccontando, filastrocche :-)| :pray :"-(?

 .wink :-OK


Title: Re:lista esercizi
Post by: Giuseppe Scollo on 20-05-2013, 23:30:16
Per cominciare: mille grazie per questo aiuto prezioso, generoso e disinteressato! Ho due osservazioni (la prima molto marginale) sull'ultima risposta:
C'è un errore di sintassi nella formula: quell'1 sottolineato immagino sia la funzione costante che vale sempre 1.
Infatti. Forse è utile precisare che si tratta della funzione unaria costante  che vale sempre 1.
Scrivo f(x,y)=[μz(y=2z ∧ y>0)-1]*10+1
Come dicevo poche righe sopra, corretto.
Hmm, non capisco la condizione y>0, non è superflua? O esiste una potenza intera di 2 che vale 0?


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 20-05-2013, 23:36:35
Infatti. Forse è utile precisare che si tratta della funzione unaria costante  che vale sempre 1.
Avremmo fugato ogni dubbio qualora se ne fosse scritta la versione corretta (deducendo la arietà dal numero di argomenti fornitole .arrossisco).

Scrivo f(x,y)=[μz(y=2z ∧ y>0)-1]*10+1
Come dicevo poche righe sopra, corretto.
Hmm, non capisco la condizione y>0, non è superflua? O esiste una potenza intera di 2 che vale 0?
Grazie per l'osservazione. In effetti mi era sfuggito quell'y>0, che va corretto nel molto simile (almeno a una vista superficiale) z>0!!!


Uhu!? Mi sono venuti in mente altri due esercizi di ragionamento, piuttosto interessanti.

  • Sia \fs{3}f una funzione da interi a interi e unaria e totale, e sia \fs{3}\text{Dom}(f)\subset\text{Ran}(f) con \fs{3}\text{Ran}(f) infinito.

    Esiste una tale funzione (matematicamente parlando)?
    • Se sì: ne esiste una calcolabile?
      • Se sì, esibirla e dimostrarle la calcolabilità.
      • Se no, dimostrarlo
    • Se no: dimostrare perché.

  • Sia \fs{3}f una funzione da interi a interi e unaria e totale, e sia \fs{3}\text{Dom}(f)\subset\text{Ran}(f) con \fs{3}\text{Ran}(f) finito.

    Esiste una tale funzione (matematicamente parlando)?
    • Se sì: ne esiste una calcolabile?
      • Se sì, esibirla e dimostrarle la calcolabilità.
      • Se no, dimostrarlo
    • Se no: dimostrare perché.

EDIT: ho rimosso l'attributo di totalità, perché è un refuso di quando ho inventato gli esercizi e stavo provando a esprimerli sul forum.


Title: Re:lista esercizi
Post by: nairi on 21-05-2013, 00:01:02
grazie a tutti per le correzioni!!!
Per il primo esercizio quella y che manca è solo un errore di trascrizione xD ....
Quote
C'è un errore di sintassi nella formula: quell'1 sottolineato immagino sia la funzione costante che vale sempre 1. In tal caso, va usata a sinistra del suo argomento, che suppongo sia tutto il minimo che invece è a sinistra (e tale argomento va inserito tra parentesi); con tale correzione, sarebbe corretto.

 :-OK ora ho capito come vanno messi in ordine!

per il secondo esercizio c'è stata molta confusione... l'idea in testa era quella ma poi mi sono imbrogliata fra le variabili e metti e togli alla fine ho messo la x... ma ho capito subito quello che intendevi, la riscrivo tutta così da poter fare ulteriore chiarezza... corregetemi se sbaglio!  .smile

2)soluzione:
         
            (y-1)*10+1           se "y è una potenza di 2" \wedge y>0
f(x,y)= \uparrow                           altrimenti

Scrivo f(x,y)=[\muz(y=2z \wedge z>0)-1]*10+1


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-05-2013, 00:08:14
corregetemi se sbaglio!  .smile
[...]
2)soluzione:
         
            (y-1)*10+1           se "y è una potenza di 2" ∧ y>0
f(x,y)=       ↑                     altrimenti

Scrivo f(x,y)=[μz(y=2z ∧ z>0)-1]*10+1
Nuovamente, hai scritto male la forma definita per casi, ma correttamente quella che mostra f come espressione calcolabile.
Mi sono accorto solo ora che l'errore y>0 probabilmente proviene da questa mal-definizione che ho evidenziato in rosso ora. Siccome ho fatto in modo che il dominio siano le potenze di 2, a partire da due, sarebbe l'esponente che produce tale potenza a dover essere maggiore di 0, cioè la potenza intera (y) dovrebbe essere maggiore di 2^0=1, cioè puoi scrivere equivalentemente (y>1) oppure (y>=2) al posto della espressione evidenziata in rosso.

Invece di (y-1) devi scrivere \fs{3}\log_2(y)-1.


Title: Re:lista esercizi
Post by: nairi on 21-05-2013, 00:11:07
ok ora tutto chiaro!!!! posso dormire in pace per oggi!  .ciaociao ....  grazie ancora!


Title: Re:lista esercizi
Post by: Mari_C on 21-05-2013, 15:44:45
Ecco altri dubbi relativi agli esercizi di ragionamento da te proposti nella seconda lista
Quote
B. Si consideri una funzione f dai naturali ai naturali, monotonicamente non-decrescente. È possibile che esista una tale funzione e che sia non-cacolabile? Se sì, esibirne un esempio e dimostrarne la non-calcolabilità; se no, dimostrare perché.

Abbiamo definito
                 \phi x(x)+1 se  \phi x(x) \downarrow
f(x) =
                 1  se  \phi x(x) \uparrow
f è non calcolabile in quanto perveniamo ad un assurdo in entrambi i casi.

La f cosi definita soddisfa le condizioni da te proposte?

Quote
C.Si dimostri l'esistenza di due funzioni totali, unarie e non-calcolabili f1 ed f2 dai naturali ai naturali, tali che la funzione composta g(x)=rm(f1(x),f2(x)) cioè il resto della divisione f2(x)/f1(x) sia calcolabile.

Qui abbiamo definito f1(x) , al solito, come \phi x(x)+1 se  \phix(x) \downarrow e 1 se non termina .
Dato per assodato che f1(x) ,così definita ,sia non calcolabile possiamo prendere come f2(x) il doppio di f1(x) cioè:
f2(x)=2 f1(x) e quindi dire che anche f2(x) è non calcolabile?
Per la funzione composta g(x)=  	\frac{f2(x)}{f1(x)}    e sostituendo la f2(x) otteniamo
 \frac{ 2f1(x)}{f1(x)}    =  2  funzione costante quindi calcolabile.

In quante lingue abbiamo bestemmiato ?  .arrossisco


Title: Re:lista esercizi
Post by: Mari_C on 21-05-2013, 16:11:37
Per quelli sulla non calcolabilità come:
Quote
1. Dimostrare che esiste una funzione unaria totale e non calcolabile f tale che Ran(f)= { y: y è pari}


                    2   \phi   y/2 (y) se \phi y (y)\downarrow and y è pari
f(y)=
                    0 altrimenti

è non calcolabile.
Supponendo per assurdo che lo sia allora esiste e tale che \phi e =f . Considerando il punto y=2e perveniamo ad un assurdo sia nel caso in cui \phi e (2e) termina e 2e è pari che non termina.
 .penso


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-05-2013, 19:29:54
Ecco altri dubbi relativi agli esercizi di ragionamento da te proposti nella seconda lista
Quote
B. Si consideri una funzione f dai naturali ai naturali, monotonicamente non-decrescente. È possibile che esista una tale funzione e che sia non-cacolabile? Se sì, esibirne un esempio e dimostrarne la non-calcolabilità; se no, dimostrare perché.

Abbiamo definito
                 \phi x(x)+1 se  \phi x(x) \downarrow
f(x) =
                 1  se  \phi x(x) \uparrow
f è non calcolabile in quanto perveniamo ad un assurdo in entrambi i casi.

La f cosi definita soddisfa le condizioni da te proposte?
Eh, questo devi dirmelo tu.
Sicuramente è non calcolabile, ma è monotonicamente non-decrescente?
Io posso dimostrare che sta funzione certamente non lo è.
Infatti, sia \fs{3}a=\min\{{x\;:\;\phi_x=\underline{1}}\} e sia \fs{3}b=\min\{{x\;:\;\phi_x=\underline{0}\;\wedge\;x>a}\}
Siccome per ogni funzione calcolabile (in questo caso per \fs{3}\underline{0}) esistono infiniti codici di programma che la calcolano, un tale \fs{3}b esiste.
Ora succede che:
\fs{3}\phi_a(a)\downarrow 1\;\Longrightarrow\;f(a)=\phi_a(a)+1=1+1=2\\\phi_b(b)\downarrow 0\;\Longrightarrow\;f(b)=\phi_b(b)+1=0+1=1\\\\f(a)=2>1=f(b)\;\Longrightarrow\;f(a)>f(b)

Quindi abbiamo trovato due punti \fs{3}a, b tali che:
\fs{3}a<b\;\wedge\;f(a)>f(b)\;\Longrightarrow\;fnon è non-decrescente (infatti è proprio DEcrescente).

Tu, invece, dovresti esibirne una che lo è, e dimostrare che per essa vale la proprietà di monotonica non-decrescenza.

Quote
C.Si dimostri l'esistenza di due funzioni totali, unarie e non-calcolabili f1 ed f2 dai naturali ai naturali, tali che la funzione composta g(x)=rm(f1(x),f2(x)) cioè il resto della divisione f2(x)/f1(x) sia calcolabile.

Qui abbiamo definito f1(x) , al solito, come \phi x(x)+1 se  \phix(x) \downarrow e 1 se non termina .
Dato per assodato che f1(x) ,così definita ,sia non calcolabile possiamo prendere come f2(x) il doppio di f1(x) cioè:
f2(x)=2 f1(x) e quindi dire che anche f2(x) è non calcolabile?
Sì, potete, ma dovete dimostrarlo. Si può dimostrare per assurdo, facendo vedere che, se fosse calcolabile, allora per composizione, anche la funzione \fs{3}k(x)=\text{qt}\{{2, f_2(x)}\}=\frac{f_2(x)}{2}=\frac{2f_1(x)}{2}=\frac{\not{2}f_1(x)}{\not{2}}=f_1(x) sarebbe calcolabile. Assurdo perché \fs{3}f_1 è non-calcolabile.

Per la funzione composta g(x)=  	\frac{f2(x)}{f1(x)}    e sostituendo la f2(x) otteniamo
 \frac{ 2f1(x)}{f1(x)}    =  2  funzione costante quindi calcolabile.
Avete sbagliato a considerare la funzione \fs{3}g(x).

Avevo detto che a essere calcolabile doveva essere la funzione \fs{3}g(x)=\text{rm}\({f_2(x), f_1(x)}\), cioè il RESTO della divisione intera \fs{3}\frac{f_2(x)}{f_1(x)}.
Ma del tutto incidentalmente :boh, anche se avete considerato la \fs{3}g sbagliata, visto che la divisione fa sempre due, significa che il resto fa sempre 0, e una funzione che assume sempre il valore 0 è \fs{3}\underline{0}\in C_1, a colpo di fortuna .smile!

Per quelli sulla non calcolabilità come:
Quote
1. Dimostrare che esiste una funzione unaria totale e non calcolabile f tale che Ran(f)= { y: y è pari}


                    2   \phi   y/2 (y) se \phi y (y)\downarrow and y è pari
f(y)=
                    0 altrimenti

è non calcolabile.
Supponendo per assurdo che lo sia allora esiste e tale che \phi e =f . Considerando il punto y=2e perveniamo ad un assurdo sia nel caso in cui \phi e (2e) termina e 2e è pari che non termina.
 .penso
Forse nella condizione volevate scrivere "se \fs{3}\phi_{\frac{y}{2}}(y)\downarrow\;\wedge\;y \text{ pari}

Ma anche in quel caso (e in questo attuale), non avete dimostrato che tutti i numeri pari sono stati assunti dalla vostra funzione \fs{3}f. .nono

Suggerimento: siccome il codominio che vi ho imposto è infinito, non vi basta "traslare" di qualche posizione (un numero finito) la diagonale, ma dovete piegarla!
In particolare, potete fare in modo che nei punti pari la funzione assuma lo stesso valore del punto, e nei dispari ci infilate i valori diversi da tutte le funzioni calcolabili (in modo che si passi da tutte le funzioni calcolabili, e non sia uguale a nessuna di esse, in almeno un punto).


Title: Re:lista esercizi
Post by: nairi on 25-05-2013, 11:23:59
 
Quote
Suggerimento: siccome il codominio che vi ho imposto è infinito, non vi basta "traslare" di qualche posizione (un numero finito) la diagonale, ma dovete piegarla!
In particolare, potete fare in modo che nei punti pari la funzione assuma lo stesso valore del punto, e nei dispari ci infilate i valori diversi da tutte le funzioni calcolabili (in modo che si passi da tutte le funzioni calcolabili, e non sia uguale a nessuna di esse, in almeno un punto).

così com'è?

           y                  se y pari
f(y)=  \phi(y-1)/2+1     y dispari \wedge  \phi(y-1)/2\downarrow
          0                   se y dispari \wedge \phi(y-1)/2\uparrow


ormai la disperazione fa parte di me  :-)|


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 25-05-2013, 11:53:02
Quote
Suggerimento: siccome il codominio che vi ho imposto è infinito, non vi basta "traslare" di qualche posizione (un numero finito) la diagonale, ma dovete piegarla!
In particolare, potete fare in modo che nei punti pari la funzione assuma lo stesso valore del punto, e nei dispari ci infilate i valori diversi da tutte le funzioni calcolabili (in modo che si passi da tutte le funzioni calcolabili, e non sia uguale a nessuna di esse, in almeno un punto).

così com'è?

           y                  se y pari
f(y)=  \phi(y-1)/2+1     y dispari \wedge  \phi(y-1)/2\downarrow
          0                   se y dispari \wedge \phi(y-1)/2\uparrow


ormai la disperazione fa parte di me  :-)|
Perfetto!!!
Hai dimenticato solo di specificare l'argomento delle funzioni \fs{5}\phi_{\frac{y-1}{2}}, che può essere qualsiasi stavolta (y stesso andrà benissimo!) .smile! Congratulescions!

Poi devi solo fare la solita "tiritera" della non calcolabilità dimostrandola tramite assurdi  :-OK!


Title: Re:lista esercizi
Post by: nairi on 25-05-2013, 12:03:49
Quote
"tiritera"
  .smile
si lo so... ora che so che l'impostazione è giusta è un gioco da ragazzi continuare ;) .....


Title: Re:lista esercizi
Post by: nairi on 26-05-2013, 10:25:01
Buona domenica (non per me  .bah ) !!!
Sto riprendendo gli es della seconda lista (quelli del t s-m-n) che avevamo sbagliato e lasciato perdere perchè non riuscivamo più a ragionarci...  ora sto riflettendo di nuovo sul 3 e in base alle osservazioni fatte :
Quote
Fra i tanti errori, ve ne indico uno: la vostra funzione  va in loop quando ; equivalentemente, una volta applicato il teorema di parametrizzazione S-m-n (forma semplice) vi accorgerete che la vostra funzione  sarà tale che
che non va bene!
ho abbozzato una soluzione ma in un caso non so ancora cosa far restituire per riportare i valori ottenuti all'immagine  .poverinoi , ecco la mia soluzione incompleta:

           y     se y\leqx
f(x,y)= ?   se x<y\leqx2
          \uparrow      se y>x2

Nel secondo caso cosa posso mettere ammesso che sia giusta l'impostazione dei casi?


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 26-05-2013, 12:39:23
Ci sei quasi, ma... facciamo un passo indietro, un secondino.
Dimentica, per adesso, che ho imposto che debba valere la seconda parte,
\fs{3}E_{k(x)}=\{{1,\;2,\;\cdots,\;x}\}.

Sai dimostrare l'esistenza di una funzione totale, unaria e calcolabile \fs{3}k(x), tale che:
\fs{3}W_{k(x)}=\{{1,\;2,\;\cdots,\;x^2}\}?
Senza ulteriori condizioni imposte, solo questa.

Cioè per tutti i numeri da 1 a x2 compresi deve terminare (negli altri loopare).


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 26-05-2013, 13:15:45
Aggiungo che nel caso speciale \fs{3}x=0, gli insiemi \fs{3}\{{1,\;2,\;\cdots,\;x}\} e \fs{3}\{{1,\;2,\;\cdots,\;x^2}\} sono entrambi vuoti .sisi.


Title: Re:lista esercizi
Post by: nairi on 26-05-2013, 14:33:31
Quote
Sai dimostrare l'esistenza di una funzione totale, unaria e calcolabile , tale che:
?
Senza ulteriori condizioni imposte, solo questa.

Cioè per tutti i numeri da 1 a x2 compresi deve terminare (negli altri loopare).

il problema è lo zero? quindi quando è finita, la condizione è 0<y\leqx^2 mentre negli altri casi è indefinita?


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 26-05-2013, 15:00:18
Esatto il problema è lo zero (una delle tante difficoltà che ho volutamente aggiunto xD).
Puoi considerare di usare, come condizione di definizione, \fs{3}1\leq y\leq x^2.

Ma poi, ti chiedo, una volta che hai tutti i numeri dell'intervallo di interi \fs{3}\[{1,\;x^2}\], riesci a trovare un modo molto sbrigativo seppure elegante, di associare tale intervallo all'intervallo \fs{3}\[{1,\;x}\] .smile (riciclando il valore \fs{3}y intendo)?


Title: Re:lista esercizi
Post by: nairi on 26-05-2013, 16:01:38
Quote
Ma poi, ti chiedo, una volta che hai tutti i numeri dell'intervallo di interi , riesci a trovare un modo molto sbrigativo seppure elegante, di associare tale intervallo all'intervallo   (riciclando il valore  intendo)?
usando il modulo?:
(y mod x)+1

così va bene?


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 26-05-2013, 16:21:16
Perfetto! :-OK

Io avevo pensato, invece, a \fs{3}\lfloor\sqrt{y}\rfloor, che si dimostra essere calcolabile .smile.

Ad ogni modo, o nel mio o nel tuo, sai riscrivere ora correttamente la funzione \fs{3}f(x,\;y)?


Title: Re:lista esercizi
Post by: nairi on 26-05-2013, 16:26:27
Quote
Ad ogni modo, o nel mio o nel tuo, sai riscrivere ora correttamente la funzione ?
si si  :[Emoticon] Asd:  brevemente restituisce la mia sol o la tua nella condizione y compresa fra 1 e x2 mentre è indefinita altrimenti..... grazie ;)


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 26-05-2013, 16:41:54
Perfetto.

Siccome abbiamo una funzione definita per casi, ove i casi sono mutualmente esclusivi e discriminati da predicati decidibili, e poiché, per ogni caso, il valore da far assumere alla funzione è calcolabile, allora la funzione è certamente calcolabile .smile.

Questo, se ricordi la discussione con il professore a cui ero presente pure io, è sufficiente per dimostrare la calcolabilità.

Però si possono avere più punti all'esame, se si è in grado di esibire una espressione funzionale (piuttosto di quella, appena enunciata, che si basa su teoremi costruttivi) e che mostri come è possibile calcolare f.

Con la mia variante, una valida soluzione è:
\fs{3}f(x,\;y)=\mu_z\({z^2=y\;\wedge\;1\leq y\;\wedge\;y\leq x^2}\)

Con la tua variante, una valida soluzione è:
\fs{3}f(x,\;y)=\{\[{{\underline{0}\({\mu_z\({1\leq y\;\wedge\;y\leq x^2}\)}\)+y}\]\;\text{mod}\;x}\}+1


Title: Re:lista esercizi
Post by: nairi on 26-05-2013, 17:02:58
 .rido grazie mille!!!!!!


Title: Re:lista esercizi
Post by: nairi on 20-06-2013, 11:01:33
Quote
Dimostrare che esiste una funzione unaria totale e non calcolabile g1 tale che g1(2x)=2x,\forall x \inN.

Dimostrare che esiste una funzione unaria totale e non calcolabileg2 tale che g2(3x)=3x,\forall x \inN.

Generalizzando:
Fissato k\inN, dimostrare che esiste una funzione unaria totale e non calcolabile g tale che g(kx)=kx, \forall x\in N

A distanza di tempo mi sono accorta che pur avendo affrontato questa serie di esercizi non sono arrivata ad una soluzione "postabile"  :[Emoticon] PC Asd: ...
Mi riferisco all'autore della lista: Per favore mi puoi spiegare su cosa devo concentrarmi? queste funzioni hanno lo stesso input e output... non capisco!   .huh


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 20-06-2013, 11:17:36
No, non hanno lo stesso output per gli stessi input in generale, ma lo hanno solo su determinati valori.

g1 ristretta ai numeri pari, assume gli stessi valori passatile in input
g2 ristretta ai multipli di 3, assume gli stessi valori passatile in input
...
gn ristretta ai mutipli di (n+1), assume gli stessi valori passatile in input

Ciò vuol dire che su tutti gli altri valori non multipli del (pedice+1), che sono infiniti (altrimenti sarebbe impossibile ottenere la incalcolabilità, nota bene!), hai libertà di scegliere quello che vuoi.


Title: Re:lista esercizi
Post by: nairi on 21-06-2013, 11:13:28
Quote
Ciò vuol dire che su tutti gli altri valori non multipli del (pedice+1), che sono infiniti (altrimenti sarebbe impossibile ottenere la incalcolabilità, nota bene!), hai libertà di scegliere quello che vuoi.

mi dici se questo ragionamento va bene? ho usato g2:

                  y   se "y è un multiplo di 3"
g2(y)=       3   se \phiy+1(y)\downarrow \wedge ymod3 \neq 0
                  3   se \phiy+1(y)\uparrow

In caso di correttezza, mi sorge un dubbio: non dovrei garantire per ogni caso la g2(y) sia diversa da \phi  in almeno un punto?


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-06-2013, 13:06:07
E se dovessimo essere nel caso in cui "y è un multiplo di 3" e contemporaneamente \fs{3}\phi_{y+1}(y)\uparrow?

Devi imparare a gestire meglio i casi, attualmente non sono mutualmente esclusivi .nono.

Sebbene la strategia sia sempre la stessa, e cioè scegliere, per ogni indice x (y nel tuo caso) di quelli che usiamo per dimostrare solo la parte di incalcolabilità, un altro indice k(x) tale che k sia biunivoca tra il suo dominio (dominio matematico stavolta, non riguardo alle teoria delle funzioni calcolabili) e tutto \fs{3}\mathbb{N}, questa volta la funzione k non è così banale:

In particolare, visto che i valori multipli di 3 (o di n in generale, dalla forma generale degli esercizi di questo tipo) sono esattamente \{{3,\;6,\;9,\;12,\;15,\;\cdots}\} e questi non li possiamo usare per dimostrare l'incalcolabilità (giacché dobbiamo imporre per questi un valore calcolabile, in particolare in quei punti bisogna che f assuma gli stessi valori dell'argomento :boh), allora per dimostrare l'incalcolabilità possiamo sfruttare un sottoinsieme infinito dell'insieme dei numeri rimanenti dalla sottrazione insiemistica \fs{3}\mathbb{N}\setminus\{{3,\;6,\;9,\;12,\;15,\;\cdots}\}=\mathbb{N}\setminus\{{x\;:\;x\;\equiv\;0\;\({\text{mod} 3}\)}\}=\{{0,\;1,\;2,\;4,\;5,\;7,\;8,\;10,\;11,\;13,\;14,\;\cdots}\}.

È importante notare che non è necessario che si passi da tutti questi indici x per costruire k(x) suriettiva su \fs{3}\mathbb{N}, ma è sufficiente che si passi da un suo sottoinsieme infinito (dev'essere infinito per forza, se vogliamo che sia suriettiva su tutto \fs{3}\mathbb{N}.

Scegliamo, per esempio, di passare dal sottoinsieme degli indici che sono i numeri precedenti dei multipli di 3, ovvero gli elementi dell'insieme:
 \fs{3}\{{2,\;5,\;8,\;11,\;14,\;...}\}\subseteq\{{0,\;1,\;2,\;4,\;5,\;7,\;8,\;10,\;11,\;13,\;14,\;\cdots}\}=\mathbb{N}\setminus\{{x\;:\;x\;\equiv\;0\;\({\text{mod} 3}\)}\}

Riesci a trovare una funzione biunivoca tra \fs{3}k tra gli insiemi \fs{3}\{{2,\;5,\;8,\;11,\;14,\;...}\}\;{k\over\longleftrightarrow}\;\mathbb{N}?


Title: Re:lista esercizi
Post by: Mari_C on 21-06-2013, 14:35:30
Quote
Riesci a trovare una funzione biunivoca tra k tra gli insiemi {2, 5, 8, 11, 14, ...} ed ℕ?

Potresti essere più chiaro ,please? Non capisco questo linguaggio formale  :boh  .smile


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-06-2013, 15:13:31
Quote
Riesci a trovare una funzione biunivoca tra k tra gli insiemi {2, 5, 8, 11, 14, ...} ed ℕ?

Potresti essere più chiaro ,please? Non capisco questo linguaggio formale  :boh  .smile
Scusa, c'era un "tra" di troppo: l'ho sbarrato modificando il messaggio:

Quello che voglio chiederti è: sai descrivere una funzione k che associ tutti gli interi precedenti ai multipli di tre, a tutti gli interi in generale, in modo che sia biunivoca (cioè ne esista l'inversa che associa ad ogni naturale uno ed un solo precedente di multiplo di 3)?


Title: Re:lista esercizi
Post by: nairi on 21-06-2013, 15:56:22
mi dispiace ma non riesco a seguirti  :-)| ....
la mia soluzione era tutta sbagliata? L'ho modificata così:

                  y   se "y è un multiplo di 3"
g2(y)=       3   se \phiy+1(y)\downarrow \wedge ymod3 \neq 0
                  3   se \phiy+1(y)\uparrow \wedge ymod3 \neq 0

Adesso è mutuamente esclusiva? io considero che se y è un multiplo di 3 debba terminare


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-06-2013, 16:26:07
Si, ok. Tutte le funzioni non calcolabili che dovete proporre devono necessariamente essere totali, quindi dirmi che se è un multiplo di 3 debba terminare è ovvio (deve terminare anche in tutti gli altri casi, cioè sempre).

Correggendo il tuo esercizio, nell'ultimo messaggio stavolta bensì i casi sono mutualmente esclusivi ma, almeno per il caso in cui ϕy+1 termina, devi ulteriormente esplicitare due casi: quello in cui termina con 3 (in cui farai assumere a g2 un valore diverso da 3) e quello in cui termina in un valore diverso da 3 (nel qual caso hai tutto il diritto di far assumere 3 a g2).

In ogni caso, sfruttare l'indice y+1 come codice di funzione calcolabile non ti basta, perché in questo modo, la funzione si comporta secondo la seguente regolarità:

in 0 (non multiplo di 3) si controlla cosa fa ϕ1
in 1 (non multiplo di 3) si controlla cosa fa ϕ2
in 2 (non multiplo di 3) si controlla cosa fa ϕ3
in 3 (multiplo di 3) si restituisce 3
in 4 (non multiplo di 3) si controlla cosa fa ϕ5
in 5 (non multiplo di 3) si controlla cosa fa ϕ6
in 6 (multiplo di 3) si restituisce 3
in 7 (non multiplo di 3) si controlla cosa fa ϕ8
in 8 (non multiplo di 3) si controlla cosa fa ϕ9
in 9 (multiplo di 3) si restituisce 3
in 10 (non multiplo di 3) si controlla cosa fa ϕ11
...

stai notando che non controlliamo mai cosa avviene alle funzioni ϕ0, ϕ4, ϕ7, ϕ10, ecc... (cioè tutte le funzioni calcolabili con codici i successivi dei multipli di tre, e inoltre la funzione con codice 0)?

Tu devi passare da tutte queste funzioni, in un modo o nell'altro! .huh


Title: Re:lista esercizi
Post by: Mari_C on 21-06-2013, 17:06:56


                  y   se "y è un multiplo di 3"
g2(y)=       3   se \phiy(y)\downarrow\wedge ymod3 \neq 0 \wedge b \neq 3
                  6   se \phiy(y)\downarrow\wedge ymod3 \neq 0 \wedge b=3
                  3   se \phiy(y)\uparrow \wedge ymod3 \neq 0

così? grazie alla tua osservazione ho capito che per passare da tutti gli indici non bisogna piegarla la diagonale!
Dico bene?



Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 21-06-2013, 17:38:11
così? grazie alla tua osservazione ho capito che per passare da tutti gli indici non bisogna piegarla la diagonale!
Dico bene?
Così sistemi il problema della copertura di tutti i casi (mutualmente esclusivi) possibili, ma ancora non hai manipolato la diagonale.
Perchè, bensì, quando ci vengono imposte condizioni dall'alto su cosa debba restituire la nostra funzione non calcolabile in certi punti, allora abbiamo bisogno di piegare/traslare/estendere/ruotare(?, no ruotare no  :nono, scherzavo) la diagonale .sisi.

Come prima, osserva dalla seguente regolarità cosa andiamo a controllare e cosa no:

in 0 (non multiplo di 3) si controlla cosa fa ϕ0
in 1 (non multiplo di 3) si controlla cosa fa ϕ1
in 2 (non multiplo di 3) si controlla cosa fa ϕ2
in 3 (multiplo di 3) si restituisce 3
in 4 (non multiplo di 3) si controlla cosa fa ϕ4
in 5 (non multiplo di 3) si controlla cosa fa ϕ5
in 6 (multiplo di 3) si restituisce 3
in 7 (non multiplo di 3) si controlla cosa fa ϕ7
in 8 (non multiplo di 3) si controlla cosa fa ϕ8
in 9 (multiplo di 3) si restituisce 3
in 10 (non multiplo di 3) si controlla cosa fa ϕ10
...

stavolta non controlliamo mai cosa avviene alle funzioni ϕ3, ϕ6, ϕ7, ϕ9, ecc... (cioè tutte le funzioni calcolabili con codici multipli di tre)!

Tu devi passare da tutte queste funzioni, in un modo o nell'altro! .huh
Anche da quelle da cui non stai passando ora.

[...]

Mi sto rendendo conto che un esercizio di questo tipo è troppo complicato anche per me. Stavo per scrivere una soluzione ma mi sono bloccato in un punto oscuro...

Fai finta che questi esercizi non te li abbia mai dati...
In effetti, nemmeno il prof. Cantone aveva mai osato tanto ai tempi in cui la insegnava lui .penso...

Ho voluto volare con le mie ali di cera fino al Sole, e mi si sono sciolte :-)L!
(no vabbè, è che dovrei studiarci molto di più, molto più di quanto richiesto e possibile nel tempo di un'esame .arrossisco)


Title: Re:lista esercizi
Post by: nairi on 21-06-2013, 19:51:27
 :[Emoticon] Rosik Asd: tu mi fai impazzire!!!!!!!!!!!!!!!!!!!!!

da un lato sono contenta però... almeno so che se il mio cervello si rifiuta proprio di collaborare vuol dire che la difficoltà è superiore di quella prevista per l'esame! (almeno spero) ... incrocio le dita e posto altre soluzioni... rimai ormai un ultimo week-end nella migliore delle ipotesi!!!!!


Title: Re:lista esercizi
Post by: Giuseppe Scollo on 22-06-2013, 11:36:05
in 0 (non multiplo di 3) si controlla cosa fa ϕ0
Hmm, qui ci vuole un'aggiustatina: 0 è un multiplo di 3 (il multiplo nullo). Temo che occorrano correzioni analoghe in post precedenti, per esempio 0 ≡ 0 (mod 3).


Title: Re:lista esercizi
Post by: Giuseppe Scollo on 15-07-2013, 14:41:04
Quote
Suggerimento: siccome il codominio che vi ho imposto è infinito, non vi basta "traslare" di qualche posizione (un numero finito) la diagonale, ma dovete piegarla!
In particolare, potete fare in modo che nei punti pari la funzione assuma lo stesso valore del punto, e nei dispari ci infilate i valori diversi da tutte le funzioni calcolabili (in modo che si passi da tutte le funzioni calcolabili, e non sia uguale a nessuna di esse, in almeno un punto).

così com'è?

           y                  se y pari
f(y)=  \phi(y-1)/2+1     y dispari \wedge  \phi(y-1)/2\downarrow
          0                   se y dispari \wedge \phi(y-1)/2\uparrow


ormai la disperazione fa parte di me  :-)|
Perfetto!!!
Hai dimenticato solo di specificare l'argomento delle funzioni \fs{5}\phi_{\frac{y-1}{2}}, che può essere qualsiasi stavolta (y stesso andrà benissimo!) .smile! Congratulescions!
Non so perché (o forse lo so ma non posso dirlo), mi è tornato in mente questo esercizio, ho riletto questa interessante discussione, e ho scovato la necessità di una piccola correzione. Poiché si impone che l'immagine della funzione sia l'insieme dei numeri pari, occorre non solo che i pari ci siano tutti (e fin qui la soluzione proposta va bene: il "piegamento" della diagonale ne è una rotazione, in termini geometrici), ma anche che la funzione assuma soltanto valori pari, e qui non va bene limitarsi a garantire (ai fini della non calcolabilità) che sui dispari la funzione assuma "valori diversi da tutte le funzioni calcolabili": diversi, certamente, purché comunque pari. Tenendo conto di questo, direi che la correzione della soluzione proposta porta alla seguente:

           y                                                       se y pari
f(y) \phi(y-1)/2(y)+(2 - (\phi(y-1)/2(y) mod 2))    se y dispari \wedge  \phi(y-1)/2(y)\downarrow
           0                                                       se y dispari \wedge \phi(y-1)/2(y)\uparrow
Quote
Poi devi solo fare la solita "tiritera" della non calcolabilità dimostrandola tramite assurdi
A proposito, non è davvero necessaria quella "tiritera": a beneficio del risparmio di tempo, carta e inchiostro, basta dire che la funzione specificata è diversa da ogni funzione calcolabile, pertanto non è calcolabile.



Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 17-07-2013, 09:47:25
[...] lo so ma non posso dirlo [...]
|-O

Grazie per la correzione. In effetti avevo dimenticato di controllare il fatto che i valori assunti dovessero essere pari.
Nella sua soluzione, ha accorpato in un'unica espressione calcolabile ciò che si deve restituire nel caso in cui
\fs{6}y\text{ dispari }\wedge\phi_{\frac{y-1}{2}}\({y}\)\downarrow
mentre normalmente, anche per una più lineare dimostrazione della incalcolabilità, noi studenti degli altri anni siamo stati abituati a separare nettamente i casi in cui \fs{6}\phi_{\frac{y-1}{2}}\({y}\) è pari o dispari .smile.

Ma sottraendo il valore assunto dalla funzione caratteristica del predicato "è dispari" calcolato sull'argomento \fs{6}\phi_{\frac{y-1}{2}}\({y}\), al valore di \fs{6}\phi_{\frac{y-1}{2}}\({y}\) stesso (e sommando 2 per renderlo certamente diverso da esso stesso), si ottiene un valore pari .smile.


Title: Re:lista esercizi
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 13-09-2013, 23:38:05
Avanti, ve ne risolvo uno per tutti:

Fissato \fs{3}k\in\mathbb{N}^{+}, dimostrare che esiste una funzione unaria, totale e non calcolabile \fs{4}g tale che \fs{4}g\({kx}\)=kx,\;\forall x\in\mathbb{N}

Si consideri la seguente \fs{4}g


\fs{6}g(x)=\{\begin{matrix}x&&\text{se }k|x\\\phi_{\lfloor{\frac{x}{k}}\rfloor}\({x}\)+1&&\text{se }k\not{|}x\;\wedge\;\phi_{\lfloor{\frac{x}{k}}\rfloor}\({x}\)\downarrow\\0&&\text{se }k\not{|}x\;\wedge\;\phi_{\lfloor{\frac{x}{k}}\rfloor}\({x}\)\uparrow\end{matrix}

Prima di tutto, verifichiamo che una tale funzione rispetti la condizione data.
Ebbene, se \fs{4}k|x (cioè se l'argomento passato è del tipo \fs{4}x=ky,\;y\in\mathbb{N}), allora la funzione assumerà proprio il valore \fs{4}x=ky, come volevasi.

Adesso, invece, asserisco che \fs{4}g è non calcolabile.

Per assurdo, sia \fs{4}g calcolabile. Allora \fs{4}\exists e\in\mathbb{N} tale che \fs{4}\phi_e=g.

Vediamo cosa accade, allora, nel punto \fs{4}x=ke+1.
Per prima cosa, notiamo che \fs{4}x=ke+1\equiv 1\({\text{mod} k}\)\Longrightarrow k\not{|}x e, inoltre, che \fs{4}\lfloor{\frac{x}{k}}\rfloor=\lfloor{\frac{ke+1}{k}}\rfloor=e.

Allora, visto che \fs{4}k\not{|}x, ci sono solo due casi possibili:
  • \fs{4}\phi_e\({ke+1}\)\downarrow. Allora \fs{4}\phi_e\({ke+1}\)=g\({ke+1}\)=\phi_e\({ke+1}\)+1\Longrightarrow 0=1 Assurdo

  • \fs{4}\phi_e\({ke+1}\)\uparrow. Allora \fs{4}\phi_e\({ke+1}\)=g\({ke+1}\)=0\Longrightarrow\phi_e\({ke+1}\)\downarrow Assurdo

In tutti i casi possibili, otteniamo un assurdo. L'assurdo nasce dall'aver supposto che \fs{4}g fosse calcolabile, quindi \fs{4}g è non calcolabile.