A (normal) enumerator is a version of a Turing machine M that has an extra outpu
ID: 3799564 • Letter: A
Question
A (normal) enumerator is a version of a Turing machine M that has an extra output tape (or a printer attached, as the textbook formulates it). Both tapes are completely blank as the machine starts. M writes a sequence of strings onto the output tape with a separation symbol (e.g., a comma) between them. This sequence is finite or infinite. Repetitions of strings are allowed. The generated language is the set of all the listed strings. A lexicographic enumerator is an enumerator that writes its list in shortlex order (ordered by length first, and ordered lexicographically for each fixed length).Explanation / Answer
If A is decidable by some TM M, the enumerator operates by generating the strings
in lexicographic order, testing each in turn for membership in A using M, and printing the
string if it is in A.
1
If A is enumerable by some enumerator E in lexicographic order, we consider two cases. If
A is finite, it is decidable because all finite languages are decidable (just hardwire each of
the strings into the TM). If A is infinite, a TM M that decides A operates as follows. On
receiving input w, M runs E to enumerate all strings in A in lexicographic order until some
string lexicographically after w appears. This must occur eventually because A is infinite. If
w has appeared in the enumeration already, then accept; else reject.
Note: It is necessary to consider the case where A is finite separately because the enumerator
may loop without producing additional output when it is enumerating a finite language. As
a result, we end up showing that the language is decidable without using the enumerator for
the language to construct a decider. This is a subtle, but essential point.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.