scientific article

zbMath0465.03024MaRDI QIDQ3916564

Anil Nerode, Richard A. Shore

Publication date: 1980

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

zbMATH Keywords

Turing degreessecond order arithmeticcodingsinitial segments of degreesn-ary relation quantifiersquantifiers over ideals

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

The undecidability of the lattice of r. e. closed subsets of an effective topological space ⋮ Interpolating \(d\)-r.e. and REA degrees between r.e. degrees ⋮ Propositional quantification in the topological semantics for \(\mathbf S4\) ⋮ The jump is definable in the structure of the degrees of unsolvability ⋮ The theory of ceers computes true arithmetic ⋮ Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино? ⋮ Not every finite lattice is embeddable in the recursively enumerable degrees ⋮ ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS ⋮ Computational complexity of theories of a binary predicate with a small number of variables ⋮ Elementary theories and hereditary undecidability for semilattices of numberings ⋮ Embedding and coding below a 1-generic degree ⋮ Definable degrees and automorphisms of 𝒟 ⋮ Propositional quantification in bimodal S5 ⋮ Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter ⋮ Strong reducibilities ⋮ LOGICS FOR PROPOSITIONAL CONTINGENTISM