Turing computability: structural theory

DOI10.1007/s10958-021-05418-yOpenAlexW3171742265MaRDI QIDQ2036465

M. M. Yamaleev, Marat M. Arslanov

Publication date: 29 June 2021

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-021-05418-y

zbMATH Keywords

definabilityTuring degreecomputably enumerable setErshov's hierarchy

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Other Turing degree structures (03D28) Hierarchies of computability and definability (03D55)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Downward density of exact degrees
• On a problem of Ishmukhametov
• Working below a \(low_ 2\) recursively enumerable degree
• Decomposability of low 2-computably enumerable degrees and Turing jumps in the Ershov hierarchy
• Splitting in 2-computably enumerable degrees with avoiding cones
• Degrees of unsolvability: structure and theory
• The elementary theory of the recursively enumerable degrees is not \(\aleph _ 0\)-categorical
• Structural theory of degrees of unsolvability: advances and open problems
• Definability in the Turing degrees
• The density of the low\(_ 2\) \(n\)-r.e. degrees
• The d.r.e. degrees are not dense
• On the r. e. predecessors of d. r. e. degrees
• Splitting theorems in recursion theory
• On relative enumerability of Turing degrees
• The elementary theory of recursively enumerable sets
• Non-uniformity and generalised Sacks splitting
• Interpolating \(d\)-r.e. and REA degrees between r.e. degrees
• Corrigendum to: ``The d.r.e. degrees are not dense
• Splitting and cone avoidance in the d.c.e. degrees
• The recursively enumerable degrees are dense
• On a hierarchy of sets. III
• Interpolation and embedding in the recursively enumerable degrees
• On the degrees less than 0'
• A splitting theorem for $n-REA$ degrees
• THE n-r.e. DEGREES: UNDECIDABILITY AND Σ₁ SUBSTRUCTURES
• Nondensity of Double Bubbles in the D.C.E. Degrees
• Decomposition and infima in the computably enumerable degrees
• Algorithmic Randomness and Complexity
• Nonexistence of Minimal Pairs in $$L[{\mathbf d}$$]
• A minimal degree less than 0’
• An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees
• On Σ₁-Structural Differences Among Finite Levels of the Ershov Hierarchy
• Decidability and Invariant Classes for Degree Structures
• The jump is definable in the structure of the degrees of unsolvability
• On Downey's conjecture
• The undecidability of the recursively enumerable degrees
• Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers
• D.R.E. Degrees and the Nondiamond Theorem
• Lattice embeddings into the recursively enumerable degrees
• Interpretability and Definability in the Recursively Enumerable Degrees
• Finitely Generated Codings and the Degrees R.E. in a Degree d
• A Splitting Theorem for the N-R.E. Degrees
• A recursively enumerable degree which will not split over all lesser ones
• Degrees of classes of RE sets
• Lattice embeddings into the recursively enumerable degrees. II
• The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
• Relative enumerability in the difference hierarchy
• Automorphisms of the lattice of recursively enumerable sets
• Algebraic aspects of the computably enumerable degrees.
• Turing Definability in the Ershov Hierarchy
• Cupping the Recursively Enumerable Degrees by D.R.E. Degrees
• Differences of Computably Enumerable Sets
• On the Lattice of Recursively Enumerable Sets
• Isolation and lattice embeddings
• ON THE DEFINABILITY OF THE DOUBLE JUMP IN THE COMPUTABLY ENUMERABLE SETS
• The nonlow computably enumerable degrees are not invariant in $\mathcal {E}$
• Definable relations in Turing degree structures
• On the existence of a strong minimal pair
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Distributive Initial Segments of the Degrees of Unsolvability
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Trial and error predicates and the solution to a problem of Mostowski
• Degrees of recursively enumerable sets which have no maximal supersets
• Hierarchies of Boolean algebras
• The Δ₃⁰-automorphism method and noninvariant classes of degrees
• New Computational Paradigms
• Extension of embeddings in the computably enumerable degrees

This page was built for publication: Turing computability: structural theory