Δύο απορίες:

1) Όταν μια γλώσσα είναι recursively enumerable, η μηχανή πρέπει πάντα να κολλάει όταν παίρνει ως είσοδο λέξη που δεν ανήκει στη γλώσσα; Ρωτάω γιατί στο αντίστοιχο μάθημα που είχα παρακολουθήσει στο προπτυχιακό του μαθηματικού, (ουσιαστικά πηγαίναμε με βάση το βιβλίο του Sipser) λέγαμε ότι υπάρχουν τρία ενδεχόμενα: yes, no, loop (δηλαδή για λέξη που δεν ανήκει στη γλώσσα μπορεί να πει όχι ή να κολλήσει).

2) Άσχετα με το προηγούμενο ερώτημα, στη σελίδα 62 στο βιβλίο του Παπαδημητρίου λέει: "If for a Machine M there is a string x such that M(x) is neither "yes" nor "loop", then, by convention, L(M)=empty." Δηλαδή αν υπάρχει έστω και μία λέξη για την οποία η ΜΤ πάει στην κατάσταση "no" ή "halt" τότε λέμε ότι η γλώσσα της είναι η κενή; Και αν αυτό ισχύει, υποθέτω ότι οι "deciders" (που λένε πάντα "yes","no") αποτελούν εξαίρεση;