Show that a language L isTuring-decidable if and only if there is a Turing machine M that enumerates L and such that the strings in L are output by M in length-increasing fashion. (Hint: The if direction is trivial when L is finite (justify) so focus on the case when L has infinitely many strings.)

_____________________________________________________________________________________________________________________________________

Referring to this excerpt from the textbook might help:

ENUMERATORS As we mentioned earlier, some people use the term recursively enumerable language for Turing-recognizable language. That term originates from a type of Turing machine variant called an enumerator. Loosely defined, an enumerator is a Turing machine with an attached printer. The Turing machine can use that printer as an output device to print strings. Every time the Turing machine wants to add a string to the list, it sends the string to the printer. Exercise 3.4 asks you to give a formal definition of an enumerator. The following figure depicts a schematic of this model.

An enumerator E starts with a blank input on its work tape. If the enumerator doesnt halt, it may print an infinite list of strings. The language enumerated by E is the collection of all the strings that it eventually prints out. Moreover, E may generate the strings of the language in any order, possibly with repetitions. Now we are ready to develop the connection between enumerators and Turingrecognizable languages.