{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:57:41Z","timestamp":1747173461614,"version":"3.40.5"},"reference-count":50,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T00:00:00Z","timestamp":1717027200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Computability on uncountable sets has no standard formalization, unlike that on countable sets, which is given by Turing machines. Some of the approaches to define computability in these sets rely on order-theoretic structures to translate such notions from Turing machines to uncountable spaces. Since these machines are used as a baseline for computability in these approaches, countability restrictions on the ordered structures are fundamental. Here, we show several relations between the usual countability restrictions in order-theoretic theories of computability and some more common order-theoretic countability constraints, like order density properties and functional characterizations of the order structure in terms of multi-utilities. As a result, we show how computability can be introduced in some order structures via countability order density and multi-utility constraints.<\/jats:p>","DOI":"10.1017\/s0960129524000173","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:16:29Z","timestamp":1717060589000},"page":"491-528","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Countability constraints in order-theoretic approaches to computability"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8176-0591","authenticated-orcid":false,"given":"Pedro","family":"Hack","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel A.","family":"Braun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Gottwald","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"S0960129524000173_ref19","unstructured":"Hack, P. , Braun, D. A. and Gottwald, S. . (2022a). Computation as uncertainty reduction: a simplified order-theoretic framework. arXiv preprint arXiv: 2206.13885."},{"key":"S0960129524000173_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s11238-022-09904-w"},{"volume-title":"Theory of Recursive Functions and Effective Computability","year":"1987","author":"Rogers","key":"S0960129524000173_ref39"},{"key":"S0960129524000173_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90208-7"},{"key":"S0960129524000173_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-8641(97)00222-8"},{"key":"S0960129524000173_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s11238-021-09861-w"},{"key":"S0960129524000173_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02219096"},{"key":"S0960129524000173_ref43","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0036946"},{"key":"S0960129524000173_ref34","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972700004597"},{"key":"S0960129524000173_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/S0370-1573(98)00082-9"},{"volume-title":"A Compendium of Continuous Lattices","year":"2012","author":"Gierz","key":"S0960129524000173_ref16"},{"key":"S0960129524000173_ref10","first-page":"159","article-title":"Representation of a preference ordering by a numerical function","volume":"3","author":"Debreu","year":"1954","journal-title":"Decision Processes"},{"key":"S0960129524000173_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68546-5_2"},{"key":"S0960129524000173_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00097-8"},{"volume-title":"A Foundation for Computation","year":"2000","author":"Martin","key":"S0960129524000173_ref32"},{"key":"S0960129524000173_ref37","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.2001.2814"},{"key":"S0960129524000173_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-8641(97)00152-1"},{"key":"S0960129524000173_ref7","volume-title":"Representations of Preferences Orderings","volume":"422","author":"Bridges","year":"2013"},{"key":"S0960129524000173_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(99)80030-5"},{"volume-title":"Computable Analysis: An Introduction","year":"2012","author":"Weihrauch","key":"S0960129524000173_ref49"},{"key":"S0960129524000173_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmateco.2011.07.003"},{"key":"S0960129524000173_ref42","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-7893-5_9"},{"key":"S0960129524000173_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129508007093"},{"key":"S0960129524000173_ref48","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-43.6.544"},{"key":"S0960129524000173_ref18","doi-asserted-by":"publisher","DOI":"10.3390\/e21040375"},{"key":"S0960129524000173_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/BF00484975"},{"key":"S0960129524000173_ref30","volume-title":"Inequalities: Theory of Majorization and Its Applications","volume":"143","author":"Marshall","year":"1979"},{"key":"S0960129524000173_ref50","volume-title":"Computability","volume":"9","author":"Weihrauch","year":"2012"},{"key":"S0960129524000173_ref11","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0046"},{"key":"S0960129524000173_ref26","doi-asserted-by":"publisher","DOI":"10.1351\/pac197022030215"},{"key":"S0960129524000173_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s11238-015-9506-z"},{"key":"S0960129524000173_ref17","volume-title":"Mathematical Foundations of Thermodynamics: International Series of Monographs On Pure and Applied Mathematics","volume":"53","author":"Giles","year":"2016"},{"volume-title":"General Topology","year":"2017","author":"Kelley","key":"S0960129524000173_ref23"},{"volume-title":"Complexity Theory of Real Functions","year":"2012","author":"Ko","key":"S0960129524000173_ref24"},{"key":"S0960129524000173_ref40","unstructured":"Scott, D. (1970). Outline of a mathematical theory of computation. Oxford University Computing Laboratory, Programming Research Group Oxford."},{"key":"S0960129524000173_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.026"},{"key":"S0960129524000173_ref29","first-page":"341","article-title":"The measurement topology and the density topology of posets","volume":"38","author":"Mao","year":"2018","journal-title":"Journal of Mathematical Research with Applications"},{"key":"S0960129524000173_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.58"},{"key":"S0960129524000173_ref41","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0073967"},{"key":"S0960129524000173_ref44","unstructured":"Stoltenberg-Hansen, V. (2001). Notes on domain theory. Lecture notes from the summer school on Proof and System Reliability in Marktoberdorf."},{"key":"S0960129524000173_ref45","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139166386"},{"volume-title":"Computability: An Introduction to Recursive Function Theory","year":"1980","author":"Cutland","key":"S0960129524000173_ref9"},{"key":"S0960129524000173_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.10.016"},{"volume-title":"Topology","year":"2019","author":"Munkres","key":"S0960129524000173_ref36"},{"key":"S0960129524000173_ref46","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68546-5_8"},{"key":"S0960129524000173_ref1","first-page":"1","volume-title":"Handbook of Logic in Computer Science","volume":"6","author":"Abramsky","year":"1994"},{"key":"S0960129524000173_ref8","unstructured":"Cartwright, R. , Parsons, R. and AbdelGawad, M. . (2016). Domain theory: An introduction. arXiv preprint arXiv: 1605.05858."},{"key":"S0960129524000173_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2017.08.002"},{"key":"S0960129524000173_ref47","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-42.1.230"},{"key":"S0960129524000173_ref3","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/257\/04025"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129524000173","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,6]],"date-time":"2024-11-06T08:52:52Z","timestamp":1730883172000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129524000173\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,30]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["S0960129524000173"],"URL":"https:\/\/doi.org\/10.1017\/s0960129524000173","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2024,5,30]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}