Immunity and hyperimmunity for sets of minimal indices

DOI10.1215/00294527-2008-001MaRDI QIDQ929628zbMATH OpenOpenAlexFDO

Authors Frank Stephan, Jason Teutsch

Publication date 18 June 2008

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1215/00294527-2008-001

zbMATH Keywords

arithmetical hierarchy[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=G%EF%BF%BD%EF%BF%BDdel+numberings&go=Go G��del numberings]hyperimmune setsimmune setsKolmogorov numberingssets of minimal indicessets of random strings

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Theory of numerations, effectively presented structures (03D45) Hierarchies of computability and definability (03D55) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• On Some Complexity Characteristics of Immune Sets
• ON THE STRUCTURE OF FAMILIES OF IMMUNE, HYPERIMMUNE AND HYPERHYPERIMMUNE SETS
• Hyperimmunity in \(2^{\mathbb N}\)
• Theory and Applications of Models of Computation
• \(e\)-immune sets
• Immunity for closed sets
• Extending finite subsets of an immune set
• Immune sets in monotone infection rules. Characterization and complexity
• A characterization of the δ₂⁰ hyperhyperimmune sets
• The degrees of bi-hyperhyperimmune sets

Cited in

(7)

• An incomplete set of shortest descriptions
• On \(\Delta ^ P_ 2\)-immunity
• Immunity and non-cupping for closed sets
• Bi-immunity over different size alphabets
• On approximate decidability of minimal programs
• On the Turing degrees of minimal index sets
• Searching for shortest and least programs

This page was built for publication: Immunity and hyperimmunity for sets of minimal indices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q929628)