Nies, in Computability and Randomness, p. 6, defines "uniformly computably enumerable":

A sequence of sets $(S_e)_{e\in\mathbb{N}}$ such that $\{\langle e,x \rangle : x \in S_e \}$ is c.e. is called uniformly computably enumerable.

I think this means that both the sequence of sets and the members of the sets are jointly c.e., i.e. that even if the sequence of sets is infinite, and/or the sets are infinite in size, one can, step by step, construct the sets in a c.e. manner.

Is that correct?

If that is correct, my further question is what Nies means by his repeated use of "uniformly in" some variable. For example, on page 108 (the one that's puzzling me at the moment), Nies writes:

By the representation of c.e. open sets in 1.8.26 we may uniformly in $m$ obtain an effective antichain $(x^m_i)_{i<N_m}, N_m \in \mathbb{N}\cup\{\infty\}$, ....

If my previous understanding is correct, "uniformly" here means that we construct the antichain (prefix-free set of strings) in a computably enumerable way with respect to both indexes $i$ and $m$ simultaneously.

What does "in $m$" indicate, though?


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.