# What do you call a set which has the following enumeration-related machine?

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?

• 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$"? – fade2black Aug 18 '17 at 0:19
• @fade2black: See edit. – einpoklum Aug 18 '17 at 7:43
• 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? – fade2black Aug 18 '17 at 8:19
• @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. – einpoklum Aug 18 '17 at 8:24
• 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. – fade2black Aug 18 '17 at 8:39