# 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).

• to give you some context, i need to be able to apply the 5th machine / language to a word as well as quickly verify that it is indeed the 5th machine/ language. So, it needs to come out of the enumerator in a form i can use (immediately apply to a word) but also, needs to be self-evident from its description what its position in the enumeration is. May 30 '20 at 14:02
• the code for the verifier is: input: (w,Cb), a word and a description of a machine Cb, check if Cb is the bth machine enumerated by E, run Cb(w). If Cb is the bth language enumerated by E and Cb(w) = 1--> Cb is a proof for w in L. I need the step 'check if Cb is the bth machine enumerated by E' to run quickly. So, i need an enumerator E that tacks on that information of where Cb was in the enumeration to Cb's description so that it is easy to see what place it was in the enumeration-- i need to choose such an enumerator for an enumerable class of languages C. May 30 '20 at 14:07
• basically, I'm asking is there a way to enumerate the machines for an enumerable class of languages in such a way that we add something to their descriptions, a tag or marker, that says: "this is the bth language in the enumeration"." May 30 '20 at 14:12
• But so that they are also still useable--i need to be able to use the machines / languages. So, a combination of a normal enumeration of machines and what you said in your answer. Looking for an enumerator that can accomplish this for any enumerable class of languages. May 30 '20 at 15:39
• @DeeDee, sorry, that's too much text for me to read through right now. If you need 8 comments to explain what your question was trying to ask, then I don't think your question was clear enough. I encourage you to spend some time figuring out how to concisely and clearly state the problem you are trying to solve, then edit your question to reflect that.
– D.W.
May 30 '20 at 20:25