.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- [Palano] Ric. Numerabili <= ricorsivo (http://www.dsy.it/forum/showthread.php?threadid=31313)

[Palano] Ric. Numerabili <= ricorsivo

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...

__________________
My Blog - My Photo Album

Hai già provato con gli appunti della Lara (vado a memoria, spero di non aver sbagliato nome )

__________________
Portale segnalazioni marchi-negozi di abbigliamento
http://www.ovojo.com

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

ahahah, mi viene la pelle d'oca... auguroni a tutti (soprattutto a me che ho l'orale il 3 e sono messo malissimo!!!)

__________________
The answer is blowing in the wind...

Scusa una cosa n3o ma l'orale con la Palano non è il 4?

Non facciam scherzi... io so che è il 9.

__________________
Portale segnalazioni marchi-negozi di abbigliamento
http://www.ovojo.com

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...

__________________
The answer is blowing in the wind...

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..