Friedberg [1] and Mu\u010dnik [4] famously constructed computably enumerable sets of whole numbers that are noncomputable but do not code the halting set. To build their examples, they independently developed the priority method, a dynamic and flexible construction framework. Harrington and Soare [2] showed that one can identify such examples using only the structure of the collection $\\mathcal{E}$ of computably enumerable (c.e.) sets under set containment. In other words, they gave a (nonempty) property $Q$ in terms of set containment that is satisfied in $\\mathcal{E}$ by only incomplete noncomputable c.e. sets. All c.e. sets that satisfy $Q$ have a slow enumeration property called $2$-tardiness [3]. We explore $n$-tardiness, as a means to further understand the interplay between dynamic enumeration properties of c.e. sets and static structural properties of $\\mathcal{E}$. We also discuss the structure of $\\mathcal{D}$-maximal sets, generalizations of both maximal and hemimaximal sets in $\\mathcal{E}$. We use both tardiness and $\\mathcal{D}$-maximality to further develop the picture of orbits of sets under automorphisms of $\\mathcal{E}$.<\/em><\/p>\n This is joint work with Peter Cholak and Peter Gerdes.<\/em><\/p>\n References<\/p>\n [1] Richard M. Friedberg. Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post’s problem, 1944). Proc. Nat. Acad. Sci. U.S.A.<\/em>, 43:236-238, 1957. Dynamic and structural properties of the computably enumerable sets Abstract: Friedberg [1] and Mu\u010dnik [4] famously constructed computably enumerable sets of whole numbers that are noncomputable but do not code the halting set. To build their examples, they independently developed the priority method, a dynamic and flexible construction framework. Harrington and Soare [2] showed that … Continue reading Karen Lange<\/span>
\n[2] Leo Harrington and Robert I. Soare. Post’s program and incomplete recursively enumerable sets. Proc. Nat. Acad. Sci. U.S.A.<\/em>, 88(22):10242-10246, 1991.
\n[3] Leo Harrington and Robert I. Soare. Codable sets and orbits of computably enumerable sets. J. Symbolic Logic<\/em>, 63(1):1-28, 1998.
\n[4] A. A. Mu\u010dnik. On the unsolvability of the problem of reducibility in the theory of algorithms. Dokl. Akad. Nauk SSSR (N.S.)<\/em>, 108:194-197, 1956.<\/p>\n","protected":false},"excerpt":{"rendered":"