{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T11:40:11Z","timestamp":1751888411056,"version":"3.41.0"},"reference-count":82,"publisher":"Springer Science and Business Media LLC","issue":"5-6","license":[{"start":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T00:00:00Z","timestamp":1738108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T00:00:00Z","timestamp":1738108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Definitionally: <jats:italic>strongly effectively immune<\/jats:italic> sets are infinite and their c.e.\u00a0subsets have <jats:italic>maximums<\/jats:italic> effectively bounded in their c.e.\u00a0indices; whereas, for <jats:italic>effectively immune<\/jats:italic> sets, their c.e.\u00a0subsets\u2019 <jats:italic>cardinalities<\/jats:italic> are what\u2019re effectively bounded. This definitional difference between these two kinds of sets is very nicely paralleled by the following difference between their <jats:italic>complements<\/jats:italic>. McLaughlin: <jats:italic>strongly<\/jats:italic> effectively immune sets can<jats:italic>not<\/jats:italic> have <jats:italic>immune complements<\/jats:italic>; whereas, the main theorem herein: <jats:italic>effectively<\/jats:italic> immune sets can<jats:italic>not<\/jats:italic> have <jats:italic>hyperimmune complements<\/jats:italic>. Ullian: <jats:italic>effectively<\/jats:italic> immune sets <jats:italic>can<\/jats:italic> have <jats:italic>effectively<\/jats:italic> immune complements. The main theorem <jats:italic>improves<\/jats:italic> Arslanov\u2019s, effectively hyperimmune sets can<jats:italic>not<\/jats:italic> have <jats:italic>effectively<\/jats:italic> hyperimmune complements: the <jats:italic>improvement<\/jats:italic> omits the second \u2018<jats:italic>effectively<\/jats:italic>\u2019. Two <jats:italic>natural<\/jats:italic> examples of <jats:italic>strongly effectively immune<\/jats:italic> sets are presented with new cases of the first proved herein. The first is the set of minimal-Blum-size programs for the partial computable functions; the second, the set of Kolmogorov-random strings. A proved, <jats:italic>natural<\/jats:italic> example is presented of an <jats:italic>effectively dense simple<\/jats:italic>, <jats:italic>not<\/jats:italic> strongly effectively simple set; its complement is a set of maximal run-times. Further motivations for this study are presented. <jats:italic>Kleene<\/jats:italic> recursion theorem proofs herein emphasize how to conceptualize them. Finally, is suggested, future, related work\u2014illustrated by a first, <jats:italic>natural<\/jats:italic>, <jats:italic>strongly effectively<\/jats:italic>\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Sigma _2^0$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msubsup>\n                    <mml:mi>\u03a3<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:msubsup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-<jats:italic>immune set<\/jats:italic>\u2014included: solution of an open problem from Rogers\u2019 book.<\/jats:p>","DOI":"10.1007\/s00153-024-00958-x","type":"journal-article","created":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T01:37:12Z","timestamp":1738114632000},"page":"819-841","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Constructivity conditions on immune sets"],"prefix":"10.1007","volume":"64","author":[{"given":"John","family":"Case","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,29]]},"reference":[{"key":"958_CR1","unstructured":"Rogers, H.: Theory of Recursive Functions and Effective Computability. McGraw Hill, New York(1967). Reprinted, MIT Press, (1987)"},{"key":"958_CR2","doi-asserted-by":"crossref","first-page":"331","DOI":"10.2307\/2964292","volume":"23","author":"H Rogers","year":"1958","unstructured":"Rogers, H.: G\u00f6del numberings of partial recursive functions. J. Symb. Log. 23, 331\u2013341 (1958)","journal-title":"J. Symb. Log."},{"key":"958_CR3","volume-title":"An Introduction to the General Theory of Algorithms","author":"M Machtey","year":"1978","unstructured":"Machtey, M., Young, P.: An Introduction to the General Theory of Algorithms. North Holland, New York (1978)"},{"key":"958_CR4","unstructured":"Riccardi, G.: The independence of control structures in abstract programming systems. PhD thesis, SUNY Buffalo (1980)"},{"key":"958_CR5","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0022-0000(81)90024-6","volume":"22","author":"G Riccardi","year":"1981","unstructured":"Riccardi, G.: The independence of control structures in abstract programming systems. J. Comput. Syst. Sci. 22, 107\u2013143 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"958_CR6","doi-asserted-by":"crossref","unstructured":"Royer, J.: A Connotational Theory of Program Structure. Lecture Notes in Computer Science, vol. 273. Springer, Berlin, Germany (1987)","DOI":"10.1007\/3-540-18253-5"},{"key":"958_CR7","volume-title":"Classical Recursion Theory","author":"P Odifreddi","year":"1989","unstructured":"Odifreddi, P.: Classical Recursion Theory. North-Holland, Amsterdam (1989)"},{"key":"958_CR8","volume-title":"Classical Recursion Theory II","author":"P Odifreddi","year":"1999","unstructured":"Odifreddi, P.: Classical Recursion Theory II. Elsevier, Amsterdam (1999)"},{"key":"958_CR9","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","volume":"50","author":"E Post","year":"1944","unstructured":"Post, E.: Recursively enumerable sets of positive integers and their decision problems. Bull. Am. Math. Soc. 50, 284\u2013316 (1944)","journal-title":"Bull. Am. Math. Soc."},{"key":"958_CR10","doi-asserted-by":"crossref","unstructured":"Li, X.: Effective immune sets, program index sets and effectively simple sets\u2014generalizations and applications of the recursion theorem. In: Chong, C.T., Wicks, W.J. (eds.) Southeast Asian Conference on Logic, pp. 97\u2013106 (1983)","DOI":"10.1016\/S0049-237X(08)70957-1"},{"key":"958_CR11","doi-asserted-by":"crossref","first-page":"33","DOI":"10.4153\/CMB-1965-006-2","volume":"8","author":"T McLaughlin","year":"1965","unstructured":"McLaughlin, T.: On a class of complete sets. Can. Math. Bull. 8, 33\u201337 (1965)","journal-title":"Can. Math. Bull."},{"key":"958_CR12","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1090\/S0002-9939-1964-0180485-7","volume":"15","author":"R Smullyan","year":"1964","unstructured":"Smullyan, R.: Effectively simple sets. Proc. Am. Math. Soc. 15, 893\u2013895 (1964)","journal-title":"Proc. Am. Math. Soc."},{"key":"958_CR13","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1007\/s00224-011-9372-1","volume":"51","author":"J Case","year":"2012","unstructured":"Case, J., Moelius, S.: Program self-reference in constructive Scott subdomains. Theory Comput. Syst. 51, 22\u201349 (2012)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"958_CR14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1080\/09528139408953778","volume":"6","author":"J Case","year":"1994","unstructured":"Case, J.: Infinitary self-reference in learning theory. J. Exp. Theor. Artif. Intell. 6(1), 3\u201316 (1994)","journal-title":"J. Exp. Theor. Artif. Intell."},{"issue":"1","key":"958_CR15","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF01761704","volume":"8","author":"J Case","year":"1974","unstructured":"Case, J.: Periodicity in generations of automata. Math. Syst. Theory 8(1), 15\u201332 (1974)","journal-title":"Math. Syst. Theory"},{"key":"958_CR16","unstructured":"von\u00a0Neumann, J.: Theory of Self\u2013Reproducing Automata. University of Illinois Press, Illinois (1966). Edited and completed by A. W. Burks"},{"key":"958_CR17","doi-asserted-by":"crossref","unstructured":"Case, J.: Directions for computability theory beyond pure mathematical. In: Gabbay, D., Goncharov, S., Zakharyaschev, M. (eds.) Mathematical Problems from Applied Logic II. New Logics for the XXIst Century. ,\u00a0International Mathematical Series, Vol.\u00a05, pp. 53\u201398. Springer, New York, NY (2007). Invited book chapter","DOI":"10.1007\/978-0-387-69245-6_2"},{"key":"958_CR18","unstructured":"Case, J.: Machine self-reference and consciousness. In: proceedings and abstracts of the 3rd annual meeting of the association for the scientific study of consciousness (London, Ontario, 1999). www.eecis.udel.edu\/~case\/slides\/krt-consc-slides.pdf"},{"key":"958_CR19","unstructured":"Case, J.: Algorithmic scientific inference: Within our computable expected reality. International Journal of Unconventional Computing 8(3), 192\u2013206 (2012). Invited journal expansion of an invited talk and paper at the 3rd International Workshop on Physics and Computation 2010"},{"key":"958_CR20","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1090\/S0002-9939-1964-0156780-4","volume":"15","author":"G Sacks","year":"1964","unstructured":"Sacks, G.: A simple set which is not effectively simple. Proc. Am. Math. Soc. 15, 51\u201355 (1964)","journal-title":"Proc. Am. Math. Soc."},{"issue":"4","key":"958_CR21","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1090\/S0002-9939-1966-0216950-5","volume":"17","author":"DA Martin","year":"1966","unstructured":"Martin, D.A.: Completeness, the recursion theorem, and effectively simple sets. Proc. Am. Math. Soc. 17(4), 838\u2013842 (1966)","journal-title":"Proc. Am. Math. Soc."},{"key":"958_CR22","doi-asserted-by":"crossref","unstructured":"Hirschfeldt, D., Jockusch, C., Kjos-Hanssen, B., Lempp, S., Slaman, T.: The strength of some combinatorial principles related to Ramsey\u2019s theorem for pairs. In: Computational Prospects of Infinity, Singapore, pp. 143\u2013161 (2008). Chap. 8","DOI":"10.1142\/9789812796554_0008"},{"key":"958_CR23","doi-asserted-by":"crossref","unstructured":"Birns, S., Kjos-Hanssen, B.: On the degrees of constructively immune sets. In: Connecting with Computability - 17th Conference on Computability in Europe (CiE 2021), Proceedings. LNCS, vol. 12813, pp. 50\u201359. Springer, Berlin-Heidelberg, Germany (2021)","DOI":"10.1007\/978-3-030-80049-9_5"},{"key":"958_CR24","doi-asserted-by":"crossref","DOI":"10.1201\/b18519","volume-title":"Introduction to Mathematical Logic","author":"E Mendelson","year":"2015","unstructured":"Mendelson, E.: Introduction to Mathematical Logic, 6th edn. Chapman & Hall, London (2015)","edition":"6"},{"key":"958_CR25","volume-title":"Intuitionism: An Introduction","author":"A Heyting","year":"1971","unstructured":"Heyting, A.: Intuitionism: An Introduction, 3rd edn. North-Holland, Amsterdam (1971)","edition":"3"},{"key":"958_CR26","unstructured":"Brouwer-Heyting-Kolmogorov interpretation. en.wikipedia.org\/wiki\/Brouwer-Heyting-Kolmogorov_interpretation"},{"key":"958_CR27","unstructured":"Realizability. en.wikipedia.org\/wiki\/Realizability"},{"key":"958_CR28","series-title":"Lecture Notes In Computer Science","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/978-3-642-39053-1_6","volume-title":"The Nature of Computation - Ninth Conference of Computability in Europe (CiE 2013), Proceedings","author":"J Case","year":"2013","unstructured":"Case, J., Ralston, M.: Beyond Rogers\u2019 non-constructively computable function. In: Bonizzoni, P., Brattka, V., L\u00f6we, B. (eds.) The Nature of Computation - Ninth Conference of Computability in Europe (CiE 2013), Proceedings. Lecture Notes In Computer Science, vol. 7921, pp. 45\u201354. Springer, Berlin (2013)"},{"key":"958_CR29","first-page":"211","volume":"102","author":"Y Medvedev","year":"1955","unstructured":"Medvedev, Y.: On non-isomorphic recursively enumerable sets. Dokl. Akad. Nauk SSSR 102, 211\u2013214 (1955)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"958_CR30","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1090\/S0002-9947-1956-0083454-0","volume":"74","author":"HG Rice","year":"1956","unstructured":"Rice, H.G.: Recursive and recursively enumerable orders. Trans. Am. Math. Soc. 74, 277\u2013300 (1956)","journal-title":"Trans. Am. Math. Soc."},{"key":"958_CR31","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1002\/malq.19570031202","volume":"3","author":"V Uspenskii","year":"1957","unstructured":"Uspenskii, V.: Some remarks on re sets. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 3, 157\u2013170 (1957)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"958_CR32","first-page":"302","volume":"38","author":"M Arslanov","year":"1985","unstructured":"Arslanov, M.: Effectively hyperimmune sets and majorants. Matematicheskie Zametki 38, 302\u2013309 (1985)","journal-title":"Matematicheskie Zametki"},{"key":"958_CR33","first-page":"143","volume":"8","author":"M Arslanov","year":"1969","unstructured":"Arslanov, M.: On effectively hypersimple sets. Algebra I Logic 8, 143\u2013153 (1969)","journal-title":"Algebra I Logic"},{"key":"958_CR34","doi-asserted-by":"crossref","first-page":"273","DOI":"10.2307\/2271305","volume":"28","author":"DA Martin","year":"1963","unstructured":"Martin, D.A.: A theorem on hyperhypersimple sets. J. Symb. Log. 28, 273\u2013278 (1963)","journal-title":"J. Symb. Log."},{"key":"958_CR35","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1002\/malq.19660120125","volume":"12","author":"DA Martin","year":"1966","unstructured":"Martin, D.A.: Classes of recursively enumerable sets and degrees of unsolvability. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 12, 295\u2013310 (1966)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"958_CR36","doi-asserted-by":"crossref","first-page":"162","DOI":"10.2307\/2271653","volume":"32","author":"RW Robinson","year":"1967","unstructured":"Robinson, R.W.: Simplicity of recursively enumerable sets. J. Symbol Logic 32, 162\u2013172 (1967)","journal-title":"J. Symbol Logic"},{"key":"958_CR37","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1002\/malq.19780241303","volume":"24","author":"R Daley","year":"1978","unstructured":"Daley, R.: On the simplicity of busy beaver sets. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 24, 207\u2013224 (1978)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"958_CR38","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1002\/malq.19680142505","volume":"14","author":"M Pour-El","year":"1968","unstructured":"Pour-El, M.: Independent axiomatization and its relation to the hypersimple set. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 14, 449\u2013456 (1968)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"958_CR39","first-page":"109","volume":"22","author":"G Kreisel","year":"1957","unstructured":"Kreisel, G.: Independent recursive axiomatizability. J. Symb. Log. 22, 109 (1957)","journal-title":"J. Symb. Log."},{"key":"958_CR40","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1006\/jcss.1996.0047","volume":"53","author":"G Baliga","year":"1996","unstructured":"Baliga, G., Case, J.: Learnability: Admissible, co-finite, and hypersimple sets. J. Comput. Syst. Sci. 53, 26\u201332 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"958_CR41","doi-asserted-by":"crossref","unstructured":"Joseph, D., Young, P.: Independence results in computer science. J. Comput Syst Sci, 205\u2013222 (1981)","DOI":"10.1016\/0022-0000(81)90013-1"},{"key":"958_CR42","unstructured":"Brouwer, L.E.J.: In: van Dalen, D. (ed.) Brouwer\u2019s Cambridge Lectures on Intuitionism. Cambridge University Press (1981)"},{"key":"958_CR43","unstructured":"Bauer, A.: Constructive gem: irrational to the power of irrational that is rational. math.andrej.com\/2009\/ (2009)"},{"key":"958_CR44","doi-asserted-by":"crossref","unstructured":"Case, J., Ralston, M., Akama, Y.: A non-uniformly c-productive sequence & non-constructive disjunctions. In: Zhao, X., Feng, Q., Kim, B., Yu, L. (eds.) Proceedings of the 13th Asian Logic Conference, pp. 29\u201352. World Scientific, Singapore (2015)","DOI":"10.1142\/9789814678001_0002"},{"key":"958_CR45","doi-asserted-by":"crossref","unstructured":"Akama, Y., Berardi, S., Hayashi, S., Kohlenbach, U.: An arithmetical hierarchy of the law of excluded middle and related principles. 19th annual symposium on logic in computer science (LICS\u201904), 192\u2013201 (2004)","DOI":"10.1109\/LICS.2004.1319613"},{"key":"958_CR46","doi-asserted-by":"crossref","unstructured":"Case, J.: Effectivizing inseparability. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 37, 97\u2013111 (1991). www.eecis.udel.edu\/~case\/papers\/mkdelta.pdf","DOI":"10.1002\/malq.19910370702"},{"key":"958_CR47","doi-asserted-by":"crossref","unstructured":"Smullyan, R.: Theory of formal systems. Annals of Mathematics Studies No. 47 (1961)","DOI":"10.1515\/9781400882007"},{"key":"958_CR48","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0019-9958(67)90546-3","volume":"11","author":"M Blum","year":"1967","unstructured":"Blum, M.: On the size of machines. Inf. Control 11, 257\u2013265 (1967)","journal-title":"Inf. Control"},{"key":"958_CR49","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/S0019-9958(72)90592-X","volume":"21","author":"A Meyer","year":"1972","unstructured":"Meyer, A.: Program size in restricted programming languages. Inf. Control 21, 382\u2013394 (1972)","journal-title":"Inf. Control"},{"key":"958_CR50","unstructured":"Bagchi, A.: Topics in complexity theory and recursion theory. PhD thesis, MIT (1972)"},{"key":"958_CR51","doi-asserted-by":"crossref","unstructured":"Meyer, A., Bagchi, A.: Program size and economy of description. In: symposium on the theory of computation (1972)","DOI":"10.1145\/800152.804912"},{"key":"958_CR52","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/malq.19770231303","volume":"23","author":"J Kinber","year":"1977","unstructured":"Kinber, J.: On btt-degrees of sets of minimal numbers in G\u00f6del numberings. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 23, 201\u2013212 (1977)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"958_CR53","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/s001530050112","volume":"18","author":"M Schaefer","year":"1998","unstructured":"Schaefer, M.: A guided tour of minimal indices and shortest descriptions. Arch Math Logic 18, 521\u2013548 (1998)","journal-title":"Arch Math Logic"},{"key":"958_CR54","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1016\/0022-0000(86)90035-8","volume":"32","author":"J Owings","year":"1986","unstructured":"Owings, J.: Effective choice functions and index sets. J. Comput. Syst. Sci. 32, 370\u2013373 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"958_CR55","volume-title":"Subsystems of Second Order Arithmetic","author":"S Simpson","year":"2010","unstructured":"Simpson, S.: Subsystems of Second Order Arithmetic, 2nd edn. Cambridge University Press, Cambridge (2010)","edition":"2"},{"key":"958_CR56","first-page":"107","volume":"49","author":"F Stephan","year":"2008","unstructured":"Stephan, F., Teutsch, J.: Immunity and hyperimmunity for sets of minimal indices. Notre Dame J Form Logic 49, 107\u2013125 (2008)","journal-title":"Notre Dame J Form Logic"},{"key":"958_CR57","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-49820-1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M Li","year":"2008","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, New York, NY (2008)","edition":"3"},{"key":"958_CR58","unstructured":"Royer, J., Case, J.: Subrecursive programming systems: complexity and succinctness. Research monograph in Progress in theoretical computer science. Birkh\u00e4user, Boston (1994). See www.eecis.udel.edu\/~case\/RC94Errata.pdf for corrections"},{"key":"958_CR59","unstructured":"Cilibrasia, R., Vit\u00e1nyi, P.: Fast whole-genome phylogeny by compression: the COVID-19 case. Proceedings of the National Academy of Sciences of the United States of America, 1\u20137 (To appear)"},{"key":"958_CR60","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S1571-0661(04)80877-6","volume":"42","author":"A Arslanov","year":"2001","unstructured":"Arslanov, A.: On elementary computability-theoretic properties of algorithmic randomness. Electron Notes Theoret Comput Sci 42, 41\u201351 (2001)","journal-title":"Electron Notes Theoret Comput Sci"},{"key":"958_CR61","doi-asserted-by":"crossref","unstructured":"Kummer, M.: On the complexity of random strings. In: Proceedings of the symposium on theoretical aspects of computer science (STACS\u201996). Lecture Notes in Computer Science, vol. 1845, pp. 25\u201336. Springer, Berlin (1996)","DOI":"10.1007\/3-540-60922-9_3"},{"key":"958_CR62","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1006\/jcss.1996.0067","volume":"8","author":"H Buhrman","year":"1996","unstructured":"Buhrman, H., Orponen, P.: Random strings make hard instances. J. Comput. Syst. Sci. 8, 261\u2013266 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"958_CR63","unstructured":"Royer, J.: The Set of Kolmogorov Random Strings is Strongly Effectively Immune. www.cis.syr.edu\/~royer\/seimmune.pdf (2020)"},{"key":"958_CR64","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1002\/j.1538-7305.1962.tb00480.x","volume":"41","author":"T Rado","year":"1962","unstructured":"Rado, T.: On non-computable functions. Bell Syst Tech J 41, 877\u2013884 (1962)","journal-title":"Bell Syst Tech J"},{"issue":"4","key":"958_CR65","doi-asserted-by":"crossref","first-page":"297","DOI":"10.25088\/ComplexSystems.25.4.297","volume":"25","author":"A Yedidia","year":"2016","unstructured":"Yedidia, A., Aaronson, S.: A relatively small Turing machine whose behavior is independent of set theory. Complex Syst 25(4), 297\u2013327 (2016)","journal-title":"Complex Syst"},{"key":"958_CR66","unstructured":"Busy Beaver. en.wikipedia.org\/wiki\/Busy_beaver"},{"key":"958_CR67","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M Blum","year":"1967","unstructured":"Blum, M.: A machine independent theory of the complexity of recursive functions. J. ACM 14, 322\u2013336 (1967)","journal-title":"J. ACM"},{"key":"958_CR68","doi-asserted-by":"crossref","first-page":"468","DOI":"10.2307\/2273749","volume":"46","author":"R Daley","year":"1981","unstructured":"Daley, R.: Busy beaver sets and the degrees of unsolvability. J. Symb. Log. 46, 468\u2013474 (1981)","journal-title":"J. Symb. Log."},{"key":"958_CR69","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/S0019-9958(82)80085-5","volume":"52","author":"R Daley","year":"1981","unstructured":"Daley, R.: Busy beaver sets: characterizations and applications. Inf. Control 52, 52\u201367 (1981)","journal-title":"Inf. Control"},{"key":"958_CR70","doi-asserted-by":"crossref","first-page":"357","DOI":"10.4153\/CJM-1958-035-x","volume":"10","author":"J Dekker","year":"1958","unstructured":"Dekker, J., Myhill, J.: Retraceable sets. Can. J. Math. 10, 357\u2013373 (1958)","journal-title":"Can. J. Math."},{"key":"958_CR71","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1002\/malq.19620080313","volume":"8","author":"CEM Yates","year":"1962","unstructured":"Yates, C.E.M.: Recursively enumerable sets and retracing functions. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 8, 331\u2013345 (1962)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"issue":"3","key":"958_CR72","first-page":"450","volume":"19","author":"P Cohen","year":"1975","unstructured":"Cohen, P., Jockusch, C.: A lattice property of Post\u2019s simple set. Ill. J. Math. 19(3), 450\u2013453 (1975)","journal-title":"Ill. J. Math."},{"key":"958_CR73","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF01361115","volume":"127","author":"W Markwald","year":"1954","unstructured":"Markwald, W.: Zur theorie der konstruktiven wohlordnugen. Math. Ann. 127, 35\u2013149 (1954)","journal-title":"Math. Ann."},{"key":"958_CR74","doi-asserted-by":"crossref","first-page":"30","DOI":"10.2307\/2266324","volume":"18","author":"W Craig","year":"1953","unstructured":"Craig, W.: On axiomatizability within a system. J. Symb. Log. 18, 30\u201332 (1953)","journal-title":"J. Symb. Log."},{"key":"958_CR75","doi-asserted-by":"crossref","first-page":"644","DOI":"10.2307\/1970028","volume":"69","author":"J Shoenfield","year":"1959","unstructured":"Shoenfield, J.: On degrees of unsolvability. Ann. Math. 69, 644\u2013653 (1959)","journal-title":"Ann. Math."},{"key":"958_CR76","doi-asserted-by":"crossref","unstructured":"Shapiro, N.: Review of \u201cLimiting recursion\u201d by E.M. Gold and \u201cTrial and error predicates and the solution to a problem of Mostowski\u201d by H. Putnam. Journal of Symbolic Logic 36, 342 (1971)","DOI":"10.2307\/2270310"},{"key":"958_CR77","unstructured":"Matijasevic\u0306, Y.: Enumerable sets are diophantine. Soviet Mathematics. Doklady 11(2), 354\u2013358 (1970). Reprinted with an addendum as a book chapter in [82]"},{"key":"958_CR78","doi-asserted-by":"crossref","first-page":"335","DOI":"10.2307\/2272832","volume":"43","author":"J Jones","year":"1978","unstructured":"Jones, J.: Three universal representations of recursively enumerable sets. J. Symb. Log. 43, 335\u2013351 (1978)","journal-title":"J. Symb. Log."},{"key":"958_CR79","doi-asserted-by":"crossref","first-page":"549","DOI":"10.2307\/2273588","volume":"47","author":"J Jones","year":"1982","unstructured":"Jones, J.: Universal diophantine equation. J. Symb. Log. 47, 549\u2013571 (1982)","journal-title":"J. Symb. Log."},{"key":"958_CR80","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/BF02414017","volume":"98","author":"R Magari","year":"1974","unstructured":"Magari, R.: Su certe teorie non enumerabili (Sulle Limitazioni dei sistemi formali, I). Annali di Matematica Pura ed Applicata 98, 119\u2013152 (1974)","journal-title":"Annali di Matematica Pura ed Applicata"},{"key":"958_CR81","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/BF00262039","volume":"4","author":"R Jeroslow","year":"1975","unstructured":"Jeroslow, R.: Experimental logics and $$\\Delta ^0_2$$-theories. J. Philos. Log. 4, 253\u2013266 (1975)","journal-title":"J. Philos. Log."},{"key":"958_CR82","doi-asserted-by":"crossref","DOI":"10.1142\/4800","volume-title":"Mathematical Logic in the 20th Century","author":"G Sacks","year":"2003","unstructured":"Sacks, G.: Mathematical Logic in the 20th Century. Singapore University Press and World Scientific, Singapore (2003)"}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-024-00958-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00153-024-00958-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-024-00958-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T11:05:39Z","timestamp":1751886339000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00153-024-00958-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,29]]},"references-count":82,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["958"],"URL":"https:\/\/doi.org\/10.1007\/s00153-024-00958-x","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"type":"print","value":"0933-5846"},{"type":"electronic","value":"1432-0665"}],"subject":[],"published":{"date-parts":[[2025,1,29]]},"assertion":[{"value":"3 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}