# Enumeration of a class of languages

Can you enumerate a class of languages in such a way that the description of every language/ machine enumerated encodes where it was in the enumeration?

Ex:if you are given the description of the bth machine/language enumerated you could quickly check, by some tag or marker in the description of the bth machine / language, that it was indeed the bth machine/language in the enumeration by an enumerator E.

Can you modify any enumerator for a class of languages so that it does this? Or can such an enumerator E be rigged up to do this for any enumerable class of languages?

To give context, my goal is for a verifier to accept, as one part of its input, the machine/language enumerated, and be able to see, quickly, what position that machine/language was in the enumeration by the enumerator E.

Thank you!

• i dont really understand the question. Did you mean to ask if there is a way for a machine to enumerate on a language, and for another machine to verify that it does actually enumerate on it? May 29 '20 at 20:44
• @nirshahar Is there a type of enumerator for every enumerable language that a verifier can quickly verify, when given a word and a number b, that that word is the bth word enumerated. May 29 '20 at 21:37
• Okay. i think i understood now May 29 '20 at 21:55
• When you enumerate, does it have to be in lexicographic order (like the usual enumerator of $\Sigma^*$) ? May 29 '20 at 21:58
• yes--what im asking is that for any enumerable language does there exist an enumerator such that it is quick to verify the spot of any word in the enumeration. Ex: given a word and a number b the verifier would be able to quickly say--yes this word is the bth word enumerated by E. May 29 '20 at 22:17

Given any enumeration $$E$$ of the language, here is a way to describe a language: "the 5th language in the enumeration".
If you use that as the description, then yes, your condition is trivially true. Given the description of a language ("the 5th language in $$E$$"), you can quickly find its position in $$E$$ (5).