Relationships Between Reducibilities

DOI10.2307/1995354zbMath0188.02604OpenAlexW4252915084MaRDI QIDQ5581615

Carl G. jun. Jockusch

Publication date: 1969

Full work available at URL: https://doi.org/10.2307/1995354

zbMATH Keywords

recursion theory, constructive mathematics

Related Items

Recursively enumerable \(m\)- and \(tt\)-degrees. II: The distribution of singular degrees, Positive equivalences, Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility, Three theorems on tt-degrees, Irreducible, singular, and contiguous degrees, Countable thin \(\Pi^0_1\) classes, Index sets of degrees of unsolvability, Truth tabular degrees of recursively enumerable sets, Lattice properties of Rogers semilattices of compuatble and generalized computable families, Recursively enumerable bw-degrees, Recursively enumerable sets and degrees, T-Degrees, Jump Classes, and Strong Reducibilities, Computable permutations and word problems, Two Theorems on Truth Table Degrees, Hypersimple sets with retraceable complements, Hereditary sets and tabular reducibility, Relations between table-type degrees, Strong reducibilities, The members of thin and minimal \(\Pi_1^0\) classes, their ranks and Turing degrees

Cites Work

• Recursively enumerable many-one degrees
• Three theorems on the degrees of recursively enumerable sets
• Recursive and Recursively Enumerable Orders
• Retraceable Sets
• A Note on Bounded-Truth-Table Reducibility
• Linear orderings under one-one reducibility
• Recursion Theory and Dedekind Cuts
• On Properties of Regressive Sets
• Semirecursive Sets and Positive Reducibility
• Recursive Functions Modulo Co-r-Maximal Sets
• The Degrees of Hyperimmune Sets
• A Theorem on Hypersimple Sets
• Recursively enumerable sets of positive integers and their decision problems
• Creative sets