Recursively Enumerable

 
Picture of Γιάννης Παπαϊωάννου
Re: Recursively Enumerable
by Γιάννης Παπαϊωάννου - Wednesday, 19 November 2014, 11:37 PM
 

Βασικά ο Παπαδημητρίου θεωρεί ότι μια γλώσσα είναι αποδεκτή από μια ΤΜ μόνο αν τερματίζει με "yes" (αν το string ανήκει στην γλώσσα) ή μπαίνει σε loop διαφορετικά. Μάλιστα στην σελίδα 62 που λες, γράφει "a machine may halt with a "no", which is incompatible with our definition of acceptance". Παρόμοιο ορισμό δίνει και στο βιβλίο που έχει γράψει με τον Lewis. 

Πάντως και ο ορισμός που έχει η wikipedia συμφωνεί με τον Sipser:

"A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that will halt and accept when presented with any string in the language as input but may either halt and reject or loop forever when presented with a string not in the language. Contrast this to recursive languages, which require that the Turing machine halts in all cases."