0
$\begingroup$

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!

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – nir shahar
    May 29 '20 at 20:44
  • $\begingroup$ @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. $\endgroup$
    – DeeDee
    May 29 '20 at 21:37
  • $\begingroup$ Okay. i think i understood now $\endgroup$
    – nir shahar
    May 29 '20 at 21:55
  • $\begingroup$ When you enumerate, does it have to be in lexicographic order (like the usual enumerator of $\Sigma^*$) ? $\endgroup$
    – nir shahar
    May 29 '20 at 21:58
  • $\begingroup$ 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. $\endgroup$
    – DeeDee
    May 29 '20 at 22:17
0
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – DeeDee
    May 30 '20 at 14:02
  • $\begingroup$ 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. $\endgroup$
    – DeeDee
    May 30 '20 at 14:07
  • $\begingroup$ 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"." $\endgroup$
    – DeeDee
    May 30 '20 at 14:12
  • $\begingroup$ 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. $\endgroup$
    – DeeDee
    May 30 '20 at 15:39
  • 2
    $\begingroup$ @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. $\endgroup$
    – D.W.
    May 30 '20 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.