1991/11/15 by Louise Harrington, Robert I. Soare · 1 citation
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Advanced Topology and Set Theory #Advanced Algebra and Logic #Recursively enumerable language #Recursively enumerable set #Maximal set #Mathematics #Turing #Combinatorics #Set (abstract data type) #Discrete mathematics #Existential quantification #Algebraic number #Order (exchange) #Computer science
paper · doi:10.1073/pnas.88.22.10242
openalex publication_date 1991/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
A set A of nonnegative integers is recursively enumerable (r.e.) if A can be computably listed. It is shown that there is a first-order property, Q(X), definable in E, the lattice of r.e. sets under inclusion, such that (i) if A is any r.e. set satisfying Q(A) then A is nonrecursive and Turing incomplete and (ii) there exists an r.e. set A satisfying Q(A). This resolves a long open question stemming from Post's program of 1944, and it sheds light on the fundamental problem of the relationship between the algebraic structure of an r.e. set A and the (Turing) degree of information that A encodes.