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

Mathematics Subject Classification ID

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

Review text

Given an equivalence relation \(\equiv\) on c.e. sets of natural numbers, one may define a corresponding set of minimal indices \(\{\,e\mid j<e\Rightarrow W_j\not\equiv W_e\,\}\). The authors investigate these sets for various choices of~\(\equiv\) (such as \(=\), \(=^*\), \(\equiv_T\), \(\equiv_m\), and~\(\equiv_1\)), examining the possible complexity in the arithmetical hierarchy of their subsets. A typical result here is that for~\(\equiv_T\), the minimal index set contains no infinite \(\Sigma_3\) subset, but it does contain an infinite \(\Sigma_4\) subset. In contrast, whether or not the minimal index set for \(\equiv_T\) contains an infinite \(\Pi_3\) subset depends on the choice of Gödel numbering for the c.e. sets.

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

(8)

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

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)