Splitting theorems in recursion theory

DOI10.1016/0168-0072(93)90234-5zbMATH Open0792.03028OpenAlexW2070295070MaRDI QIDQ1314544FDOQ1314544

Michael Stob, Rodney G. Downey

Publication date: 17 February 1994

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(93)90234-5

zbMATH Keywords

r.e. degreelattice of r.e. setsdefinability of the jump operatorPost's Programsplitting of r.e. setssplitting theorems in classical recursion theory

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Classical recursion theory. Vol. II
• Σ₂-collection and the infinite injury priority method
• Pseudo Jump Operators. I: The R. E. Case
• Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers
• Recursively enumerable sets of positive integers and their decision problems
• The d.r.e. degrees are not dense
• On the degrees less than 0'
• An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees
• D.R.E. Degrees and the Nondiamond Theorem
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Automorphisms of the Lattice of Recursively Enumerable Sets: Promptly Simple Sets
• Post's program and incomplete recursively enumerable sets.
• Degrees in Which the Recursive Sets are Uniformly Recursive
• Automorphisms of the lattice of recursively enumerable sets: Orbits
• Automorphisms of the lattice of recursively enumerable sets
• Diagonals and semihyperhypersimple sets
• Diagonals and -maximal sets
• Interpolation and embedding in the recursively enumerable degrees
• The undecidability of the recursively enumerable degrees
• A recursively enumerable degree which will not split over all lesser ones
• An extension of the nondiamond theorem in classical and α-recursion theory
• Decomposition of Recursively Enumerable Degrees
• The weak truth table degrees of recursively enumerable sets
• Working below a \(low_ 2\) recursively enumerable degree
• The theory of the recursively enumerable weak truth-table degrees is undecidable
• Degrees of classes of RE sets
• On the Lattice of Recursively Enumerable Sets
• Completely mitotic r. e. degrees
• \(\Delta\)\( ^ 0_ 2\) degrees and transfer theorems
• A non-inversion theorem for the jump operator
• Splitting properties and jump classes
• On Pairs of Recursively Enumerable Degrees
• Characterization of Recursively Enumerable Sets with Supersets Effectively Isomorphic to all Recursively Enumerable Sets
• Lattice embeddings into the recursively enumerable degrees
• Degree theoretical splitting properties of recursively enumerable sets
• Recursively enumerable generic sets
• Branching Degrees above low Degrees
• Jumps of Hemimaximal Sets
• Computational complexity, speedable and levelable sets
• Mitotic recursively enumerable sets
• Friedberg splittings of recursively enumerable sets
• The intervals of the lattice of recursively enumerable sets determined by major subsets
• A Splitting Theorem for the N-R.E. Degrees
• Intervals and sublattices of the r.e. weak truth table degrees. I: Density
• Automorphisms of the lattice of recursively enumerable sets. Part II: Low sets
• Bounding minimal pairs
• Lattice embeddings into the recursively enumerable degrees. II
• Lattice nonembeddings and initial segments of the recursively enumerable degrees
• Highness and bounding minimal pairs
• Invariance of properties under automorphisms of the lattice of recursively enumerable sets
• Three theorems on the degrees of recursively enumerable sets
• The Priority Method I
• Subsets of hypersimple sets
• The universal splitting property. II
• On complexity properties of recursively enumerable sets
• Structural interactions of the recursively enumerable T- and W-degrees
• The Degrees of R.E. Sets Without the Universal Splitting Property
• Anti‐Mitotic Recursively Enumerable Sets
• Splitting properties of r.e. sets and degrees
• Degrees of Splittings and Bases of Recursively Enumerable Subspace
• Classification of degree classes associated with r.e. subspaces
• Minimal pairs in initial segments of the recursively enumerable degrees
• A jump class of noncappable degrees
• T-Degrees, Jump Classes, and Strong Reducibilities
• Logic year 1979--80, The University of Connecticut, USA
• Determining Automorphisms of the Recursively Enumerable Sets
• Recursion theory week. Proceedings of a conference held in Oberwolfach, Germany, March 19-25, 1989
• Array nonrecursive degrees and lattice embeddings of the diamond
• Jumps of nontrivial splittings of recursively enumerable sets
• Decomposition and infima in the computably enumerable degrees
• Index sets and degrees of unsolvability
• The jump is definable in the structure of the degrees of unsolvability
• Degree theoretic definitions of the low₂ recursively enumerable sets
• Recursion, metarecursion, and inclusion

Cited In (22)

• Friedberg splittings of recursively enumerable sets
• Nonuniformity of downward density in \(n\)-computably enumerable Turing degrees
• Infimum properties differ in the weak truth-table degrees and the Turing degrees
• Some recent research directions in the computably enumerable sets
• Introduction to Autoreducibility and Mitoticity
• Lattice embeddings below a nonlow\(_ 2\) recursively enumerable degree
• Completely mitotic c.e. degrees and non-jump inversion
• Splitting theorems and the jump operator
• New Computational Paradigms
• Turing computability: structural theory
• Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility
• Splittings of effectively speedable sets and effectively levelable sets
• Splitting the relative assembly map, nil-terms and involutions
• On the bounded quasi‐degrees of c.e. sets
• Non-cupping, measure and computably enumerable splittings
• Contiguity and distributivity in the enumerable Turing degrees
• There Are No Maximal d.c.e. wtt-degrees
• Maximal contiguous degrees
• A Survey of Results on the d-c.e. and n-c.e. Degrees
• How to Split Recursive Automata
• Some orbits for \({\mathcal E}\)
• Implicit measurements of dynamic complexity properties and splittings of speedable sets

Recommendations

• GENERALIZATIONS OF THE RECURSION THEOREM 👍 👎
• Degree theoretical splitting properties of recursively enumerable sets 👍 👎
• Friedberg splittings of recursively enumerable sets 👍 👎
• The combinatorics of the splitting theorem 👍 👎
• Some reducibilities and splittings of recursively enumerable sets 👍 👎
• Splitting recursively enumerable subalgebras in recursive Boolean algebras 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Splitting theorems in recursion theory

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