{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:56:36Z","timestamp":1757624196218,"version":"3.44.0"},"reference-count":41,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2023,9,20]],"date-time":"2023-09-20T00:00:00Z","timestamp":1695168000000},"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":[[2023,11,13]]},"abstract":"<jats:p> A compact set has computable type if any homeomorphic copy of the set which is semicomputable is actually computable. Miller proved that finite-dimensional spheres have computable type, Iljazovi\u0107 and other authors established the property for many other sets, such as manifolds. In this article we propose a theoretical study of the notion of computable type, in order to improve our general understanding of this notion and to provide tools to prove or disprove this property. <\/jats:p><jats:p> We first show that the definitions of computable type that were distinguished in the literature, involving metric spaces and Hausdorff spaces respectively, are actually equivalent. We argue that the stronger, relativized version of computable type, is better behaved and prone to topological analysis. We obtain characterizations of strong computable type, related to the descriptive complexity of topological invariants, as well as purely topological criteria. We study two families of topological invariants of low descriptive complexity, expressing the extensibility and the null-homotopy of continuous functions. We apply the theory to revisit previous results and obtain new ones. <\/jats:p>","DOI":"10.3233\/com-220430","type":"journal-article","created":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T12:15:32Z","timestamp":1695384932000},"page":"227-269","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":5,"title":["Strong computable type"],"prefix":"10.1177","volume":"12","author":[{"given":"Djamel Eddine","family":"Amir","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France"}]},{"given":"Mathieu","family":"Hoyrup","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France"}]}],"member":"179","published-online":{"date-parts":[[2023,9,20]]},"reference":[{"key":"ref001","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1947.0027"},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.111"},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2023.17"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.4064\/fm-19-1-220-242"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59234-9_11"},{"key":"ref006","doi-asserted-by":"crossref","unstructured":"G.E.\u00a0Bredon, J.H.\u00a0Ewing, F.W.\u00a0Gehring and P.R.\u00a0Halmos, Topology and Geometry, Graduate Texts in Mathematics, Springer, 1993. ISBN 9780387979267.","DOI":"10.1007\/978-1-4757-6848-0"},{"key":"ref007","doi-asserted-by":"crossref","unstructured":"K.\u00a0Burnik and Z.\u00a0Iljazovi\u0107, Computability of 1-manifolds, Log. Methods Comput. Sci. 10(2) (2014).","DOI":"10.2168\/LMCS-10(2:8)2014"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.1145\/2597629"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020-10017-6"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exab063"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-019-00667-w"},{"key":"ref012","unstructured":"P.\u00a0Collins, Computability of homology for compact absolute neighbourhood retracts, in: Sixth International Conference on Computability and Complexity in Analysis, CCA 2009, Ljubljana, Slovenia, August 18\u201322, 2009, A.\u00a0Bauer, P.\u00a0Hertling and K.\u00a0Ko, eds, OASICS, Vol.\u00a011, Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik, Germany, 2009."},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1017\/bsl.2023.16"},{"key":"ref014","unstructured":"R.\u00a0Engelking, General Topology. Rev. and Compl. ed., Vol.\u00a06, Rev. and compl. ed. edn, Heldermann Verlag, Berlin, 1989, viii + 529. ISBN 3-88538-006-4."},{"key":"ref015","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591376"},{"key":"ref016","unstructured":"A.\u00a0Hatcher, Algebraic Topology, Algebraic Topology, Cambridge University Press, 2002. ISBN 9780521795401."},{"key":"ref017","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310124"},{"key":"ref018","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2020.102823"},{"key":"ref019","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1948-0026325-3"},{"key":"ref020","doi-asserted-by":"crossref","unstructured":"W.\u00a0Hurewicz and H.\u00a0Wallman, Dimension Theory (PMS-4), Princeton University Press, 1941. http:\/\/www.jstor.org\/stable\/j.ctt183pk8v. ISBN 9780691627748.","DOI":"10.1515\/9781400875665"},{"issue":"6","key":"ref021","first-page":"1206","volume":"15","author":"Iljazovi\u0107 Z.","year":"2009","journal-title":"Journal of Universal Computer Science"},{"key":"ref022","doi-asserted-by":"crossref","unstructured":"Z.\u00a0Iljazovi\u0107, Co-c.e. spheres and cells in computable metric spaces, Logical Methods in Computer Science 7(3) (2011).","DOI":"10.2168\/LMCS-7(3:5)2011"},{"key":"ref023","doi-asserted-by":"crossref","unstructured":"Z.\u00a0Iljazovic, Compact manifolds with computable boundaries, Log. Methods Comput. Sci. 9(4) (2013).","DOI":"10.2168\/LMCS-9(4:19)2013"},{"key":"ref024","doi-asserted-by":"publisher","DOI":"10.1002\/malq.201900025"},{"key":"ref025","doi-asserted-by":"crossref","unstructured":"Z.\u00a0Iljazovi\u0107 and T.\u00a0Kihara, Computability of subsets of metric spaces, in: Handbook of Computability and Complexity in Analysis, V.\u00a0Brattka and P.\u00a0Hertling, eds, Springer, 2020.","DOI":"10.1007\/978-3-030-59234-9_2"},{"key":"ref026","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.11.004"},{"key":"ref027","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005086"},{"key":"ref028","doi-asserted-by":"crossref","unstructured":"A.S.\u00a0Kechris, Classical Descriptive Set Theory, Springer, 1995. ISBN 0387943749.","DOI":"10.1007\/978-1-4612-4190-4"},{"key":"ref029","doi-asserted-by":"publisher","DOI":"10.1017\/fms.2022.7"},{"key":"ref030","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2022.10.003"},{"key":"ref031","doi-asserted-by":"publisher","DOI":"10.4064\/fm-46-1-29-45"},{"key":"ref032","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)80384-0"},{"key":"ref033","doi-asserted-by":"crossref","unstructured":"Y.N.\u00a0Moschovakis, Descriptive Set Theory, 2nd edn, Mathematical Surveys and Monographs, American Mathematical Society, 2009. ISBN 9780821848135.","DOI":"10.1090\/surv\/155"},{"key":"ref034","doi-asserted-by":"publisher","DOI":"10.3233\/COM-150049"},{"key":"ref035","unstructured":"A.\u00a0Pauly, Weihrauch degrees of problems related to topological circles, 2021, Continuity, Computability, Constructivity (CCC)."},{"key":"ref036","unstructured":"M.\u00a0Schr\u00f6der, Effective metrization of regular spaces, in: Computability and Complexity in Analysis, Vol.\u00a0235, K.I.\u00a0Ko, A.\u00a0Nerode, M.B.\u00a0Pour-El, K.\u00a0Weihrauch and J.\u00a0Wiedermann, eds, Informatik Berichte, FernUniversit\u00e4t Hagen, 1998, pp.\u00a063\u201380."},{"key":"ref037","doi-asserted-by":"publisher","DOI":"10.1137\/0205037"},{"key":"ref038","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.07.053"},{"key":"ref039","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19710170139"},{"key":"ref040","unstructured":"J.\u00a0van Mill, The Infinite-Dimensional Topology of Function Spaces, North-Holland Mathematical Library, Elsevier Science, 2001. ISBN 9780444505576."},{"key":"ref041","doi-asserted-by":"publisher","DOI":"10.4064\/fm-82-3-269-294"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-220430","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-220430","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-220430","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T12:22:16Z","timestamp":1757420536000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-220430"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,20]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11,13]]}},"alternative-id":["10.3233\/COM-220430"],"URL":"https:\/\/doi.org\/10.3233\/com-220430","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"type":"print","value":"2211-3568"},{"type":"electronic","value":"2211-3576"}],"subject":[],"published":{"date-parts":[[2023,9,20]]}}}