Non-coding Enumeration Operators

摘要

An enumeration operator maps each set A of natural numbers to a set E(A) is contained in N, in such a way that E(A) can be enumerated uniformly from every enumeration of A. The maximum possible Turing degree of E(A) is therefore the degree of the jump A'. It is impossible to have E(A) ≡T A' for all A, but possible to achieve this for all A outside a meager set of Lebesgue measure 0. We consider the properties of two specific enumeration operators: the HTP operator, mapping a set W of prime numbers to the set of polynomials realizing Hilbert's Tenth Problem in the ring Z[W~(-1)]; and the root operator, mapping the atomic diagram of an algebraic field F of characteristic; 0 to the set of polynomials in Z[X] with roots in F. These lead to new open questions about enumeration operators in general.