Post's program and incomplete recursively enumerable sets.

DOI10.1073/pnas.88.22.10242zbMath0767.03022OpenAlexW1996663206WikidataQ37622685 ScholiaQ37622685MaRDI QIDQ4024700

Robert I. Soare, Leo Harrington

Publication date: 9 February 1993

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1073/pnas.88.22.10242

zbMATH Keywords

lattice of recursively enumerable setsPost's programTuring complete sets

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

2011 North American Annual Meeting of the Association for Symbolic Logic, Coding in the partial order of enumerable sets, There is no fat orbit, Extending and interpreting Post's programme, On \(n\)-tardy sets, The Complexity of Orbits of Computably Enumerable Sets, Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets, A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES, On the structures inside truth-table degrees, Friedberg splittings of recursively enumerable sets, Automorphisms of the lattice of $\Pi _1^0$ classes; perfect thin classes and anc degrees, Codable sets and orbits of computably enumerable sets, Computably enumerable sets and related issues, 2001 Annual Meeting of the Association for Symbolic Logic, Automorphisms of the Lattice of Recursively Enumerable Sets: Promptly Simple Sets, On the orbits of computably enumerable sets, Permutations and Presentations, Hierarchy of Computably Enumerable Degrees II, Recursively enumerable sets and degrees, Post's problem for ordinal register machines: an explicit approach, Definable properties of the computably enumerable sets, Some orbits for \({\mathcal E}\), Orbits of computably enumerable sets: Low sets can avoid an upper cone, Cappable recursively enumerable degrees and Post's program, Splitting theorems in recursion theory, Bounded Immunity and Btt-Reductions, On orbits, of prompt and low computably enumerable sets, Definable incompleteness and Friedberg splittings