Sage Journals: Discover world-class research

Abstract

Most of the physical processes arising in nature are modeled by differential equations, either ordinary (example: the spring/mass/damper system) or partial (example: heat diffusion). From the point of view of analog computability, the existence of an effective way to obtain solutions (either exact or approximate) of these systems is essential.

A pioneering model of analog computation is the General Purpose Analog Computer (GPAC), introduced by Shannon [Journal of Mathematical Physics 20 (1941), 337–354] as a model of the Differential Analyzer and improved by Pour-El [Transactions of the American Mathematical Society 199 (1974), 1–28], Lipshitz and Rubel [Proceedings of the American Mathematical Society 99(2) (1987)], Costa and Graça [Journal of Complexity 19(5) (2003), 644–664] and others. The GPAC is capable of manipulating real-valued data streams. Its power is known to be characterized by the class of differentially algebraic functions, which includes the solutions of initial value problems for ordinary differential equations.

We address one of the limitations of this model, which is its fundamental inability to reason about functions of more than one independent variable (the ‘time’ variable), as noted by Rubel [Advances in Applied Mathematics 14(1) (1993), 39–50]. In particular, the Shannon GPAC cannot be used to specify solutions of partial differential equations. We extend the class of data types using networks with channels which carry information on a general complete metric space X; here we take $X = C (R)$ , the class of continuous functions of one real (spatial) variable.

We consider the original modules in Shannon’s construction (constants, adders, multipliers, integrators) and we add a differential module which has one input and one output. For input u, it outputs the spatial derivative $v (t) = \partial_{x} u (t)$ .

We then define an X-GPAC to be a network built with X-stream channels and the above-mentioned modules. This leads us to a framework in which the specifications of such analog systems are given by fixed points of certain operators on continuous data streams. Such a framework was considered by Tucker and Zucker [Theoretical Computer Science 371 (2007), 115–146]. We study the properties of these analog systems and their associated operators, and present a characterization of the X-GPAC-generable functions which generalizes Shannon’s results.

Keywords

Analog computation computable analysis partial differential equations

Get full access to this article

View all access options for this article.

References

Bournez,

Graça and

Pouly, On the functions generated by the general purpose analog computer, 2016, submitted on 21 Jan 2016, arXiv:1602.00546.

Bush, The differential analyzer. A new machine for solving differential equations, Journal of the Franklin Institute 212(4) (1931), 447–488. doi:10.1016/S0016-0032(31)90616-9.

Campagnolo,

Moore and

J.F.

Costa, An analog characterization of the Grzegorczyk hierarchy, Journal of Complexity 18(4) (2002), 977–1000. doi:10.1006/jcom.2002.0655.

Courant and

Hilbert, Methods of Mathematical Physics, Vol. 2, Interscience Publishers, Inc., 1953.

Graça, Some recent developments on Shannon’s general purpose analog computer, Mathematical Logic Quarterly 50(4–5) (2004), 473–485.

Graça and

J.F.

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

Grzegorczyk, Computable functions, Fundamenta Mathematicae 42 (1955), 168–202.

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

Hadamard, Lectures on Cauchy’s Problem in Linear Partial Differential Equations, Dover, 1952.

10.

D.R.

Hartree, Calculating Instruments and Machines, Cambridge University Press, 1950.

11.

P.A.

Holst, Svein Rosseland and the Oslo Analyzer, IEEE Annals of the History of Computing 18(4) (1996), 16–26. doi:10.1109/85.539912.

12.

N.D.

James and

J.I.

Zucker, A class of contracting stream operators, The Computer Journal 56 (2013), 15–33. doi:10.1093/comjnl/bxs054.

13.

Johansson, Early analog computers in Sweden – With examples from Chalmers University of Technology and the Swedish aerospace industry, IEEE Annals of the History of Computing 18(4) (1996), 27–33. doi:10.1109/85.539913.

14.

Kleene, Arithmetical predicates and function quantifiers, Transactions of the American Mathematical Society 79 (1955), 312–340. doi:10.1090/S0002-9947-1955-0070594-4.

15.

Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles I, Comptes Rendus des Séances d l’Académie des Sciences, Paris 240 (1955), 2478–2480.

16.

Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles II, Comptes Rendus des Séances d l’Académie des Sciences, Paris 241 (1955), 13–14.

17.

Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles III, Comptes Rendus des Séances d l’Académie des Sciences, Paris 241 (1955), 151–153.

18.

Lipshitz and

Rubel, A differentially algebraic replacement theorem, Proceedings of the American Mathematical Society 99(2) (1987), 367–372. doi:10.1090/S0002-9939-1987-0870803-1.

19.

J.W.

Mills, The nature of the extended analog computer, Physica D: Nonlinear Phenomena 237(9) (2008), 1235–1256. doi:10.1016/j.physd.2008.03.041.

20.

Moore, Recursion theory on the reals and continuous-time computation, Theoretical Computer Science 162(1) (1996), 23–44. doi:10.1016/0304-3975(95)00248-0.

21.

Mycka and

J.F.

Costa, Real recursive functions and their hierarchy, Journal of Complexity 20(6) (2004), 835–857. doi:10.1016/j.jco.2004.06.001.

22.

F.W.J.

Olver,

D.W.

Lozier,

R.F.

Boisvert and

C.W.

Clark, NIST Handbook of Mathematical Functions, Cambridge University Press, 2010.

23.

Pouly, Continuous models of computation: from computability to complexity, PhD thesis, École Polytechnique and Universidade do Algarve, 2015.

24.

Pour-El, Abstract computability and its relations to the general purpose analog computer, Transactions of the American Mathematical Society 199 (1974), 1–28. doi:10.1090/S0002-9947-1974-0347575-8.

25.

Pour-El and

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

26.

Renardy and

R.C.

Rogers, An Introduction to Partial Differential Equations, Vol. 13, 2nd edn, Springer-Verlag, New York, 2006.

27.

L.A.

Rubel, The extended analog computer, Advances in Applied Mathematics 14(1) (1993), 39–50. doi:10.1006/aama.1993.1003.

28.

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

29.

J.S.

Small, General-purpose electronic analog computing: 1945–1965, IEEE Annals of the History of Computing 15(2) (1993), 8–18. doi:10.1109/85.207740.

30.

Thompson and

P.G.

Tait, Treatise on Natural Philosophy, Vol. 1, 2nd edn, Cambridge University Press, 1880, Part I.

31.

J.V.

Tucker and

J.I.

Zucker, Computable functions and semicomputable sets on many sorted algebras, in: Handbook of Logic for Computer Science,

Abramsky,

Gabbay and

Maibaum, eds, University Series in Mathematics, Vol. V, Oxford University Press, 2000, pp. 317–523.

32.

J.V.

Tucker and

J.I.

Zucker, Computability of analog networks, Theoretical Computer Science 371 (2007), 115–146. doi:10.1016/j.tcs.2006.10.018.

33.

J.V.

Tucker and

J.I.

Zucker, Continuity of operators on continuous and discrete time streams, Theoretical Computer Science 412 (2011), 3378–3403. doi:10.1016/j.tcs.2011.04.012.

34.

J.V.

Tucker and

J.I.

Zucker, Computability of operators on continuous and discrete time streams, Computability 3 (2014), 9–44.

35.

Weihrauch, Computable Analysis – An Introduction, Texts in Theoretical Computer Science, Springer-Verlag, Berlin, Heidelberg, 2000. doi:10.1007/978-3-642-56999-9.

Analog networks on function data streams

Abstract

Keywords

Get full access to this article

References