On the Turing degrees of minimal index sets

DOI10.1016/j.apal.2007.07.003zbMath1128.03033OpenAlexW2113988846MaRDI QIDQ2382278

Jason Teutsch

Publication date: 28 September 2007

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

Full work available at URL: https://doi.org/10.1016/j.apal.2007.07.003

zbMATH Keywords

minimal indicesTuring degreestruth-table degreesKolmogorov numberingsshortest descriptionsshortest programs

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45) Other Turing degree structures (03D28)

Related Items

On the Turing degrees of minimal index sets ⋮ An incomplete set of shortest descriptions ⋮ Index Sets and Universal Numberings ⋮ Index sets and universal numberings ⋮ On Approximate Decidability of Minimal Programs

Cites Work

• Unnamed Item
• Immunity and hyperimmunity for sets of minimal indices
• A guided tour of minimal indices and shortest descriptions
• On the Turing degrees of minimal index sets
• Three theorems on the degrees of recursively enumerable sets
• Turing Computability
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• Program size in restricted programming languages
• On btt‐Degrees of Sets of Minimal Numbers in Gödel Numberings
• Recursively enumerable sets and degrees
• Bounded Immunity and Btt-Reductions
• On the complexity of random strings
• Degrees of Unsolvability. (AM-55)
• On the Degrees of Index Sets
• The Friedberg-Muchnik Theorem Re-Examined
• Recursive Enumerability and the Jump Operator
• A Theorem on Hypersimple Sets