Immunity and hyperimmunity for sets of minimal indices

DOI10.1215/00294527-2008-001zbMath1142.03024OpenAlexW1979770457MaRDI QIDQ929628

Jason Teutsch, Frank Stephan

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 hierarchyGödel numberingshyperimmune setsimmune setsKolmogorov numberingssets of minimal indicessets of random strings

Mathematics Subject Classification ID

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

Related Items

On the Turing degrees of minimal index sets ⋮ An incomplete set of shortest descriptions ⋮ Bi-immunity over different size alphabets ⋮ Searching for shortest and least programs ⋮ On Approximate Decidability of Minimal Programs