 |
Joliet Jake |
.illuminato.
Registered: Oct 2006
Posts: 249 (0.04 al dì)
Location: Milano
Corso: Informatica triennale
Anno: 3
Time Online: 1 Day, 4:31:25 [...]
Status: Offline
Edit | Report | IP: Logged |
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.
__________________
In Blues We Trust
|
johnnyd
)
