Domanda su Teorema di Rice!
Domani dovrei fare lo scritto di Informatica Teorica e quindi vorrei togliermi gli ultimi quesiti...
Qualcuno di voi che studia informatica, sa qualche applicazione pratica del Teorame di Rice...
Teorema: "Ogni proprietà di RE non banale è indecidibile!"
Sulla dimostrazione del teorema ci sono! ma il problema è....
che applicazione pratica può avere??? (dovrà averla per forza)
su wiki eng non hai trovato nessuna dritta?
Dritte non consistenti...
Per quel che ho potuto capire fino ad ora è che è indecidibile ogni problema sulle Turing Machine che riguarda le proprietà dei linguaggi accettati!
Tipo: Il linguaggio accettato da una TM M ha una particolare proprietà? è indecidibile...
un altro esempio potrebbe essere... "Esiste un programma virus free?" questo è indecidibile in quanto può essere rincondotto ad un problema su linguaggi e quindi considerare il problema "Esiste un linguaggio con la proprietà di essere virus free?" quindi è indecidibile..
Sono decidibili invece le proprietà che riguardano la TM stessa.!.
Spero solamente di aver capito il nocciolo della questione... o magari mi sono complicato solo di più la vita... mah!
Ora però devo fare un pò di chiarezza ...
LinkBack URL
About LinkBacks
Rispondi citando