Sage Journals: Discover world-class research

Abstract

Several results from classical computability theory (computability over discrete structures such as the natural numbers and strings over finite alphabets, due to Turing, Church, Kleene and others) have been shown to hold for generalisations of computability theory over total abstract algebras, using a computation model of a high level imperative ( While ) language.

We present a number of results relating to computation on topological partial algebras using an abstract model of computation, While , based on high level imperative languages. We investigate the validity of several results from the classical theory in the context of topological algebras on the reals: closure of semicomputable sets under finite union, the equivalence of semicomputable and projectively (semi)computable sets, and Post’s Theorem.

This research has significance in the field of scientific computation, which is underpinned by computability on the real numbers. By the Continuity Principle, computability of functions implies their continuity. Since equality, order, and other total boolean-valued functions on the reals are clearly discontinuous, we resolve this incompatibility by redefining such functions to be partial, leading us to consider topological partial algebras.

Keywords

Generalised computability computability on topological algebra computability on the reals

Get full access to this article

View all access options for this article.

References

Andradas,

Bröcker and

Ruiz, Constructible Sets in Real Geometry, Springer, 1996. doi:10.1007/978-3-642-80024-5.

K.R.

Apt and

E.-R.

Olderog, Verification of Sequential and Concurrent Programs, Springer-Verlag, 1991. doi:10.1007/978-1-4757-4376-0.

Armstrong, Notions of semicomputability in topological algebras over the reals, MSc Thesis, Department of Computing & Software, McMaster University, 2015, Archived in DSpace at http://hdl.handle.net/11375/18334.

Bournez,

M.L.

Campagnolo,

D.S.

Graça and

Hainry, Polynomial differential equations compute all real computable functions, Journal of Complexity 23 (2007), 317–335. doi:10.1016/j.jco.2006.12.005.

Bournez,

Graça and

Pouly, On the functions generated by the general purpose analog computer, Information and Computation 257 (2017), 34–57. doi:10.1016/j.ic.2017.09.015.

Bournez,

Graça and

Pouly, Polynomial time corresponds to solutions of polynomial ordinary differential equations, Journal of the Association for Computing Machinery 64(6) (2017), 38:1–38:76. doi:10.1145/3127496.

Church, An unsolvable problem of elementary number theory, American Journal of Mathematics 58 (1936), 345–363. doi:10.2307/2371045.

Courant and

Hilbert, Methods of Mathematical Physics, Vol. II, Interscience, 1953, Translated and revised from the German edition [1937].

J.W.

de Bakker, Mathematical Theory of Program Correctness, Prentice Hall, 1980.

10.

D.S.

Dummit and

R.M.

Foote, Abstract Algebra, John Wiley and Sons, 1991.

11.

Engeler, Formal Languages: Automata and Structures, Markham, 1968.

12.

M.Q.

Fu, Models of computability of partial functions on the reals, MSc Thesis, Department of Computing & Software, McMaster University, 2007, Technical Report CAS-08-01-JZ, January 2008.

13.

M.Q.

Fu, Characterizations of semicomputable sets, and computable partial functions, on the real plane, PhD Thesis, Department of Computing & Software, McMaster University, 2014, Archived in DSpace at http://hdl.handle.net/11375/16066.

14.

M.Q.

Fu and

J.I.

Zucker, Models of computation for partial functions on the reals, Journal of Logical and Algebraic Methods in Programming (2015). doi:10.1016/j.jlamp.2014.11.001.

15.

D.S.

Graça and

J.F.

Costa, Analog computers and recursive functions over the reals, Journal of Complexity 19 (2003), 644–664. doi:10.1016/S0885-064X(03)00034-7.

16.

Grzegorczyk, Computable functions, Fundamenta Mathematicae 42 (1955), 168–202. doi:10.4064/fm-42-1-168-202.

17.

Grzegorczyk, On the defintions of computable real continuous functions, Fundamenta Mathematicae 44 (1957), 61–71.

18.

Hadamard, Lectures on Cauchy’s Problem in Linear Partial Differential Equations, Dover, 1952, Translated from the French edition [1922].

19.

Hadamard, La Théorie des Équations aux Dérivées Partielles, Éditions Scientifiques, 1964.

20.

S.C.

Kleene, General recursive functions of natural numbers, Mathematische Annalen 112 (1936), 727–742. doi:10.1007/BF01565439.

21.

S.C.

Kleene, Introduction to Metamathematics, North Holland, 1952.

22.

Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles, I, C.R. Acad. Sci. Paris 240 (1955), 2470–2480.

23.

Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles, II, C.R. Acad. Sci. Paris 241 (1955), 13–14.

24.

Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles, III, C.R. Acad. Sci. Paris 241 (1955), 151–153.

25.

Poças, Analog computability in differential equations, PhD Thesis, Department of Mathematics & Statistics, McMaster University, 2017, archived in DSpace at http://hdl.handle.net/11375/22593.

26.

M.B.

Pour-El and

J.I.

Richards, Computability in Analysis and Physics, Springer-Verlag, 1989. doi:10.1007/978-3-662-21717-7.

27.

Shannon, Mathematical theory of the differential analyser, Journal of Mathematics and Physics 20 (1941), 337–354. doi:10.1002/sapm1941201337.

28.

Stoltenberg-Hansen and

J.V.

Tucker, Concrete models of computation for topological algebras, Theoretical Computer Science 219 (1999), 347–378. doi:10.1016/S0304-3975(98)00296-5.

29.

Stoltenberg-Hansen and

J.V.

Tucker, Computable and continuous homomorphisms on metric partial algebras, Bulletin of Symbolic Logic 9 (2003), 299–334. doi:10.2178/bsl/1058448675.

30.

Tucker and

J.I.

Zucker, Computation by ‘while’ programs on topological partial algebras, Theoretical Computer Science 219 (1999), 379–420. doi:10.1016/S0304-3975(98)00297-7.

31.

Tucker and

J.I.

Zucker, Computable functions and semicomputable sets on many-sorted algebras, in: Handbook of Logic in Computer Science, Vol. 5,

Abramsky,

Gabbay and

Maibaum, eds, Oxford University Press, 2000, pp. 317–523.

32.

Tucker and

J.I.

Zucker, Abstract versus concrete computation on metric partial algebras, ACM Transactions on Computational Logic 5 (2004), 611–668. doi:10.1145/1024922.1024924.

33.

Tucker and

J.I.

Zucker, Computable total functions, algebraic specifications and dynamical systems, Journal of Logic and Algebraic Programming 62 (2005), 71–108. doi:10.1016/j.jlap.2003.10.001.

34.

Tucker and

J.I.

Zucker, Generalizing computability theory to abstract algebras, in: Turing’s Revolution. The Impact of His Ideas About Computability,

Sommaruga and

Strahm, eds, Birkhauser/Springer Basel, 2015, pp. 127–160. doi:10.1007/978-3-319-22156-4_5.

35.

A.M.

Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society 42 (1936), 230–265, With correction, ibid., 43, 544–546, 1937. Reprinted in The Undecidable, M. Davis, ed., Raven Press, 1965.

36.

Weihrauch, Computable Analysis: An Introduction, Springer, 2000. doi:10.1007/978-3-642-56999-9.

37.

Xie,

M.Q.

Fu and

Zucker, Characterizations of semicomputable sets of real numbers, Journal of Logic and Algebraic Programming 84 (2015), 124–154. doi:10.1016/j.jlap.2013.11.001.