Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-24T13:10:50.119Z Has data issue: false hasContentIssue false
  • English
  • Français

Domains for Computation in Mathematics, Physics and Exact Real Arithmetic

Published online by Cambridge University Press:  15 January 2014

Abbas Edalat
Abbas Edalat*
Affiliation:
Department of Computing, Imperial College of Science, Technology and Medicine, 180 Queen's Gate London SW7 2BZ, UK.E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We present a survey of the recent applications of continuous domains for providing simple computational models for classical spaces in mathematics including the real line, countably based locally compact spaces, complete separable metric spaces, separable Banach spaces and spaces of probability distributions. It is shown how these models have a logical and effective presentation and how they are used to give a computational framework in several areas in mathematics and physics. These include fractal geometry, where new results on existence and uniqueness of attractors and invariant distributions have been obtained, measure and integration theory, where a generalization of the Riemann theory of integration has been developed, and real arithmetic, where a feasible setting for exact computer arithmetic has been formulated. We give a number of algorithms for computation in the theory of iterated function systems with applications in statistical physics and in period doubling route to chaos; we also show how efficient algorithms have been obtained for computing elementary functions in exact real arithmetic.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 3 , Issue 4 , December 1997 , pp. 401 - 452
Copyright
Copyright © Association for Symbolic Logic 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Abramsky, S., Domain theory in logical form, Annals of Pure and Applied Logic (1991).Google Scholar
[2] Abramsky, S. and Jung, A., Domain theory, Handbook of logic in computer science (Abramsky, S., Gabbay, D. M., and Maibaum, T. S. E., editors), vol. 3, Clarendon Press, 1994.Google Scholar
[3] Alvarez, M., Edalat, A., and Saheb-Djahromi, N., An extension result for continuous valuations, 1997.Google Scholar
[4] Baker, George A. Jr., Essentials of Padé approximants, Academic Press, 1975.Google Scholar
[5] Banks, J., Brooks, J., Cairns, G., Davis, G., and Stacey, P., On Devaney's definition of chaos, American Mathematical Monthly, vol. 99 (1992), no. 4, pp. 332–334.CrossRefGoogle Scholar
[6] Barendregt, H. P., The lambda calculus: Its syntax and semantics, revised ed., North-Holland, 1984.Google Scholar
[7] Barnsley, M. F., Fractals everywhere, second ed., Academic Press, 1993.Google Scholar
[8] Barnsley, M. F. and Demko, S., Iterated function systems and the global construction of fractals, Proceedings of the Royal Society of London, vol. A399 (1985), pp. 243–275.Google Scholar
[9] Barnsley, M. F., Ervin, V., Hardin, D., and Lancaster, J., Solution of an inverse problem for fractals and other sets, Proceedings of the National Academy of Science, vol. 83 (1985), pp. 1975–1977.CrossRefGoogle Scholar
[10] Barnsley, M. F. and Hurd, L. P., Fractal image compression, AK Peters, Ltd, 1993.Google Scholar
[11] Barnsley, M. F., Jacquin, A., Reuter, L., and Sloan, A. D., Harnessing chaos for image synthesis, Computer graphics, 1988, SIGGRAPH proceedings.Google Scholar
[12] Barnsley, M. F. and Sloan, A. D., A better way to compress images, Byte Magazine (1988), pp. 215–223.Google Scholar
[13] Behn, U., van Hemmen, J. L., Kühn, R., Lange, A., and Zagrebnov, V A., Multifractality in forgetful memories, Physica D, vol. 68 (1993), pp. 401–415.CrossRefGoogle Scholar
[14] Behn, U., Patzlaff, H., and Lange, A., Generalized integrals with respect to multifractals densities and discrete stochastic mappings, draft, University of Leipzig, 1996.Google Scholar
[15] Behn, U. and Zagrebnov, V., One dimensional Markovian-field Ising model: Physical properties and characteristics of the discrete stochastic mapping, Journal of Physics. B. Mathematical and General, vol. 21 (1988), pp. 2151–2165.CrossRefGoogle Scholar
[16] Birkhoff, G., Lattice theory, American Mathematical Society, 1967.Google Scholar
[17] Bishop, E. and Bridges, D., Constructive analysis, Springer-Verlag, 1985.CrossRefGoogle Scholar
[18] Blanck, J., Computability on topological spaces by effective domain representations, Ph.D. thesis , Uppsala University, 1997, Uppsala Dissertations in Mathematics 7.Google Scholar
[19] Blanck, J., Domain representability of metric spaces, Annals of Pure and Applied Logic, vol. 83 (1997), pp. 225–247.CrossRefGoogle Scholar
[20] Boehm, H. J. and Cartwright, R., Exact real arithmetic: Formulating real numbers as functions, Research topics in functional programming (Turner, D., editor), Addison-Wesley, 1990, pp. 43–64.Google Scholar
[21] Boehm, H. J., Cartwright, R., Riggle, M., and O'Donnell, M. J., Exact real arithmetic: A case study in higher order programming, ACM symposium on lisp and functional programming, 1986.Google Scholar
[22] Bressloff, P. C. and Stark, J., Neural networks, learning automata and iterated function systems, Fractals and chaos (Crilly, A. J., Earnshaw, R. A., and Jones, H., editors), Springer-Verlag, 1991, pp. 145–164.CrossRefGoogle Scholar
[23] Davies, P., The new physics, Cambridge University Press, 1989.Google Scholar
[24] de Mello, W. and van Strien, S., One-dimensional dynamics, Springer-Verlag, 1993.CrossRefGoogle Scholar
[25] Devaney, R., An introduction to chaotic dynamical systems, second ed., Addison-Wesley, 1989.Google Scholar
[26] Di Gianantonio, P., A functional approach to real number computation, Ph.D. thesis , University of Pisa, 1993.Google Scholar
[27] Di Gianantonio, P., Real number computability and domain theory, Information and Computation, vol. 127 (1996), no. 1, pp. 11–25.CrossRefGoogle Scholar
[28] Di Gianantonio, P., An abstract data type for real numbers, Proceedings of 24th international colloquium on automata, languages, and programming (ICALP'97), 1997.Google Scholar
[29] Diaconis, P. M. and Shahshahani, M., Products ofrandom matrices and computer image generation, Contemporary Mathematics, vol. 50 (1986), pp. 173–182.CrossRefGoogle Scholar
[30] Dudley, R. M., Real analysis and probability, Wadsworth & Brooks/Cole, 1989.Google Scholar
[31] Edalat, A., Domain of computation of a random field in statistical physics, Theory and formal methods 1994: Proceedings of the second Imperial College workshop, IC Press, 1995.Google Scholar
[32] Edalat, A., Domain theory and integration, Theoretical Computer Science, vol. 151 (1995), pp. 163–193.CrossRefGoogle Scholar
[33] Edalat, A., Domain theory in learning processes, Proceedings of MFPS (Brookes, S., Main, M., Melton, A., and Mislove, M., editors), Electronic Notes in Theoretical Computer Science, vol. 1, Elsevier, 1995.Google Scholar
[34] Edalat, A., Domain theory in stochastic processes, Tenth annual IEEE symposium on logic in computer science (LICS), IEEE, 1995.Google Scholar
[35] Edalat, A., Dynamical systems, measures and fractals via domain theory, Information and Computation, vol. 120 (1995), no. 1, pp. 32–48.CrossRefGoogle Scholar
[36] Edalat, A., An algorithm to estimate the Hausdorff dimension of self-affine sets, Imperial College, 1996, draft.Google Scholar
[37] Edalat, A., Power domains and iterated function systems, Information and Computation, vol. 124 (1996), pp. 182–197.CrossRefGoogle Scholar
[38] Edalat, A., The Scott topology induces the weak topology, Eleventh annual IEEE symposium on logic in computer science (LICS), IEEE, 1996.Google Scholar
[39] Edalat, A., When Scott is weak on the top, Mathematical Structures in Computer Science, vol. 7 (1997), pp. 401–417.CrossRefGoogle Scholar
[40] Edalat, A. and Escardó, M., Integration in real PCF, Eleventh annual IEEE symposium on logic in computer science (LICS), IEEE, 1996.Google Scholar
[41] Edalat, A. and Heckmann, R., A computational model for metric spaces, Theoretical Computer Science (1996), to appear.Google Scholar
[42] Edalat, A. and Negri, S., Generalised Riemann integral on locally compact spaces, Advances in theory and formal methods of computing: Proceedings ofthe third Imperial College workshop (Edalat, A., Jourdan, S., and McCusker, G., editors), 04 1996, full paper to appear in Topology and its applications , pp. 73–84.CrossRefGoogle Scholar
[43] Edalat, A. and Potts, P., The storage capacity of forgetful neural nets, Physica D (1996), submitted.Google Scholar
[44] Edalat, A. and Potts, P. J., A new representation for exact real numbers, Proceedings of mathematical foundations of programming semantics 13, Electronic Notes in Theoretical Computer Science, vol. 6, Elsevier Science B. V., 1997.Google Scholar
[45] Edalat, A. and Smyth, M. B., Information categories, Applied Categorical Structures, vol. 1 (1993), pp. 197–232.CrossRefGoogle Scholar
[46] Edalat, A. and Sünderhauf, P., Computable Banach spaces via domain theory, manuscript in preparation.Google Scholar
[47] Edalat, A. and Sünderhauf, P., A domain theoretic approach to computability on the real line, Theoretical Computer Science (1997), to appear.Google Scholar
[48] Elton, J., An ergodic theorem for iterated maps, Journal of Ergodic Theory and Dynamical Systems, vol. 7 (1987), pp. 481–487.CrossRefGoogle Scholar
[49] Ershov, Y.L., Computable functionals of finite types, Algebra and Logic, vol. 11 (1972), no. 4, pp. 367–437.CrossRefGoogle Scholar
[50] Escardó, M. H., PCF extended with real numbers, Theoretical Computer Science, vol. 162 (1996), no. 1, pp. 79–115.CrossRefGoogle Scholar
[51] Escardó, M. H., Properly infective spaces and function spaces, Topology and Its Applications (1997), to appear in a special issue on domain theory, guest editor Jimmie Lawson.Google Scholar
[52] Escardó, M. H. and Streicher, T., Induction and recursion on the partial real line via biquotients of bifree algebras, Twelfth annual IEEE symposium on logic in computer science, IEEE, 1997.Google Scholar
[53] Falconer, K., The Hausdorff dimension of self-affine fractals, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 103 (1988), pp. 339–350.CrossRefGoogle Scholar
[54] Falconer, K., Fractal geometry, John Wiley & Sons, 1989.Google Scholar
[55] Falconer, K., Dimension of self-affine fractals II, Mathematical Proceedings of the Cambridge Philosophical Society, vol. III (1992), pp. 169–179.CrossRefGoogle Scholar
[56] Feigenbaum, M. J., The universal metric properties of nonlinear transformations, Journal of Statistical Physics, vol. 21 (1979), pp. 669–709.CrossRefGoogle Scholar
[57] Fisher, Y., Fractal image compression, Springer-Verlag, 1994.Google Scholar
[58] Flagg, R. C. and Kopperman, R., Computational models for ultrametric spaces, Proceedings of mathematical foundations of programming semantics 13, Electronic Notes in Theoretical Computer Science, Elsevier Science B. V., 1997.Google Scholar
[59] Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M., and Scott, D. S., A compendium of continuous lattices, Springer-Verlag, Berlin, 1980.CrossRefGoogle Scholar
[60] Gordon, R. A., The integrals of Lebesgue, Denjoy, Perron, and Henstock, Graduate Studies in Mathematics, vol. 4, American Mathematical Society, Providence, 1994.Google Scholar
[61] Gosper, W., Continued fraction arithmetic, HAKMEM Item 101B, MIT Artificial Intelligence Memo 239, Massachusetts Institute of Technology, 1972.Google Scholar
[62] Grzegorczyk, A., Computable functionals, Fundamenta Mathematicae, vol. 42 (1955), pp. 168–202.CrossRefGoogle Scholar
[63] Grzegorczyk, A., On the definition of computable real continuous functions, Fundamenta Mathematicae, vol. 44 (1957), pp. 61–71.CrossRefGoogle Scholar
[64] Gunter, C. A., Semantics of programming languages, MIT Press, 1992.Google Scholar
[65] Hayashi, S., Self-similar sets as Tarski's fixed points, Publications of the Research Institute for Mathematical Sciences, vol. 21 (1985), no. 5, pp. 1059–1066.CrossRefGoogle Scholar
[66] Heckmann, R., Approximation of metric spaces by partial metric spaces, Informatik-Berichte 96-04, Technische Universität Braunschweig, 1996, Workshop Domains II.Google Scholar
[67] Heckmann, R., Spaces of valuations, Papers on general topology and its applications, Annals of the New York Academy of Science, vol. 806, 12 1996, pp. 174–200.Google Scholar
[68] Heckmann, R., The appearance of big integers in exact real arithmetic based on linear fractional transformations, submitted to ETAPS'98, 1997.CrossRefGoogle Scholar
[69] van Hemmen, J. L., Keller, G., and Kühn, R., Forgetful memories, Europhysics Letters, vol. 5 (1988), no. 7, pp. 663–668.CrossRefGoogle Scholar
[70] Henstock, R., The general theory of integration, Oxford Mathematical Monographs, Clarendon Press, 1991.CrossRefGoogle Scholar
[71] Hepting, D., Prusinkiewicz, P., and Saupe, D., Rendering methods for iteratedfunction systems, Proceedings IFIP fractals 90, 1991.Google Scholar
[72] Hoofman, R., Continuous information systems, Information and Computation, vol. 105 (1993), pp. 42–71.CrossRefGoogle Scholar
[73] Hutchinson, J. E., Fractals and self-similarity, Indiana University Mathematics Journal, vol. 30 (1981), pp. 713–747.CrossRefGoogle Scholar
[74] Johnstone, P. T., Stone spaces, Cambridge Studies in Advanced Mathematics, vol. 3, Cambridge University Press, Cambridge, 1982.Google Scholar
[75] Jones, C., Probabilistic non-determinism, Ph.D. thesis , University of Edinburgh, 1989.Google Scholar
[76] Jones, C. and Plotkin, G., A probabilistic powerdomain of evaluations, Logic in computer science, IEEE Computer Society Press, 1989, pp. 186–195.Google Scholar
[77] Jones, G. and Singerman, D., Complex functions, Cambridge University Press, 1987.CrossRefGoogle Scholar
[78] Jones, W. B. and Thron, W. J., Continued fractions: Analytic theory and applications, Addison-Wesley, 1980.Google Scholar
[79] Jung, A., Cartesian closed categories of domains, CWI Tract, vol. 66, Centrum voor Wiskunde en Informatica, Amsterdam, 1989.Google Scholar
[80] Kamimura, T. and Tang, A., Total objects of domains, Theoretical Computer Science, vol. 34 (1984), pp. 275–288.CrossRefGoogle Scholar
[81] Kirch, O., Bereiche und Bewertungen, Master's thesis , Technische Hochschule Darmstadt, 1993.Google Scholar
[82] Knuth, D., The art ofcomputer programming, Seminumerical Algorithms, vol. 2, Addison-Wesley, 1969.Google Scholar
[83] Kusuoka, S., A diffusion process on a fractal, Probabilistic methods in mathematical physics, kinokuniya (Ito, K. and Ikeda, N., editors), 1987, Proceedings of the Taniguchi International Symposium (Katata and Kyoto, 1985).Google Scholar
[84] Kusuoka, S., Dirichlet forms on fractals and products of random matrices, Research Institute for Mathematical Sciences. Publications, vol. 25 (1989), pp. 251–274.CrossRefGoogle Scholar
[85] Lacombe, D., Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles I, Comptes Rendus, vol. 240 (1955), pp. 2478–80.Google Scholar
[86] Lawson, J., Valuations on continuous lattices, Continuous lattices and related topics (Hoffmann, Rudolf-Eberhard, editor), Mathematik Arbeitspapiere, vol. 27, Universität Bremen, 1982.Google Scholar
[87] Lawson, J., Computation on metric spaces via domain theory, Topology and its applications (1996), to appear.Google Scholar
[88] Lawson, J., Spaces of maximal points, Mathematical Structures in Computer Science, vol. 7 (1997), pp. 543–556.CrossRefGoogle Scholar
[89] Lester, D. R., Vuillemin's exact real arithmetic, Functional programming, Glasgow 1991: Proceedings of the 1991 workshop, Portree, UK (Heldal, R., Holst, C. K., and Wadler, P. L., editors), Springer-Verlag, Berlin, 1992, pp. 225–238.CrossRefGoogle Scholar
[90] Menissier-Morain, V., Arbitrary precision real arithmetic: design and algorithms, submitted to Journal of Symbolic Computation, 1996.Google Scholar
[91] Moore, R. E., Interval analysis, Prentice-Hall, Englewood Cliffs, 1966.Google Scholar
[92] Nielsen, A. and Kornerup, P., Msb-first digit serial arithmetic, J. of Univ. Comp. Scien., vol. 1 (1995), no. 7.Google Scholar
[93] Norberg, T., Existence theorems for measures on continuous posets, with applications to random set theory, Mathematica Scandinavica, vol. 64 (1989), pp. 15–51.CrossRefGoogle Scholar
[94] Parry, J., A new algorithm for computing fractal dimension, Master's thesis , Department of Computing, Imperial College, 1996.Google Scholar
[95] Plotkin, G. D., LCF considered as a programming language, Theoretical Computer Science, vol. 5 (1977), pp. 223–255.CrossRefGoogle Scholar
[96] Plotkin, G. D., Post-graduate lecture notes in advanced domain theory (incorporating the “Pisa Notes”), Department of Computer Science, University of Edinburgh, 1981.Google Scholar
[97] Potts, P., Edalat, A., and Escardó, M., Semantics of exact real arithmetic, Twelfth annual IEEE symposium on logic in computer science, IEEE, 1997.Google Scholar
[98] Potts, P. J., Efficient and strict algorithms for exact real arithmetic, draft, Imperial College, 1997.Google Scholar
[99] Potts, P. J. and Edalat, A., Exact real arithmetic based on linear fractional transformations, draft, Imperial College, 12 1996.Google Scholar
[100] Potts, P. J. and Edalat, A., Exact real computer arithmetic, draft, Imperial College, 03 1997.Google Scholar
[101] Pour-El, M. B. and Richards, J. I., Computability in analysis andphysics, Springer-Verlag, 1988.Google Scholar
[102] Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, 1967.Google Scholar
[103] Rudin, W., Real and complex analysis, McGraw-Hill, 1966.Google Scholar
[104] Saheb-Djahromi, N., Cpo's of measures for non-determinism, Theoretical Computer Science, vol. 12 (1980), no. 1, pp. 19–37.CrossRefGoogle Scholar
[105] Scott, D. S., Outline of a mathematical theory of computation, 4th annual Princeton conference on information sciences and systems, 1970, pp. 169–176.Google Scholar
[106] Scott, D. S., Continuous lattices, Toposes, algebraic geometry and logic (Lawvere, F. W., editor), Lecture Notes in Mathematics, vol. 274, Springer-Verlag, Berlin, 1972, pp. 97–136.CrossRefGoogle Scholar
[107] Scott, D. S., Models for various type-free calculi, Logic, methodology and philosophy of science IV, North-Holland, 1973, pp. 157–187.Google Scholar
[108] Scott, D. S., Domains for denotational semantics, Automata, languages and programming: Proceedings 1982 (Nielson, M. and Schmidt, E. M., editors), Lecture Notes in Computer Science, vol. 140, Springer-Verlag, Berlin, 1982.CrossRefGoogle Scholar
[109] Smart, D. R., Fixed point theorems, Cambridge University Press, 1974.Google Scholar
[110] Smyth, M. B., Effectively given domains, Theoretical Computer Science, vol. 5 (1977), pp. 257–274.CrossRefGoogle Scholar
[111] Smyth, M. B., Power domains, Journal of Computer and System Sciences, vol. 16 (1978), no. 1, pp. 23–36.CrossRefGoogle Scholar
[112] Smyth, M. B., Power domains and predicate transformers: a topological view, Automata, languages and programming (Diaz, J., editor), Lecture Notes in Computer Science, vol. 154, Springer-Verlag, Berlin, 1983.Google Scholar
[113] Smyth, M. B., Topology, Handbook of logic in computer science, Chapter 5 (Abramsky, S., Gabbay, D., and Maibaum, T. S. E., editors), Oxford University Press, 1992.Google Scholar
[114] Stoltenberg-Hansen, V., Lindström, I., and Griffor, E. R., Mathematical theory of domains, Cambridge Tracts in Theoretical Computer Science, vol. 22, Cambridge University Press, 1994.CrossRefGoogle Scholar
[115] Stoltenberg-Hansen, V. and Tucker, J. V., Complete local rings as domains, Journal of Symbolic Logic, vol. 53 (1988), pp. 603–624.CrossRefGoogle Scholar
[116] Stoltenberg-Hansen, V. and Tucker, J. V., Effective algebras, Handbook of logic in computer science (Gabbay, D. Abramsky, S. and Maibaum, T.S.E., editors), vol. 4, Oxford University Press, 1995, pp. 357–526.CrossRefGoogle Scholar
[117] Sünderhauf, P., A note on tensors in the Ift approach to exact real arithmetic, manuscript, 1997.Google Scholar
[118] Vickers, S. J., Topology via logic, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 1988.Google Scholar
[119] Vickers, S. J., Information systems for continuous posets, Theoretical Computer Science, vol. 114 (1993), pp. 201–229.CrossRefGoogle Scholar
[120] Vuillemin, J. E., Exact real computer arithmetic with continued fractions, IEEE Transactionson Computers, vol. 39 (1990), no. 8, pp. 1087–1105.CrossRefGoogle Scholar
[121] Wall, H. S., Analytic theory of continued fractions, Chelsea Publishing, 1973.Google Scholar
[122] Weihrauch, K., A foundation for computable analysis, Combinatorics, complexity, and logic, discrete mathematics and theoretical computer science (Bridges, D. S., Calude, C.S., Gibbons, J., Reeves, S., and Witten, I. H., editors), Proceedings of DMTCS'96, Springer-Verlag, Singapore, 1997, pp. 66–89.Google Scholar
[123] Weihrauch, K. and Deil, T., Berechenbarkeit auf cpo's, Technical Report 63, Rheinisch-Westfälische Technische Hochschule Aachen, 1980.Google Scholar
[124] Weihrauch, K. and Schreiber, U., Embedding metric spaces into cpo's, Theoretical Computer Science, vol. 16 (1981), pp. 5–24.CrossRefGoogle Scholar