Classes of Recursively Enumerable Sets and Degrees of Unsolvability

DOI10.1002/malq.19660120125zbMath0181.30504OpenAlexW2101746971MaRDI QIDQ5571699

Donald A. Martin

Publication date: 1966

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19660120125

zbMATH Keywords

recursion theory, constructive mathematics

Related Items (only showing first 100 items - show all)

Numberings, c.e. oracles, and fixed points ⋮ Some theorems on R-maximal sets and major subsets of recursively enumerable sets ⋮ Classifying word problems of finitely generated algebras via computable reducibility ⋮ Robust learning with infinite additional information ⋮ Degrees of sets having no subsets of higher m- and t t-degree ⋮ Two theorems on degrees of models of true arithmetic ⋮ On the orbits of hyperhypersimple sets ⋮ Orbits of maximal vector spaces ⋮ Computational depth and reducibility ⋮ Computational depth and reducibility ⋮ Nonhemimaximal degrees and the high/low hierarchy ⋮ Upper bounds for the arithmetical degrees ⋮ On the Relations between Some Rate-of-Growth Conditions ⋮ ON THE DEFINABILITY OF THE DOUBLE JUMP IN THE COMPUTABLY ENUMERABLE SETS ⋮ The degrees of hyperhyperimmune sets ⋮ Maximal theories ⋮ Working below a high recursively enumerable degree ⋮ Inductive inference and reverse mathematics ⋮ Degrees of recursively enumerable sets which have no maximal supersets ⋮ A Decidable Fragment of the Elementary Theory of the Lattice of Recursively Enumerable Sets ⋮ Almost everywhere domination ⋮ Simplicity of recursively enumerable sets ⋮ Lattice of recursively enumerable subalgebras of a recursive Boolean algebra ⋮ On the Degrees of Index Sets ⋮ On the strength of Ramsey's theorem ⋮ A limit on relative genericity in the recursively enumerable sets ⋮ Spectrum of the field of computable real numbers ⋮ Deficiency Sets and Bounded Information Reducibilities ⋮ The lattice of recursively enumerable substructures of an effective closure system ⋮ Nonbounding and Slaman triples ⋮ Initial segments of the degrees of unsolvability Part II: minimal degrees ⋮ Coding in the partial order of enumerable sets ⋮ There is no fat orbit ⋮ On the lattices of NP-subspaces of a polynomial time vector space over a finite field ⋮ COMPUTABLE POLISH GROUP ACTIONS ⋮ THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY ⋮ Recursively enumerable sets which are uniform for finite extensions ⋮ Three theorems on tt-degrees ⋮ On the Lattice of Recursively Enumerable Sets ⋮ Degree theoretic definitions of the low₂ recursively enumerable sets ⋮ A superhigh diamond in the c.e. tt-degrees ⋮ Dimensions of Points in Self-similar Fractals ⋮ On the Degrees of Index Sets. II ⋮ Honest polynomial time reducibilities and the \(P=?NP\) problem ⋮ Weakly Represented Families in Reverse Mathematics ⋮ Complexity-theoretic algebra. II: Boolean algebras ⋮ Minimal-program complexity of pseudo-recursive and pseudo-random sequences ⋮ Definable relations in Turing degree structures ⋮ The Complexity of Orbits of Computably Enumerable Sets ⋮ On very high degrees ⋮ Degrees bounding principles and universal instances in reverse mathematics ⋮ A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES ⋮ Jump inversions inside effectively closed sets and applications to randomness ⋮ The nonlow computably enumerable degrees are not invariant in $\mathcal {E}$ ⋮ Automorphisms of the lattice of $\Pi _1^0$ classes; perfect thin classes and anc degrees ⋮ Indifferent sets for genericity ⋮ Codable sets and orbits of computably enumerable sets ⋮ Computably enumerable sets and related issues ⋮ Computable analogs of cardinal characteristics: prediction and rearrangement ⋮ Countable thin \(\Pi^0_1\) classes ⋮ Recursive isomorphism types of recursive Boolean algebras ⋮ Pointwise decomposable sets ⋮ The extent and density of sequences within the minimal-program complexity hierarchies ⋮ Two existence theorems for computable numerations ⋮ Small \(\Pi^{0}_{1}\) classes ⋮ Jump equivalence of the Δ₂⁰ hyperimmune sets ⋮ Relativized Schnorr tests with universal behavior ⋮ Index sets and universal numberings ⋮ Schnorr triviality and genericity ⋮ Automorphisms of the Lattice of Recursively Enumerable Sets: Promptly Simple Sets ⋮ Maximal and Cohesive vector spaces ⋮ -MAXIMAL SETS ⋮ Asymptotic density and the coarse computability bound ⋮ \(r\)-maximal major subsets ⋮ Turing computability: structural theory ⋮ Elementary differences among jump classes ⋮ α-Degrees of maximal α-r.e. sets ⋮ Supersets of recursively enumerable sets ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Recursively enumerable sets and degrees ⋮ Computational complexity, speedable and levelable sets ⋮ On a conjecture of Dobrinen and Simpson concerning almost everywhere domination ⋮ Low sets without subsets of higher many-one degree ⋮ Pigeons do not jump high ⋮ Bounding non-GL₂ and R.E.A. ⋮ Double jumps of minimal degrees ⋮ Tracing and domination in the Turing degrees ⋮ Degree invariance in the Π₁⁰classes ⋮ Uniform almost everywhere domination ⋮ Hypersimple sets with retraceable complements ⋮ Recursion theory on orderings. I. A model theoretic setting ⋮ Recursion theory on orderings. II ⋮ On r.e. and co-r.e. vector spaces with nonextendible bases ⋮ Definable properties of the computably enumerable sets ⋮ Some orbits for \({\mathcal E}\) ⋮ When van Lambalgen’s Theorem fails ⋮ Prime models of computably enumerable degree ⋮ Automorphisms of the lattice of recursively enumerable sets ⋮ Orbits of computably enumerable sets: Low sets can avoid an upper cone ⋮ ON SUPERSETS OF NON-LOW SETS

This page was built for publication: Classes of Recursively Enumerable Sets and Degrees of Unsolvability