Question

. Show that a language is decidable if and only if some enumerator prints the strings in the language in lexicographical order.

Answer 1

If A is decidable by some TMM, 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.

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 TMM 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