Post's program and incomplete recursively enumerable sets.

DOI10.1073/PNAS.88.22.10242MaRDI QIDQ4024700zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Recommendations

• Cappable recursively enumerable degrees and Post's program
• scientific article; zbMATH DE number 3896921
• scientific article; zbMATH DE number 4057497
• Completely recursively enumerable sets
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• On a Class of Recursively Enumerable Sets
• Recursively enumerable sets of positive integers and their decision problems
• Computably enumerable sets and related issues
• RECURSIVELY ENUMERABLE SETS AND WELL-ORDERING OF THEIR ENUMERATIONS
• On \(sQ\)-completeness of recursively enumerable sets

Cited in

(32)

• Post's problem for ordinal register machines: an explicit approach
• Definable properties of the computably enumerable sets
• Cappable recursively enumerable degrees and Post's program
• Splitting theorems in recursion theory
• Coding in the partial order of enumerable sets
• Some orbits for \({\mathcal E}\)
• Orbits of computably enumerable sets: Low sets can avoid an upper cone
• There is no fat orbit
• On the structures inside truth-table degrees
• Automorphisms of the lattice of _1⁰ classes; perfect thin classes and anc degrees
• 2001 Annual Meeting of the Association for Symbolic Logic. University of Pennsylvania, Philadelphia, PA, March 10-13, 2001
• 2011 North American Annual Meeting of the Association for Symbolic Logic, University of California at Berkeley, Berkeley, CA, USA, March 24--27, 2011
• On the orbits of computably enumerable sets
• On orbits, of prompt and low computably enumerable sets
• Definable incompleteness and Friedberg splittings
• Hierarchy of Computably Enumerable Degrees II
• A Post's program for complexity theory.
• Automorphisms of the Lattice of Recursively Enumerable Sets: Promptly Simple Sets
• Recursively enumerable sets and degrees
• Bounded Immunity and Btt-Reductions
• Permutations and Presentations
• On \(n\)-tardy sets
• Codable sets and orbits of computably enumerable sets
• scientific article; zbMATH DE number 1163992 (Why is no real title available?)
• A hierarchy of computably enumerable degrees
• Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets
• Extending properly n - REA sets1
• The Complexity of Orbits of Computably Enumerable Sets
• Extending and interpreting Post's programme
• Some recent research directions in the computably enumerable sets
• Friedberg splittings of recursively enumerable sets
• Computably enumerable sets and related issues

This page was built for publication: Post's program and incomplete recursively enumerable sets.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4024700)