{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,13]],"date-time":"2025-12-13T06:39:43Z","timestamp":1765607983196,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2004,10,1]],"date-time":"2004-10-01T00:00:00Z","timestamp":1096588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2004,10]]},"abstract":"<jats:p>In the theory of computation on topological algebras there is a considerable gap between so-called abstract and concrete models of computation. In concrete models, unlike abstract models, the computations depend on the representation of the algebra. First, we show that with abstract models, one needs algebras with &lt;i&gt;partial operations&lt;\/i&gt;, and computable functions that are both &lt;i&gt;continuous&lt;\/i&gt; and &lt;i&gt;many-valued&lt;\/i&gt;. This many-valuedness is needed even to compute single-valued functions, and so &lt;i&gt;abstract models must be nondeterministic even to compute deterministic problems&lt;\/i&gt;. As an abstract model, we choose the \"while\"-array programming language, extended with a nondeterministic \"countable choice\" assignment, called the &lt;i&gt;&lt;b&gt;WhileCC*&lt;\/b&gt;&lt;\/i&gt; model. Using this, we introduce the concept of &lt;i&gt;approximable many-valued computation&lt;\/i&gt; on metric algebras. For our concrete model, we choose metric algebras with &lt;i&gt;effective representations&lt;\/i&gt;. We prove:(1) for any metric algebra &lt;i&gt;A&lt;\/i&gt; with an effective representation \u03b1, &lt;i&gt;&lt;b&gt;WhileCC*&lt;\/b&gt;&lt;\/i&gt; approximability implies computability in \u03b1, and (2) also the converse, under certain reasonable conditions on &lt;i&gt;A&lt;\/i&gt;. From (1) and (2) we derive an equivalence theorem between abstract and concrete computation on metric partial algebras. We give examples of algebras where this equivalence holds.<\/jats:p>","DOI":"10.1145\/1024922.1024924","type":"journal-article","created":{"date-parts":[[2004,10,7]],"date-time":"2004-10-07T17:38:56Z","timestamp":1097170736000},"page":"611-668","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Abstract versus concrete computation on metric partial algebras"],"prefix":"10.1145","volume":"5","author":[{"given":"J. V.","family":"Tucker","sequence":"first","affiliation":[{"name":"University of Wales, Swansea, Wales"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. I.","family":"Zucker","sequence":"additional","affiliation":[{"name":"McMaster University, Hamilton, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aberth O. 1980. Computable Analysis. MIT Press Cambridge MA. Aberth O. 1980. Computable Analysis. MIT Press Cambridge MA."},{"key":"e_1_2_1_2_1","unstructured":"Aberth O. 2001. Computable Calculus. Addison-Wesley Reading MA. Aberth O. 2001. Computable Calculus. Addison-Wesley Reading MA."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Apt K. and Olderog E.-R. 1991. Verification of Sequential and Concurrent Programs. Springer-Verlag Berlin Germany. Apt K. and Olderog E.-R. 1991. Verification of Sequential and Concurrent Programs. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-1-4757-4376-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Blum L. Cucker F. Shub M. and Smale S. 1998. Complexity and Real Computation. Springer-Verlag Berlin Germany. Blum L. Cucker F. Shub M. and Smale S. 1998. Complexity and Real Computation. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","article-title":"On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines","volume":"21","author":"Blum L.","year":"1989","journal-title":"Bull. Amer. Math. Soc."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00249-9"},{"volume-title":"FernUniversit\u00e4t Hagen","year":"1999","author":"Brattka V.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","first-page":"49","article-title":"Algebraic operators in constructive complete separable metric spaces","volume":"128","author":"Ceitin G.","year":"1959","journal-title":"Dok. Akad. Nauk SSSR"},{"key":"e_1_2_1_9_1","unstructured":"de Bakker J. 1980. Mathematical Theory of Program Correctness. Prentice Hall Englewood Cliffs NJ. de Bakker J. 1980. Mathematical Theory of Program Correctness. Prentice Hall Englewood Cliffs NJ."},{"key":"e_1_2_1_10_1","unstructured":"Dijkstra E. 1976. A Discipline of Programming. Prentice Hall Englewood Cliffs NJ. Dijkstra E. 1976. A Discipline of Programming. Prentice Hall Englewood Cliffs NJ."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1096"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"401","DOI":"10.2307\/421098","article-title":"Domains for computation in mathematics, physics and exact real arithmetic","volume":"3","author":"Edalat A.","year":"1997","journal-title":"Bull. Symbol. Log."},{"key":"e_1_2_1_13_1","unstructured":"Engelking R. 1989. General Topology. Heldermann Verlag Berlin Lemge Germany. Engelking R. 1989. General Topology. Heldermann Verlag Berlin Lemge Germany."},{"volume-title":"Data Structuring","year":"1978","author":"Goguen J.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"168","DOI":"10.4064\/fm-42-1-168-202","article-title":"Computable functions","volume":"42","author":"Grzegorczyk A.","year":"1955","journal-title":"Fundamenta Mathematicae"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.4064\/fm-44-1-61-71","article-title":"On the defintions of computable real continuous functions","volume":"44","author":"Grzegorczyk A.","year":"1957","journal-title":"Fundamenta Mathematicae"},{"volume-title":"Scientific Computing: An Introductory Survey","year":"1997","author":"Heath M.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","first-page":"2470","article-title":"Extension de la notion de fonction r\u00e9cursive aux fonctions d'une ou plusieurs variables r\u00e9elles","volume":"240","author":"Lacombe D.","year":"1955","journal-title":"I, II, III. C.R. Acad. Sci. Paris."},{"key":"e_1_2_1_19_1","unstructured":"Meseguer J. and Goguen J. 1985. Initiality induction and computability. In Algebraic Methods in Semantics M. Nivat and J. Reynolds Eds. Cambridge University Press Cambridge U.K. 459--541. Meseguer J. and Goguen J. 1985. Initiality induction and computability. In Algebraic Methods in Semantics M. Nivat and J. Reynolds Eds. Cambridge University Press Cambridge U.K. 459--541."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"215","DOI":"10.4064\/fm-55-3-215-238","article-title":"Recursive metric spaces","volume":"55","author":"Moschovakis Y.","year":"1964","journal-title":"Fundamenta Mathematicae"},{"key":"e_1_2_1_21_1","unstructured":"Odifreddi P. 1999. Classical Recursion Theory 21st ed. North Holland Amsterdam The Netherlands. Odifreddi P. 1999. Classical Recursion Theory 21st ed. North Holland Amsterdam The Netherlands."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Pour-El M. and Richards J. 1989. Computability in Analysis and Physics. Springer-Verlag Berlin Germany. Pour-El M. and Richards J. 1989. Computability in Analysis and Physics. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-3-662-21717-7"},{"key":"e_1_2_1_23_1","unstructured":"Royden H. 1963. Real Analysis. Macmillan London U.K. Royden H. 1963. Real Analysis. Macmillan London U.K."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"185","DOI":"10.2307\/2586596","article-title":"On effective topological spaces","volume":"63","author":"Spreen D.","year":"1998","journal-title":"J. Symbol. Log."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00319-4"},{"key":"e_1_2_1_26_1","unstructured":"Stephenson K. 1996. An algebraic approach to syntax semantics and computation. Ph.D. dissertation Department of Computer Science University of Wales Swansea U.K. Stephenson K. 1996. An algebraic approach to syntax semantics and computation. Ph.D. dissertation Department of Computer Science University of Wales Swansea U.K."},{"key":"e_1_2_1_27_1","unstructured":"Stewart K. 1998. Concrete and abstract models of computation over metric algebras. Ph.D. dissertation Department of Computer Science University of Wales Swansea U.K. Stewart K. 1998. Concrete and abstract models of computation over metric algebras. Ph.D. dissertation Department of Computer Science University of Wales Swansea U.K."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1017\/S0022481200028498","article-title":"Complete local rings as domains","volume":"53","author":"Stoltenberg-Hansen V.","year":"1988","journal-title":"J. Symbol. Log."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Stoltenberg-Hansen V. and Tucker J. 1995. Effective algebras. In Handbook of Logic in Computer Science S. Abramsky D. Gabbay and T. Maibaum Eds. Vol. 4. Oxford University Press Oxford U.K. 357--526. Stoltenberg-Hansen V. and Tucker J. 1995. Effective algebras. In Handbook of Logic in Computer Science S. Abramsky D. Gabbay and T. Maibaum Eds. Vol. 4. Oxford University Press Oxford U.K. 357--526.","DOI":"10.1093\/oso\/9780198537809.003.0004"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00296-5"},{"key":"e_1_2_1_31_1","unstructured":"Taylor A. and Lay D. 1980. Introduction to Functional Analysis. John Wiley & Sons New York NY. Taylor A. and Lay D. 1980. Introduction to Functional Analysis. John Wiley & Sons New York NY."},{"volume":"6","volume-title":"CWI Monographs","author":"Tucker J.","key":"e_1_2_1_32_1"},{"volume-title":"Constructivity in Computer Science: Summer Symposium","year":"1991","author":"Tucker J.","key":"e_1_2_1_33_1"},{"volume":"629","volume-title":"Eds. Lecture Notes in Computer Science","author":"Tucker J.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","unstructured":"Tucker J. and Zucker J. 1994. Computable functions on stream algebras. In Proof and Computation: NATO Advanced Study Institute International Summer School at Marktoberdorf 1993 H. Schwichtenberg Ed. Springer-Verlag Berlin Germany 341--382. Tucker J. and Zucker J. 1994. Computable functions on stream algebras. In Proof and Computation: NATO Advanced Study Institute International Summer School at Marktoberdorf 1993 H. Schwichtenberg Ed. Springer-Verlag Berlin Germany 341--382."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00297-7"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Tucker J. and Zucker J. 2000. Computable functions and semicomputable sets on many-sorted algebras. In Handbook of Logic in Computer Science S. Abramsky D. Gabbay and T. Maibaum Eds. Vol. 5. Oxford University Press Oxford U.K. 317--523. Tucker J. and Zucker J. 2000. Computable functions and semicomputable sets on many-sorted algebras. In Handbook of Logic in Computer Science S. Abramsky D. Gabbay and T. Maibaum Eds. Vol. 5. Oxford University Press Oxford U.K. 317--523.","DOI":"10.1093\/oso\/9780198537816.003.0008"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/505372.505375"},{"key":"e_1_2_1_39_1","unstructured":"Tucker J. and Zucker J. 2002b. Computable total functions on metric algebras universal algebraic specifications and dynamical systems. Tech. rep. CAS 02-04-JZ Department of Computing & Software McMaster University Hamilton Ont. Canada. (Accepted for publication in Journal of Logic and Algebraic Programming.) Tucker J. and Zucker J. 2002b. Computable total functions on metric algebras universal algebraic specifications and dynamical systems. Tech. rep. CAS 02-04-JZ Department of Computing & Software McMaster University Hamilton Ont. Canada. (Accepted for publication in Journal of Logic and Algebraic Programming.)"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-56999-9","volume-title":"Computable Analysis: An Introduction","author":"Weihrauch K.","year":"2000"},{"volume-title":"Handbook of Theoretical Computer Science","author":"Wirsing M.","key":"e_1_2_1_41_1"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1024922.1024924","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1024922.1024924","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:46Z","timestamp":1750286926000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1024922.1024924"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,10]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,10]]}},"alternative-id":["10.1145\/1024922.1024924"],"URL":"https:\/\/doi.org\/10.1145\/1024922.1024924","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2004,10]]},"assertion":[{"value":"2004-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}