I get the proof of going from an enumerator to a Turing Machine (keep running en
ID: 649081 • Letter: I
Question
I get the proof of going from an enumerator to a Turing Machine (keep running enumerator and see if it matches input) but I don't see how the other way works.
According to my notes and the book (Intro to the Theory of Computation - Sipser), to get Turing enumerator from a Turing machine, we basically write all combinations of the alphabet. You then run the TM on this input, if it accepts print it out, replace with new string repeat ad infinitum.
The problem I am having is surely this requires the language to be decidable. Otherwise it might get stuck on the third word in some infinite loop doomed never to accept or reject and certainly never print out the whole language.
What am I missing?
Explanation / Answer
What's missing is the way you run the Turing Machine M on strings to get the Enumerator. Rather than generate each string, run M, and then output this string if the M accepts
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.