Very important line-
REC has lexicographic enumeration procedure but RE do not have lexicographic enumeration procedure (Of course, RE has enumeration procedure, that is why it is called Recursively enumerable language but it need not to be lexicographic )
(Throughout this answer, whenever I write RE it means "RE but Not REC")
Why so ?
-for REC we have Halting Turing machine.
Enumeration procedure for REC-
I can give each string in HTM and wait for some time, either HTM will accept it or reject it. If accept it then print string and move on to next string, if reject then move to next string without printing.
Of course i can give strings in lexicographic order and this procedure will enumerate in the same order in which i give input.
![](https://gateoverflow.in/?qa=blob&qa_blobid=7351357350489521595)
Here$ \tilde{M}$ generates all strings in lexicographic order (or in whatever order we want) and M also outputs in same order.
Can we use same procedure for RE ? (again RE means "RE but not REC")
NO!, this procedure won't work for RE, Why?
That enumeration procedure looks like this-
Repeat: $ \tilde{M}$ generates a string w
M checks if w∈L
Yes: Print w
No: Ignore
This procedure won't work for RE.
Problem: If w∉L M may loop forever
Now, The question is, How to enumerate RE ?, Which is best procedure for enumerating RE ?
-We all know that there is a procedure to enumerate RE, but we never bother about how this procedure looks like :D
I have one idea, not sure if this works or not, Let's see-
-I give all strings to TM simultaneously, and as soon as one string is accepted by TM, It will print.
Say, 1st string is taking 500 steps and 2nd string is taking 5 steps then after 5 steps it will print 2nd string, and after 500 steps it will print 1st string.
Seems like it will work and will enumerate strings of RE language, but How can i give all strings simultaneously?
-If i modify the procedure mentioned above then it will pretend like all strings are given simultaneously.
$\tilde{M}$ generates first string $w_1$
M executes first step on $w_1$
$\tilde{M}$ generates second string $w_2$
M executes first step on $w_2$
Second step on $w_1$
$\tilde{M}$ generates third string $w_3$
M executes first step on $w_3$
M executes second step on $w_2$
Third step on $w_1$
And So on....
If for string machine halts in a final state then it prints on the output.
This procedure enumerates in random order.
Say, 1st string is taking 1000 steps of TM and 5th takes only 2 steps. Then it prints 5th string first.
Now if i ask you "A language L can be enumerated by length if and only if it is recursive.", Then You must agree that this statement is also true.
Be it any order, if u can enumerate in that order then that language can not be RE.