The Elliptic Integral Machine:

I. A. C. Melnik

Russian journal of nonlinear dynamics, Tome 18 (2022) no. 1, pp. 83-102.

Résumé

In this work we will show how any elliptic integral can be computed by analyzing the asymptotic behavior of idealized mechanical models. Specifically, our results reveal how a set of circular billiard systems computes the canonical set of three elliptic integrals defined by Legendre. We will treat these Newtonian systems as a particular application of the billiard-ball model, a ballistic computer idealized by Eduard Fredkin and Tommaso Toffoli. Initially, we showed how to define the initial conditions in order to encode the computation of a set of integral functions. We then combined our first conclusions with results established in the 18th and 19th centuries mostly by Euler, Lagrange, Legendre and Gauss in developing the theory of integral functions. In this way, we derived collision-based methods to compute elementary functions, integrals functions and mathematical constants. In particular, from the Legendre identity for elliptic integrals, we were able to define a new collision-based method to compute the number $\pi$, while an identity demonstrated by Gauss revealed a new method to compute the arithmeticgeometric mean. In order to explore the computational potential of the model, we admitted a hypothetical device that measures the total number of collisions between the balls and the boundary. There is even the possibility that the methods we are about to describe could one day be experimentally applied using optical phenomena, as recent studies indicate that it is possible to implement collision-based computation with solitons.

Détail

Keywords: collision-based computing, physical models of computation, elliptic integral, arithmetic geometric mean.
Mots-clés : billiard

Bibliographie

[1] Zuse, K., Rechnender Raum, Vieweg, Braunschweig, 1969, 84 pp. | Zbl

[2] Sauder, J., Hilgemann, E., Johnson, M., Parness, A., Bienstock, B., Hall, J., Kawata, J., and Stack, K., “Automaton Rover for Extreme Environments”, Technical Report, 2017, California Institute of Technology, California, 44 pp.

[3] Fredkin, E. and Toffoli, T., “Conservative Logic”, Int. J. Theor. Phys., 21:3–4 (1982), 219–253 | DOI | MR | Zbl

[4] Beggs, E. J. and Tucker, J. V., “Embedding Infinitely Parallel Computation in Newtonian Kinematics”, Appl. Math. Comput., 178:1 (2006), 25–43 | MR | Zbl

[5] Jakubowski, M. J., “Computing with Solitons in Bulk Media”, PhD Thesis, Princeton Univ., Princeton, N.J.\, 1999, 158 pp.

[6] Rozenberg, G., Bäck, Th., and Kok, J. N., Handbook of Natural Computing, Springer, Berlin, 2012, LII, 2052 pp. | MR | Zbl

[7] Toffoli, T. and Margolus, N., Cellular Automata Machines: A New Environment for Modeling, MIT Press, Cambridge, 1987, 276 pp.

[8] Richard, K. S. and Steiglitz, K., “Programmable Parallel Arithmetic in Cellular Automata Using a Particle Model”, Complex Syst., 8:5 (1994), 311–323 | MR | Zbl

[9] Beggs, E. J. and Tucker, J. V., “Experimental Computation of Real Numbers by Newtonian Machines”, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 463:2082 (2007), 1541–1561 | MR | Zbl

[10] Beggs, E. J. and Tucker, J. V., “Can Newtonian Systems, Bounded in Space, Time, Mass and Energy Compute All Functions?”, Theoret. Comput. Sci., 371:1–2 (2007), 4–19 | DOI | MR | Zbl

[11] Collision-Based Computing, ed. A. Adamatzky, Springer, London, 2002, xxviii+549 pp. | MR | Zbl

[12] Galperin, G. A., “Playing Pool with $\pi$ (the Number $\pi$ from a Billiard Point of View)”, Regul. Chaotic Dyn., 8:4 (2003), 375–394 | DOI | MR | Zbl

[13] Ganguly, N., Sikdar, B. K., Deutsch, A., Canright, G., and Chaudhuri, P. A., Survey on Cellular Automata, Technical Report No. 9, Centre for High Performance Computing, Dresden University of Technology, 2003, 30 pp.

