[Palano] Ric. Numerabili <= ricorsivo
Clicca QUI per vedere il messaggio nel forum |
| johnnyd |
Ragazzi non riesco a capire la dimostrazione
D ricorsivamente numerabile quindi non è ricorsivo
Mi perdo nel punto in cui inizia a mettere in mezzo il programma "e" su AssurdoA
help me... :) |
| number15 |
| Hai già provato con gli appunti della Lara (vado a memoria, spero di non aver sbagliato nome :D) |
| Joliet Jake |
mah io ho guardato le dispense... praticamente è così:
per dimostrare che esiste un linguaggio r.n. ma non ricorsivo prendi il formalismo dell'interprete, e il teorema che dice che A={x|Fu (x$x) termina--> A è ricorsivamente num. ma non ric.
devi dimostrare entrambe le cose
prima parte.
prendi un processo che fa i seguenti passi:
1.calcola x$x
2.calcola Fu(x$x)
3.return 1
Se Fu(x$x) è calcolabile, termina e ritorna uno, se no no.
Quindi è R.N.
parte due
supponiamo per assurdo che A sia ricorsivo
ora crea un processo "e" che fa i seguenti passi:
1. calcola Fu(x$x)
2. ritorna 1-Fu(x$x) se x appartiene ad A , oppure 0 se non appartiene ad A
Allora se usiamo il processo e nella formula abbiamo
Fu(e$e)
SE x APPARTIENE AD A
il processo ritorna 1-Fu(e$e)
però il processo è Fu(e$e), e quindi dovrebbe essere
Fu(e$e) = 1-Fu(e$e)
SE x NON APPARTIENE AD A
il processo ritorna 0
dovrebbe quindi essere Fu(e$e) = 0
ma nella definizione di A si dice che A è composto da tutte le x tali per cui termina, e quindi se e non appartiene ad A come fa a terminare?
Spero sia questa la dimostrazione ;)
dimmi se non hai capito. |
| n3o |
| ahahah, mi viene la pelle d'oca... auguroni a tutti (soprattutto a me che ho l'orale il 3 e sono messo malissimo!!!) |
| Kira82 |
| Scusa una cosa n3o ma l'orale con la Palano non è il 4? |
| number15 |
| Non facciam scherzi... io so che è il 9. |
| n3o |
Io ho seguito il corso e l'ultima lezione c'erano, sia per l'appello di Giugno, sia per quello di Luglio, delle possibili date da scegliere.
In ogni caso credo tu possa mandargli una mail per chiedergli a che data presentarti (e dove), meglio ancora se ti presenti il giovedì a ricevimento... |
| Kira82 |
| Ah no perchè io sono andata a seguire gli orali del 18 e prendeva le iscrizioni per fare l'orale il 4/07 per quello.. |
|
|
|
