{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:57:11Z","timestamp":1757624231379,"version":"3.44.0"},"reference-count":39,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T00:00:00Z","timestamp":1696204800000},"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":[[2024,3,20]]},"abstract":"<jats:p> We introduce the notion of eventually uniformly weak truth table array computable (e.u.wtt-a.c.) sets. As our main result, we show that a computably enumerable (c.e.) set has this property iff it is weak truth table ([Formula: see text]-) reducible to a maximal set. Moreover, in this equivalence we may replace maximal sets by quasi-maximal sets, hyperhypersimple sets or dense simple sets and we may replace [Formula: see text]-reducibility by identity-bounded Turing reducibility (or any intermediate reducibility). <\/jats:p><jats:p> Here, a set A is e.u.wtt-a.c. if there is an effective procedure which, for any given partial [Formula: see text]-functional [Formula: see text], yields a computable approximation [Formula: see text] of the domain of [Formula: see text] together with a computable indicator function [Formula: see text] and a computable order [Formula: see text] such that, once the indicator becomes positive, i.e., [Formula: see text], the number of the mind changes of the approximation g on x after stage s is bounded by [Formula: see text] where, for total [Formula: see text], the indicator eventually becomes positive on almost all arguments x of [Formula: see text]. <\/jats:p><jats:p> In addition to our main result, we show several properties of the computably enumerable e.u.wtt-a.c. sets. For instance, the class of these sets is closed downwards under [Formula: see text]-reductions and closed under join. Moreover, we relate this class to \u2013 and separate it from \u2013 well known classes in the literature. On the one hand, the class of the [Formula: see text]-degrees of the c.e. e.u.wtt-a.c. sets is strictly contained in the class of the array computable c.e. [Formula: see text]-degrees. On the other hand, every bounded low set is e.u.wtt-a.c. but there are e.u.wtt-a.c. c.e. sets which are not bounded low. Here a set A is bounded low if [Formula: see text], i.e., if [Formula: see text] is \u03c9-c.a., where [Formula: see text] is the [Formula: see text]-jump of A (Anderson, Csima and Lange ( Archive for Mathematical Logic 56(5\u20136) ( 2017 ) 507\u2013521)). <\/jats:p><jats:p> Finally, we prove that there is a strict hierarchy within the class of the bounded low c.e. sets A depending on the order h that bounds the number of mind changes of a computable approximation of [Formula: see text], and we show that there exists a Turing complete set A such that [Formula: see text] is h-c.a. for any computable order h with [Formula: see text]. <\/jats:p>","DOI":"10.3233\/com-220432","type":"journal-article","created":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T11:42:20Z","timestamp":1696333340000},"page":"1-56","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Lowness properties for strong reducibilities and the computational power of maximal sets"],"prefix":"10.1177","volume":"13","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[{"name":"University of Heidelberg, Department of Mathematics and Computer Science, Im Neuenheimer Feld 205, D-69120 Heidelberg, Germany"}]},{"given":"Rod","family":"Downey","sequence":"additional","affiliation":[{"name":"Victoria University, School of Mathematics and Statistics, P.O. Box 600, Wellington, New Zealand"}]},{"given":"Martin","family":"Monath","sequence":"additional","affiliation":[{"name":"University of Heidelberg, Department of Mathematics and Computer Science, Im Neuenheimer Feld 205, D-69120 Heidelberg, Germany"}]}],"member":"179","published-online":{"date-parts":[[2023,10,2]]},"reference":[{"doi-asserted-by":"publisher","key":"ref001","DOI":"10.1007\/978-3-319-94418-0_3"},{"unstructured":"K.\u00a0Ambos-Spies, R.\u00a0Downey and M.\u00a0Monath, Some notes on the wtt-jump, Proceedings of the Asian Logic Meeting, (in press).","key":"ref002"},{"doi-asserted-by":"publisher","key":"ref003","DOI":"10.1215\/00294527-2420660"},{"doi-asserted-by":"publisher","key":"ref004","DOI":"10.1007\/s00153-017-0537-8"},{"doi-asserted-by":"publisher","key":"ref005","DOI":"10.1090\/S0002-9947-09-04910-1"},{"doi-asserted-by":"publisher","key":"ref006","DOI":"10.1016\/j.jcss.2015.05.001"},{"doi-asserted-by":"crossref","unstructured":"P.\u00a0Cholak, R.\u00a0Coles, R.\u00a0Downey and E.\u00a0Herrmann, Automorphisms of the lattice of \u03c001 classes: Perfect thin classes and anr degrees, Transactions of the American Mathematical Society 353 (2001), 4988\u20134924.","key":"ref007","DOI":"10.1090\/S0002-9947-01-02821-5"},{"doi-asserted-by":"publisher","key":"ref008","DOI":"10.1090\/S0002-9947-1992-1097164-6"},{"unstructured":"R.\u00a0Coles, R.\u00a0Downey and G.\u00a0LaForte, Notes on wtt-jump and ordinal notations, 1998, Unpublished Manuscript.","key":"ref009"},{"doi-asserted-by":"publisher","key":"ref010","DOI":"10.2178\/jsl\/1318338849"},{"doi-asserted-by":"publisher","key":"ref011","DOI":"10.1002\/malq.19660120125"},{"doi-asserted-by":"publisher","key":"ref012","DOI":"10.1016\/j.ipl.2008.05.028"},{"doi-asserted-by":"crossref","unstructured":"R.\u00a0Downey and N.\u00a0Greenberg, A Hierarchy of Turing Degrees: A Transfinite Hierarchy of Lowness Notions in the Computably Enumerable Degrees, Unifying Classes, and Natural Definability, Annals of Mathematics, Studies, Princeton University Press, 2020.","key":"ref013","DOI":"10.23943\/princeton\/9780691199665.001.0001"},{"doi-asserted-by":"crossref","unstructured":"R.\u00a0Downey and D.R.\u00a0Hirschfeldt, Algorithmic Randomness and Complexity, Springer, New York, 2010.","key":"ref014","DOI":"10.1007\/978-0-387-68441-3"},{"doi-asserted-by":"publisher","key":"ref015","DOI":"10.1007\/BFb0086116"},{"doi-asserted-by":"crossref","unstructured":"R.\u00a0Downey, C.\u00a0Jockusch and M.\u00a0Stob, Array nonrecursive degrees and genericity, in: Computability, Enumerability, Unsolvability, London Math. Soc. Lecture Note Ser., Vol.\u00a0224, Cambridge Univ. Press, Cambridge, 1996, pp.\u00a093\u2013104.","key":"ref016","DOI":"10.1017\/CBO9780511629167.005"},{"doi-asserted-by":"publisher","key":"ref017","DOI":"10.1090\/S0002-9947-1987-0879565-X"},{"issue":"1","key":"ref018","first-page":"34","volume":"9","author":"Ershov Y.L.","year":"1970","journal-title":"Algebra i Logika"},{"doi-asserted-by":"publisher","key":"ref019","DOI":"10.2307\/2964290"},{"doi-asserted-by":"publisher","key":"ref020","DOI":"10.1002\/malq.19590050703"},{"doi-asserted-by":"publisher","key":"ref021","DOI":"10.1073\/pnas.43.2.236"},{"issue":"2","key":"ref022","first-page":"765","volume":"16","author":"Gerla G.","year":"1979","journal-title":"Unione Matematica Italiana. Bollettino. B. Serie V"},{"doi-asserted-by":"publisher","key":"ref023","DOI":"10.1016\/S0019-9958(67)91165-5"},{"doi-asserted-by":"publisher","key":"ref024","DOI":"10.1017\/bsl.2017.38"},{"doi-asserted-by":"publisher","key":"ref025","DOI":"10.1073\/pnas.88.22.10242"},{"doi-asserted-by":"publisher","key":"ref026","DOI":"10.1137\/S0097539794268789"},{"unstructured":"M.\u00a0Lerman, Degrees of Unsolvability, Springer-Verlag, 1985.","key":"ref027"},{"key":"ref028","first-page":"194","volume":"108","author":"Mu\u010dnik A.A.","year":"1956","journal-title":"Doklady Akademii Nauk SSSR"},{"doi-asserted-by":"crossref","unstructured":"A.\u00a0Nies, Reals which compute little, in: Logic Colloquium \u201902, Lecture Notes in Logic, Vol.\u00a027, Assoc. Symbol. Logic, La Jolla, CA, 2006, pp.\u00a0261\u2013275.","key":"ref029","DOI":"10.1017\/9781316755723.012"},{"doi-asserted-by":"publisher","key":"ref030","DOI":"10.2178\/jsl\/1120224726"},{"unstructured":"P.\u00a0Odifreddi, Classical Recursion Theory, Vol. II, North-Holland, 1999.","key":"ref031"},{"doi-asserted-by":"publisher","key":"ref032","DOI":"10.1090\/S0002-9904-1944-08111-1"},{"doi-asserted-by":"publisher","key":"ref033","DOI":"10.2307\/2271653"},{"doi-asserted-by":"publisher","key":"ref034","DOI":"10.2307\/1970842"},{"doi-asserted-by":"crossref","unstructured":"R.I.\u00a0Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin, 1987.","key":"ref035","DOI":"10.1007\/978-3-662-02460-7"},{"key":"ref036","first-page":"608","volume":"8","author":"Tennenbaum S.","year":"1961","journal-title":"Notices Amer. Math. Soc"},{"doi-asserted-by":"publisher","key":"ref037","DOI":"10.2307\/2695101"},{"doi-asserted-by":"crossref","unstructured":"G.\u00a0Wu and H.\u00a0Wu, Bounded jump and the high\/low hierarchy, in: Theory and Applications of Models of Computation, Lecture Notes in Comput. Sci., Vol.\u00a011436, Springer, 2019, pp.\u00a0647\u2013658.","key":"ref038","DOI":"10.1007\/978-3-030-14812-6_40"},{"doi-asserted-by":"publisher","key":"ref039","DOI":"10.1215\/S0012-7094-65-03247-3"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-220432","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-220432","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-220432","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T12:22:18Z","timestamp":1757420538000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-220432"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,2]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,20]]}},"alternative-id":["10.3233\/COM-220432"],"URL":"https:\/\/doi.org\/10.3233\/com-220432","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"type":"print","value":"2211-3568"},{"type":"electronic","value":"2211-3576"}],"subject":[],"published":{"date-parts":[[2023,10,2]]}}}