Fall 2005, moed A, closed question 3, of Benny Chor (the exam and solution can be found here: http://www.cs.tau.ac.il/~jonatha6/Computational%20Models%20-%20fall%202008.html - bulletin of 2/2/09):
L has an "organized" enumerator if there exists an enumerator g: N->L, such that
forall n. |g(n)|<=|lex(n)|
where lex(n) is string no. n in the lexi. order.
The question is about the relations between decideable languages and languges that have an "organized" enumerator:
I understand that every language in R has an organized enumerator, as this is a private case of the sorted enumerator we saw in the recitation.
The answers state that if a language has a "sorted" enumerator, than it's in R, but I'm not sure about that.
We don't know how much we should wait to see a string of length 1, for example. As the "sorted" enumerator is not neccesarily one-to-one, it is possible that a string in the language is denied, and appears only very late.
Thanks a lot.