[14] Smith, M. A., “Cellular Automata Methods in Mathematical Physics”, PhD Thesis, 1994, Mass., MIT, Cambridge, 243 pp. | MR

[15] Wolfram, S., “Universality and Complexity in Cellular Automata”, Phys. D, 10:1–2 (1984), 1–35 | DOI | MR | Zbl

[16] Dascalu, M., “Cellular Automata Hardware Implementations: An Overview”, Rom. J. Inf. Sci. Technol., 19:4 (2016), 360–368

[17] Toffoli, T., “Cellular Automata As an Alternative to (Rather Than an Approximation of) Differential Equations in Modeling Physics”, Phys. D, 10:1–2 (1984), 117–127 | DOI | MR | Zbl

[18] Margolus, N., “Physics-Like Models of Computation”, Phys. D, 10:1–2 (1984), 81–95 | DOI | MR | Zbl

[19] Fredkin, E., “An Introduction to Digital Philosophy”, Internat. J. Theoret. Phys., 42:2 (2003), 189–247 | DOI | MR | Zbl

[20] Toffoli, T., “CAM: A High-Performance Cellular-Automaton”, Phys. D, 10:1–2 (1984), 195–204 | DOI | MR

[21] Byrd, P. F. and Friedman, M. D., Handbook of Elliptic Integrals for Engineers and Scientists, Grundlehren Math. Wiss., 67, 2nd ed., rev., Springer, New York, 1971, xvi+358 pp. | MR | Zbl

[22] Hancock, H., Elliptic Integrals, Dover, New York, 1958, 104 pp. | MR | Zbl

[23] Borwein, J. M. and Borwein, P. B., Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity, Wiley, New York, 1987, xvi+414 pp. | MR | Zbl

[24] Salamin, E., “Computation of $\pi$ Using Arithmetic-Geometric Mean”, Math. Comp., 30:135 (1976), 565–570 | MR | Zbl

[25] Brent, J. M., “Fast Multiple-Precision Evaluation of Elementary Functions”, J. Assoc. Comput. Mach., 23:2 (1976), 242–251 | DOI | MR | Zbl

[26] Chernov, N. and Markarian, R., Chaotic Billiards, Math. Surv. Monogr., 127, AMS, Providence, R.I., 2006, xii+316 pp. | DOI | MR | Zbl

[27] Bellman, R., A Brief Introduction to Theta Functions, Holt, Rinehart Winston, New York, 1961, x+78 pp. | MR | Zbl

[28] Thornton, S. T. and Marion, J. B., Classical Dynamics of Particles and Systems, 5th ed, Brooks/Cole, Pacific Grove, Calif., 2004, 656 pp.

[29] Aretxabaleta, X. M., Gonchenko, M., Harshman, N. L., Jackson, S. G., Olshanii, M., and Astrakharchik, G. E., “The Dynamics of Digits: Calculating Pi with Galperin's Billiards”, Mathematics, 8:4 (2020), 509, 32 pp. | DOI

[30] Zhang, L., “Computing Naturally in the Billiard Ball Model”, UC'09: Proc. of the 8th Internat. Conf. on Unconventional Computation (Ponta Delgada, Portugal, Sept 2009), Springer, Berlin, 2009, 277–286 | DOI | MR | Zbl

[31] Berger, B., Geometry Revealed: A Jacob's Ladder to Modern Higher Geometry, Springer, Berlin, 2010, 831 pp. | MR

[32] Chang, S.-J. and Friedberg, R., “Elliptical Billiards and Poncelet's Theorem”, J. Math. Phys., 29:7 (1988), 1537–1550 | DOI | MR | Zbl

[33] Fredkin, E., “Digital Mechanics: An Informational Process Based on Reversible Universal Cellular Automata”, Phys. D, 45:1–3 (1990), 254–270 | DOI | MR | Zbl