If a language is recursive, then there exists an easily constructed enumeration
procedure. Suppose that M is a Turing machine that determines membership in a
recursive language L. We first construct another Turing machine, say , that
generates all strings in Σ + in proper order, let us say w 1 , w 2 ,…. As these strings
are generated, they become the input to M, which is modified so that it writes
strings on its tape only if they are in L.
That there is also an enumeration procedure for every recursively
enumerable language is not as easy to see. We cannot use the previous argument
as it stands, because if some w j is not in L, the machine M, when started with w j
on its tape, may never halt and therefore never get to the strings in L that follow
w j in the enumeration. To make sure that this does not happen, the computation
is performed in a different way. We first get to generate w 1 and let M execute
one move on it. Then we let generate w 2 and let M execute one move on w 2 ,
followed by the second move on w After this, we generate w 3 and do one step
on w 3 , the second step on w 2 , the third step on w 1 and so on. The order of
performance is depicted in Figure 11.1. From this, it is clear that M will never
get into an infinite loop. Since any w ∈ L is generated by and accepted by M
in a finite number of steps, every string in L is eventually produced by M.
It is easy to see that every language for which an enumeration procedure
exists is recursively enumerable. We simply compare the given input string
against successive strings generated by the enumeration procedure. If w ∈ L, we
will eventually get a match, and the process can be terminated.
Definitions 11.1 and 11.2 give us very little insight into the nature of either
recursive or recursively enumerable languages. These definitions attach names to
language families associated with Turing machines, but shed no light on the
nature of representative languages in these families. Nor do they tell us much
about the relationships between these languages or their connection to the
language families we have encountered before. We are therefore immediately
faced with questions such as “Are there languages that are recursively
enumerable but not recursive?” and “Are there languages, describable somehow,
that are not recursively enumerable?” While we will be able to supply some
answers, we will not be able to produce very explicit examples to illustrate these
questions, especially the second one.
Figure 11.1
procedure. Suppose that M is a Turing machine that determines membership in a
recursive language L. We first construct another Turing machine, say , that
generates all strings in Σ + in proper order, let us say w 1 , w 2 ,…. As these strings
are generated, they become the input to M, which is modified so that it writes
strings on its tape only if they are in L.
That there is also an enumeration procedure for every recursively
enumerable language is not as easy to see. We cannot use the previous argument
as it stands, because if some w j is not in L, the machine M, when started with w j
on its tape, may never halt and therefore never get to the strings in L that follow
w j in the enumeration. To make sure that this does not happen, the computation
is performed in a different way. We first get to generate w 1 and let M execute
one move on it. Then we let generate w 2 and let M execute one move on w 2 ,
followed by the second move on w After this, we generate w 3 and do one step
on w 3 , the second step on w 2 , the third step on w 1 and so on. The order of
performance is depicted in Figure 11.1. From this, it is clear that M will never
get into an infinite loop. Since any w ∈ L is generated by and accepted by M
in a finite number of steps, every string in L is eventually produced by M.
It is easy to see that every language for which an enumeration procedure
exists is recursively enumerable. We simply compare the given input string
against successive strings generated by the enumeration procedure. If w ∈ L, we
will eventually get a match, and the process can be terminated.
Definitions 11.1 and 11.2 give us very little insight into the nature of either
recursive or recursively enumerable languages. These definitions attach names to
language families associated with Turing machines, but shed no light on the
nature of representative languages in these families. Nor do they tell us much
about the relationships between these languages or their connection to the
language families we have encountered before. We are therefore immediately
faced with questions such as “Are there languages that are recursively
enumerable but not recursive?” and “Are there languages, describable somehow,
that are not recursively enumerable?” While we will be able to supply some
answers, we will not be able to produce very explicit examples to illustrate these
questions, especially the second one.
Figure 11.1