1
$\begingroup$

A set $S$ of natural numbers is Recursively Enumerable if there exists a Turing machine which enumerates them, i.e. given no input, outputs the elements of $S$ in increasing order (never halting if $S$ is infinite).

Now, suppose my set has a different kind of machine: Instead of enumerating the set, it takes an integer $i$ as input, outputs the $i$-th lowest element of $S$...

Case 1. in ascending order.
Case 2. in an arbitrary order (but the same order for all $i$)

... and halts. Also suppose the machine is in some complexity class $\mathcal{C}$.

Is there a commonly-used term for such a set, in either of the cases?

$\endgroup$
  • $\begingroup$ Your question is not clear. $S$ is a set, and no more. It is not ordered, so what is the meaning of "$i$-th element of $S$"? $\endgroup$ – fade2black Aug 18 '17 at 0:19
  • $\begingroup$ @fade2black: See edit. $\endgroup$ – einpoklum Aug 18 '17 at 7:43
  • $\begingroup$ I don't know if the problem has any relation to the Kolmogorov complexity, but if for $S$ there is a TM which given $i$ outputs $i$-th lowest element of $S$, then you can easily construct another TM which would decide (say yes/no) if $x \in S$. In this case the set would be called recursive (or computable). But I still don't understand what the cases 1 and 2 have to do with the second TM in your post. Are you interested in enumerating the set in some particular order? $\endgroup$ – fade2black Aug 18 '17 at 8:19
  • $\begingroup$ @fade2black: It's vaguely related to K. complexity, since if you think of $S$ as a vector of bits of length |S|, enumerating S is like printing our that vector. Thus pair (M, |S|) is an encoding of that bit vector. $\endgroup$ – einpoklum Aug 18 '17 at 8:24
  • $\begingroup$ I agree, so you must be interested in enumerating in some specific order, right? For example, you want to list all integers in $S$ ascending order. But I don't think that such sets has special names. At least I have never heard about such kind of terminology. $\endgroup$ – fade2black Aug 18 '17 at 8:39

Your Answer

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

Browse other questions tagged or ask your own question.