{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T10:41:20Z","timestamp":1758278480842,"version":"3.44.0"},"reference-count":34,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T00:00:00Z","timestamp":1666310400000},"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,6,21]]},"abstract":"<jats:p> In this paper, we analyze the problem of finding the minimum dimension n such that an analytic map\/ordinary differential equation over [Formula: see text] can simulate a Turing machine in a way that is robust to perturbations. We show that one-dimensional analytic maps are sufficient to robustly simulate Turing machines; but the minimum dimension for the analytic ordinary differential equations to robustly simulate Turing machines is two, under some reasonable assumptions. We also show that any Turing machine can be simulated by a two-dimensional [Formula: see text] ordinary differential equation on the compact sphere [Formula: see text]. <\/jats:p>","DOI":"10.3233\/com-210381","type":"journal-article","created":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T12:00:35Z","timestamp":1666353635000},"page":"117-144","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":3,"title":["Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines"],"prefix":"10.1177","volume":"12","author":[{"given":"Daniel","family":"Gra\u00e7a","sequence":"first","affiliation":[{"name":"Universidade do Algarve, Portugal"},{"name":"Instituto de Telecomunica\u00e7\u00f5es, Portugal"}]},{"given":"Ning","family":"Zhong","sequence":"additional","affiliation":[{"name":"DMS, University of Cincinnati, OH, USA"}]}],"member":"179","published-online":{"date-parts":[[2022,10,21]]},"reference":[{"key":"ref001","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2001.932503"},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00096-6"},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68546-5_17"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.12.005"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.025"},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1145\/2442829.2442849"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1145\/3127496"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59234-9_6"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00147-B"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68546-5_18"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2004.06.031"},{"key":"ref012","unstructured":"M.L.Campagnolo, Computational Complexity of Real Valued Recursive Functions and Analog Circuits, PhD thesis, Instituto Superior T\u00e9cnico\/Universidade T\u00e9cnica de Lisboa, 2002."},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.2000.0559"},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnab233"},{"key":"ref015","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2026818118"},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.12.010"},{"key":"ref017","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-96-01501-2"},{"key":"ref018","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2007.02.003"},{"key":"ref019","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-04929-0"},{"key":"ref020","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0286-0"},{"issue":"1","key":"ref021","first-page":"1","volume":"10","author":"Kawamura A.","year":"2014","journal-title":"Logical Methods in Computer Science"},{"key":"ref022","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-6802-1"},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00088-6"},{"key":"ref024","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90229-1"},{"key":"ref025","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00117-0"},{"key":"ref026","doi-asserted-by":"publisher","DOI":"10.1007\/11560319_16"},{"key":"ref027","doi-asserted-by":"publisher","DOI":"10.37236\/259"},{"key":"ref028","doi-asserted-by":"publisher","DOI":"10.1162\/089976698300017359"},{"key":"ref029","unstructured":"Y.Matiyasevich, Hilbert\u2019s 10th Problem, The MIT Press, 1993."},{"key":"ref030","doi-asserted-by":"publisher","DOI":"10.1088\/0951-7715\/4\/2\/002"},{"key":"ref031","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1286889124"},{"key":"ref032","unstructured":"P.Odifreddi, Classical Recursion Theory, Vol. 1, Elsevier, 1989."},{"key":"ref033","unstructured":"M.Sipser, Introduction to the Theory of Computation, 3rd edn, Cengage Learning, 2012."},{"key":"ref034","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-42.1.230"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-210381","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-210381","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-210381","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-210381"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,21]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,21]]}},"alternative-id":["10.3233\/COM-210381"],"URL":"https:\/\/doi.org\/10.3233\/com-210381","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"type":"print","value":"2211-3568"},{"type":"electronic","value":"2211-3576"}],"subject":[],"published":{"date-parts":[[2022,10,21]]}}}