{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:10Z","timestamp":1777516750126,"version":"3.51.4"},"reference-count":34,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2016,7,13]],"date-time":"2016-07-13T00:00:00Z","timestamp":1468368000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2017,8,7]]},"abstract":"<jats:p>By a theorem of Sacks, if a real x is recursive relative to all elements of a set of positive Lebesgue measure, x is recursive. This statement, and the analogous statement for non-meagerness instead of positive Lebesgue measure, have been shown to carry over to many models of transfinite computations in: Notre Dame Journal of Formal Logic, to appear, arXiv:1307.0160 [math.LO]. Here, we start exploring another analogue concerning recognizability rather than computability. For a notion of relativized recognizability (introduced in: Annals of Pure and Applied Logic 165(9) (2014), 1353\u20131532, for ITRMs and generalized here to various other machine types), we show that, for Infinite Time Turing Machines (ITTMs), if a real x is recognizable relative to all elements of a non-meager Borel set Y, then x is recognizable. We also show that a relativized version of this statement holds for Infinite Time Register Machines (ITRMs). This extends our work in: Evolving Computability: 11th Conference on Computability in Europe, 2015, pp.\u00a0137\u2013145, where we obtained the (unrelativized) result for ITRMs. We then introduce a jump operator for recognizability, examine its set-theoretical content and show that the recognizable jumps for ITRMs and ITTMs are primitive-recursively equivalent, even though these two models are otherwise of vastly different strength. Finally, we introduce degrees of recognizability by considering the transitive closure of relativized recognizability and connect it with the recognizable jump operator to obtain a solution to Post\u2019s problem for degrees of recognizability.<\/jats:p>","DOI":"10.3233\/com-160061","type":"journal-article","created":{"date-parts":[[2016,7,15]],"date-time":"2016-07-15T12:23:08Z","timestamp":1468585388000},"page":"223-247","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["Infinite time recognizability from generic oracles and the recognizable jump operator"],"prefix":"10.1177","volume":"6","author":[{"given":"Merlin","family":"Carl","sequence":"first","affiliation":[{"name":"Fachbereich f\u00fcr Mathematik und Statistik, Universit\u00e4t Konstanz, Konstanz, Germany. ."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2016,7,13]]},"reference":[{"key":"ref001","doi-asserted-by":"crossref","unstructured":"G.\u00a0Barmpalias and A.\u00a0Lewis-Pye, The information content of typical reals, in: Turing\u2019s Ideas\u00a0\u2013 Their Significance and Impact, G.\u00a0Sommaruga and T.\u00a0Strahm, eds, Springer, Basel, 2014.","DOI":"10.1007\/978-3-319-22156-4_8"},{"key":"ref002","doi-asserted-by":"crossref","unstructured":"T.\u00a0Bartoszynski and H.\u00a0Judah, Set Theory: On the Structure of the Real Line A, K. Peters Ltd, 1995.","DOI":"10.1201\/9781439863466"},{"key":"ref003","doi-asserted-by":"crossref","unstructured":"J.\u00a0Barwise, Admissible Sets and Structures, Springer, Heidelberg, 1975. doi:10.1007\/978-3-662-11035-5.","DOI":"10.1007\/978-3-662-11035-5"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.2307\/2271357"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2015.8"},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.3233\/COM-160055"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2014.04.010"},{"key":"ref008","doi-asserted-by":"crossref","unstructured":"M.\u00a0Carl, ITRM-recognizability from random oracles, in: Evolving Computability: 11th Conference on Computability in Europe, A.\u00a0Beckmann et al., eds, Lecture Notes in Computer Science, Vol.\u00a09136, 2015, pp.\u00a0137\u2013145.","DOI":"10.1007\/978-3-319-20028-6_14"},{"key":"ref009","unstructured":"M.\u00a0Carl, The lost melody phenomenon, in: Infinity, Computability, and Metamathematics: Festschrift Celebrating the 60th Birthdays of Peter Koepke and Philip Welch, S.\u00a0Geschke et al., eds, pp.\u00a049\u201370."},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-009-0167-x"},{"key":"ref011","unstructured":"M.\u00a0Carl and P.\u00a0Schlicht, Infinite computations with random oracles,\n                      Notre Dame Journal of Formal Logic\n                      , to appear, Preprint available at: arXiv:1307.0160 [math.LO]."},{"key":"ref012","unstructured":"M.\u00a0Carl, P.\u00a0Schlicht and P.\u00a0Welch, Recognizable sets and Woodin cardinals: Computation beyond the constructible universe, Preprint, submitted, available at: http:\/\/arxiv.org\/pdf\/1512.06101.pdf."},{"key":"ref013","doi-asserted-by":"crossref","unstructured":"N.\u00a0Cutland, Computability\u00a0\u2013 An Introduction to Recursive Function Theory, Cambridge University Press, 1980.","DOI":"10.1017\/CBO9781139171496"},{"key":"ref014","doi-asserted-by":"crossref","unstructured":"R.G.\u00a0Downey and D.\u00a0Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer LLC, 2010.","DOI":"10.1007\/978-0-387-68441-3"},{"key":"ref015","unstructured":"C.W.\u00a0Gray, Iterated forcing from the strategic point of view, PhD thesis, University of California, Berkeley, California, 1980."},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.2307\/2586556"},{"key":"ref017","unstructured":"T.\u00a0Jech, Set Theory, 3rd Millenium edn, revised and expanded, Springer Monographs in Mathematics, Springer, 2002."},{"key":"ref018","doi-asserted-by":"crossref","unstructured":"R.\u00a0Jensen and C.\u00a0Karp, Primitive recursive set functions, in: Axiomatic Set Theory, Proc. Sympos. Pure Math., Vol.\u00a0XIII, Part I, Amer. Math. Soc., Providence, RI, 1971, pp.\u00a0143\u2013176.","DOI":"10.1090\/pspum\/013.1\/0281602"},{"key":"ref019","unstructured":"A.\u00a0Kanamori, The Higher Infinite, Springer, Berlin, 2005."},{"key":"ref020","doi-asserted-by":"crossref","unstructured":"P.\u00a0Koepke, Turing computations on ordinals,\n                      The Bulletin of Symbolic Logic\n                      11\n                      (3) (2005). doi:10.2178\/bsl\/1122038993.","DOI":"10.2178\/bsl\/1122038993"},{"key":"ref021","doi-asserted-by":"crossref","unstructured":"P.\u00a0Koepke, Infinite time register machines, in: Logical Approaches to Computational Barriers, A.\u00a0Beckmann et al., eds, Lecture Notes in Computer Science, Vol.\u00a03988, 2006, pp.\u00a0257\u2013266. doi:10.1007\/11780342_27.","DOI":"10.1007\/11780342_27"},{"key":"ref022","doi-asserted-by":"crossref","unstructured":"P.\u00a0Koepke, Ordinal computability, in: Mathematical Theory and Computational Practice, K.\u00a0Ambos-Spies et al., eds, Lecture Notes in Computer Science, Vol.\u00a05635, 2009, pp.\u00a0280\u2013289. doi:10.1007\/978-3-642-03073-4_29.","DOI":"10.1007\/978-3-642-03073-4_29"},{"key":"ref023","doi-asserted-by":"crossref","unstructured":"P.\u00a0Koepke and R.\u00a0Miller, An enhanced theory of infinite time register machines, in: Logic and Theory of Algorithms, A.\u00a0Beckmann et al., eds, Lecture Notes in Computer Science, Vol.\u00a05028, 2008, pp.\u00a0306\u2013315. doi:10.1007\/978-3-540-69407-6_34.","DOI":"10.1007\/978-3-540-69407-6_34"},{"key":"ref024","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2009.01.005"},{"key":"ref025","unstructured":"K.\u00a0Kunen, Set Theory. An Introduction to Independence Proofs, Elsevier, 2006."},{"key":"ref026","doi-asserted-by":"publisher","DOI":"10.1007\/s001530100092"},{"key":"ref027","unstructured":"A.R.D.\u00a0Mathias, Provident sets and rudimentary set forcing, Preprint, available at: https:\/\/www.dpmms.cam.ac.uk\/~ardm\/fifofields3.pdf."},{"key":"ref028","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2014.04.016"},{"key":"ref029","doi-asserted-by":"crossref","unstructured":"G.\u00a0Sacks, Higher Recursion Theory, Springer, Heidelberg, 1990. doi:10.1007\/978-3-662-12013-2.","DOI":"10.1007\/978-3-662-12013-2"},{"key":"ref030","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdl015"},{"key":"ref031","doi-asserted-by":"crossref","unstructured":"R.\u00a0Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets. Perspectives in Mathematical Logic, Springer, Heidelberg, 1987.","DOI":"10.1007\/978-3-662-02460-7"},{"key":"ref032","doi-asserted-by":"crossref","unstructured":"P.\u00a0Welch, Minimality arguments for infinite time Turing degrees, in: Sets and Proofs, S.B.\u00a0Cooper and J.K.\u00a0Truss, eds, London Mathematical Society Lecture Note Series, Vol.\u00a0258, 1999, pp.\u00a0425\u2013436.","DOI":"10.1017\/CBO9781107325944.018"},{"key":"ref033","doi-asserted-by":"publisher","DOI":"10.2307\/2586695"},{"key":"ref034","doi-asserted-by":"crossref","unstructured":"P.\u00a0Welch, Discrete transfinite computation, in: Turing\u2019s Ideas\u00a0\u2013 Their Significance and Impact, G.\u00a0Sommaruga and T.\u00a0Strahm, eds, Springer, Basel, 2014.","DOI":"10.1007\/978-3-319-22156-4_6"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-160061","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-160061","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-160061","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:59:53Z","timestamp":1777391993000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-160061"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,13]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,7]]}},"alternative-id":["10.3233\/COM-160061"],"URL":"https:\/\/doi.org\/10.3233\/com-160061","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,13]]}}}