To *enumerate* a set is to place the elements of the set in a one-to-one
correspondence with the natural numbers.

The set of all strings over an alphabet is denumerable (think of a string as a number in an ||-ary number system). The strings in a language form a subset of the set of all strings over . But can we enumerate the strings in a language?

If a language is recursive, then there exists a Turing machine for it that is guaranteed to halt. We can generate the strings of * in a shortest-first order (to guarantee that every finite string will be generated), test the string with the Turing machine, and if the Turing machine accepts the string, assign that string the next available natural number.

We can also enumerate the recursively enumerable languages. We have a Turing machine that will halt and accept any string that belongs to the language; the trick is to avoid getting hung up on strings that cause the Turing machine to go into an infinite loop. We do this by "time sharing." Here's how:

W := ; N := 0; for i := 1 to_{0}do { add the next string in * to set W; initialize a Turing machine for this new string; for each string in set W do { let the Turing machine for it make one move; if the Turing machine halts { accept or reject the string as appropriate; if the string is accepted { N := N + 1; let this be string N of the language; } remove the string from set W; } } }

Copyright © 1996 by David Matuszek

Last modified Apr 1, 1996