1
$\begingroup$

Pt 1. Given as input the tuple: (word (from an r.e. language we fix), natural number)--does there exist a verifier, that runs faster than simply enumerating that language, that can accept if the word is in the position of the natural number in an enumeration by an enumerator, and reject if it is not (choosing any enumerator you want for the set that makes this possible)?

I suspect the answer is no. In that case...

Pt 2. Is there a way to get around this by adding a "tagging" function to an enumerator for the language, so that a verifier can be given something like (word#tag, natural number) so that it almost immediately knows, from the tag, if the word is in the position of the natural number in that enumeration? AND IT CAN'T BE FOOLED! Of course you can stick a natural number onto a word, but how can you do this so the verifier can BE SURE you aren't lying...?

clarification from the comments on the question:

The question is basically: can you manufacture an enumerator for any enumerable language so that it includes extra data that the verifier can use to quickly determine what position it was in the enumeration, ie: can such an enumerator be constructed for any enumerable language?

Any ideas? :)

$\endgroup$
9
  • $\begingroup$ This problem seems to me to be highly dependent on the fixed enumerator itself. For example, if its enumeration scheme was based on some cryptographically secure hash function (using an unknown secret key), I'm not sure how you would avoid doing the enumeration. $\endgroup$
    – mhum
    Jun 3 '20 at 19:53
  • $\begingroup$ @mhum Ya, for sure. I'm wondering if for an enumerable language, pick any enumerate language, you can modify the enumerator in such a way so that you can do this. Basically the inverse of the obfuscation you are talking about. $\endgroup$
    – user121977
    Jun 3 '20 at 19:56
  • $\begingroup$ @mhum if the enumeration scheme was based on a secure hash function a modification could be gluing the key onto the word. Key = tag. this is the kind of thing I'm talking about. Once you fix a language, and some enumerator for it, can you change the enumerator so that it glues extra data to the words (or describes them differently in some way) so their positions in this new enumeration are revealed. $\endgroup$
    – user121977
    Jun 3 '20 at 20:06
  • $\begingroup$ So, I'm not sure this question is answerable in this level of generality, without more details or parameters around the enumerator. In an even worse case, the enumerator could be attached to a true random number generator and it could pick a new, completely random order for every new set of words it is asked to enumerate. $\endgroup$
    – mhum
    Jun 3 '20 at 20:08
  • $\begingroup$ @mhum. Sorry, actually it's not so much about the enumerator--I'm not being clear. Let me be: can you manufacture an enumerator for any enumerable language so that it includes extra data that the verifier can use to quickly determine what position it was in the enumeration. My question is basically: can such an enumerator be constructed for any enumerable language? $\endgroup$
    – user121977
    Jun 3 '20 at 20:13

Your Answer

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