Turing Machines, Cranking Out the Language

Cranking Out the Language

A tm can produce, rather than accept, a language, by writing the words of that language to a predefined output area, which could be a separate track on the tm's read/write tape. The tm generates all possible words on one track, performs calculations on another track, and writes the words of the language to the output track.

A recursive language can be generated in lexicographical order. Crank out the words in order and test each one. Since each word is accepted or rejected in finite time, the tm steps through all possible words in order, and the language is generated in order.

An re language can also be generated in its entirity, but the words may come in any order. You need to test all words in parallel. This can be done by a diagonal algorithm. Let the recognizing tm run on each of the first j words, for j steps, as j runs from 1 to infinity. If the ith word is accepted in j steps, this will be detected at either the ith or the jth iteration, for the larger of i and j, and it is printed out at this point. Of course this word is detected again, and again, but it is only printed out once - when the number of steps needed to accept the word equals its index in the order of all words, or the index of the current iteration.

Conversely, a set of words that can be generated by a tm forms an re language. Given a candidate word, run the generating tm and watch for a match.

If the words can be produced in lexicographical order, the language is recursive. A finite language is automatically recursive. If the language is infinite, a generated word will eventually exceed the candidate word. If you haven't found a match by then, halt in a failure state.

In summary, re languages can be generated, and recursive languages can be generated in order.