Pages: [1] 2 3   Go Down
Print
Author Topic: lista esercizi  (Read 7967 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« 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!!!!! Smiley ... 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  testate
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.449


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


WWW
« Reply #1 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 pc...
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
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #2 on: 17-05-2013, 22:26:21 »


Divertitevi pc...
ahahahahhah... sicuramente!!!!! grazie mille Wink
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.449


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


WWW
« Reply #3 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 .

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

Posts: 185



« Reply #4 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? 
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?
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.449


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


WWW
« Reply #5 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?  
Sì. Mi aspettavo questa osservazione, a dire il vero: è stata inserita provocatoriamente .

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 .

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 ?
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
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #6 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  ?
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.
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.449


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


WWW
« Reply #7 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à.

Che è calcolabile (bisogna fare la tiritera del discorso della calcolabilità)
TIRITERA??? Ma che stiamo raccontando, filastrocche testate pray cry?

  ok
« Last Edit: 20-05-2013, 23:41:46 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
Giuseppe Scollo
Moderator
Forumista Esperto
*****
Offline Offline

Posts: 1.389


« Reply #8 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?
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.449


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


WWW
« Reply #9 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 ).

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.
« Last Edit: 20-05-2013, 23:44:29 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
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #10 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! 

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
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.449


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


WWW
« Reply #11 on: 21-05-2013, 00:08:14 »

corregetemi se sbaglio! 
[...]
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.
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
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #12 on: 21-05-2013, 00:11:07 »

ok ora tutto chiaro!!!! posso dormire in pace per oggi!  ....  grazie ancora!
Logged
Mari_C
Apprendista Forumista
**
Offline Offline

Posts: 240


"SmiiiiLe"


« Reply #13 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 ? 
Logged
Mari_C
Apprendista Forumista
**
Offline Offline

Posts: 240


"SmiiiiLe"


« Reply #14 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.
 
Logged
Pages: [1] 2 3   Go Up
Print
Jump to: