scientific article

Publication date: 1983

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

upper semilattice degrees of unsolvability initial segments jump operator Countable ideals

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Other degrees and reducibilities in computability and recursion theory (03D30) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

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

There is no ordering on the classes in the generalized high/low hierarchies ⋮ The Σ 2 theory of D h ( ⩽ h O ) as an uppersemilattice with least and greatest element is decidable ⋮ Bounding minimal degrees by computably enumerable degrees ⋮ Upper bounds for the arithmetical degrees ⋮ The complexity of reversible cellular automata ⋮ Lattices of c-degrees ⋮ Working below a high recursively enumerable degree ⋮ The ∀∃-theory of ℛ(≤,∨,∧) is undecidable ⋮ Turing incomparability in Scott sets ⋮ Nonisomorphism of lattices of recursively enumerable sets ⋮ THEOREMS OF HYPERARITHMETIC ANALYSIS AND ALMOST THEOREMS OF HYPERARITHMETIC ANALYSIS ⋮ On the embedding of α-recursive presentable lattices into the α-recursive degrees below 0′ ⋮ Lower bounds on degrees of game-theoretic structures ⋮ Diagonalizations over polynomial time computable sets ⋮ Degrees of unsolvability of continuous functions ⋮ Π₁¹ relations and paths through ⋮ RAMSEY-LIKE THEOREMS AND MODULI OF COMPUTATION ⋮ Undecidable fragments of elementary theories ⋮ Initial segments of the degrees of constructibility ⋮ Degrees of Unsolvability: A Tutorial ⋮ The degrees of conditional problems ⋮ The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable ⋮ Graph isomorphism is in the low hierarchy ⋮ Some remarks on the algebraic structure of the Medvedev Lattice ⋮ 1994 Annual Meeting of the Association for Symbolic Logic ⋮ 2-minimality, jump classes and a note on natural definability ⋮ The jump is definable in the structure of the degrees of unsolvability ⋮ A 1-generic degree which bounds a minimal degree ⋮ The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility ⋮ Initial segments of the lattice of ideals of r.e. degrees ⋮ Embedding lattices into the wtt-degrees below 0′ ⋮ On initial segment complexity and degrees of randomness ⋮ Cellular automata and intermediate degrees. ⋮ Degree theoretic definitions of the low₂ recursively enumerable sets ⋮ ON THE DECIDABILITY OF THE THEORIES OF THE ARITHMETIC AND HYPERARITHMETIC DEGREES AS UPPERSEMILATTICES ⋮ Structural theory of degrees of unsolvability: advances and open problems ⋮ A Rigid Cone in the Truth-Table Degrees with Jump ⋮ A measure-theoretic proof of Turing incomparability ⋮ The undecidability of the Π₄-theory for the r.e. wtt and Turing degrees ⋮ Degrees of asynchronously automaton transformations ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ Some logically weak Ramseyan theorems ⋮ The finite intervals of the Muchnik lattice ⋮ WEAKLY 2-RANDOMS AND 1-GENERICS IN SCOTT SETS ⋮ TD implies \(\operatorname{CC}_{\mathbb{R}} \) ⋮ Cofinal maximal chains in the Turing degrees ⋮ Strong polynomial-time reducibility ⋮ The complexity types of computable sets ⋮ Decidability of the AE-theory of the lattice of \({\Pi}_1^0\) classes ⋮ Embedding jump upper semilattices into the Turing degrees ⋮ Generic degrees are complemented ⋮ The property “arithmetic-is-recursive” on a cone ⋮ Topological aspects of the Medvedev lattice ⋮ Joining up to the generalized high degrees ⋮ A survey of results on the d.c.e. and \(n\)-c.e. degrees ⋮ Turing degrees of reals of positive effective packing dimension ⋮ Embedding and coding below a 1-generic degree ⋮ Fragments of the theory of the enumeration degrees ⋮ Forcing in Proof Theory ⋮ Lattice initial segments of the hyperdegrees ⋮ On computational complexity and honest polynomial degrees ⋮ Working below a \(low_ 2\) recursively enumerable degree ⋮ Constructive logic and the Medvedev lattice ⋮ Maximal chains in the Turing degrees ⋮ Arithmetical Sacks forcing ⋮ Undecidability and initial segments of the (r.e.) tt-degrees ⋮ Turing computability: structural theory ⋮ Local Initial Segments of The Turing Degrees ⋮ Cohen and Set Theory ⋮ Decidability and Invariant Classes for Degree Structures ⋮ Classifying model-theoretic properties ⋮ Mass Problems and Randomness ⋮ Model-theoretic properties of Turing degrees in the Ershov difference hierarchy ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Coding true arithmetic in the Medvedev and Muchnik degrees ⋮ Probabilistic complexity classes and lowness ⋮ The undecidability of the elementary theory of lattices of all equational theories of large signature ⋮ The atomic model theorem and type omitting ⋮ Initial segments of the degrees of size \(\aleph _ 1\) ⋮ On minimal pairs of enumeration degrees ⋮ Complete sets and closeness to complexity classes ⋮ The jump operator on the \(\omega \)-enumeration degrees ⋮ Turing oracle machines, online computing, and three displacements in computability theory ⋮ Quasi-minimal enumeration degrees and minimal Turing degrees ⋮ Extensions of embeddings below computably enumerable degrees ⋮ Mass Problems and Measure-Theoretic Regularity ⋮ Measure theory aspects of locally countable orderings ⋮ Degree Structures: Local and Global Investigations ⋮ Randomness and Computability: Open Questions ⋮ A note on the join property ⋮ Non-cupping and randomness ⋮ Noncappable enumeration degrees below 0_e^′ ⋮ 1-generic splittings of computably enumerable degrees ⋮ ON SUPERSETS OF NON-LOW SETS ⋮ On the Computable Theory of Bounded Analytic Functions ⋮ The Baire category theorem in weak subsystems of second-order arithmetic ⋮ On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets ⋮ Low Level Nondelegability Results: Domination and Recursive Enumeration ⋮ A reducibility related to being hyperimmune-free ⋮ Weak truth table degrees of structures

This page was built for publication: