Decidability and Universality in Symbolic Dynamical Systems

• Autorzy: Delvenne J-C. , Kurka P. , Blondel V.
• Języki publikacji: EN

Abstrakty

EN

Many different definitions of computational universality for various types of dynamical systems have flourished since Turing's work. We propose a general definition of universality that applies to arbitrary discrete time symbolic dynamical systems. Universality of a system is defined as undecidability of a model-checking problem. For Turing machines, counter machines and tag systems, our definition coincides with the classical one. It yields, however, a new definition for cellular automata and subshifts. Our definition is robust with respect to initial condition, which is a desirable feature for physical realizability. We derive necessary conditions for undecidability and universality. For instance, a universal system must have a sensitive point and a proper subsystem. We conjecture that universal systems have infinite number of subsystems. We also discuss the thesis according to which computation should occur at the `edge of chaos' and we exhibit a universal chaotic system.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 463--490
• Opis fizyczny: bibliogr. 40 poz., wykr.

Twórcy

autor

Delvenne J-C.

autor

Kurka P.

autor

Blondel V.

• Universite catholique de Louvain, Department of Mathematical Engineering, Avenue Georges Lemaitre 4, B-1348 Louvain-la-Neuve, Belgium,

Bibliografia

• [1] E. Asarin and A. Bouajjani. Perturbed turing machines and hybrid systems. In Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science (LICS-01), pages 269-278, Los Alamitos, CA, June 16-19 2001. IEEE Computer Society.
• [2] E. Asarin, O. Maler, and A. Pnueli. Reachability analysis of dynamical systems having piecewise-constant derivatives. Theoretical Computer Science, 138(1):35-65, 1995. Special issue on hybrid systems.
• [3] J. Banks, J. Brooks, G. Cairns, G. Davis, and P. Stacey. On Devaney's definition of chaos. American Mathematics Monthly, 99:332-334, 1992.
• [4] A. Ben-Hur, H. T. Siegelmann, and S. Fishman. A theory of complexity for continuous time systems. Journal of Complexity, 18(1):51-86, 2002.
• [5] O. Bournez and M. Cosnard. On the computational power of dynamical systems and hybrid systems. Theoretical Computer Science, 168:417-459, 1996.
• [6] J. H. Conway. Unpredictable iterations. In Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972), pages 49-52, Boulder, Colo., 1972. Univ. Colorado.
• [7] J. P. Crutchfield and K. Young. Computation at the onset of chaos. In W. Zurek, editor, Complexity, Entropy and the Physics of Information, pages 223-269. Addison-Wesley, 1989.
• [8] M. D. Davis. A note on universal Turing machines. In C.E. Shannon and J. McCarthy, editors, Automata Studies, pages 167-175. Princeton University Press, 1956.
• [9] J.-C. Delvenne and V. D. Blondel. Quasiperiodic configurations and undecidable dynamics for tilings, infinite words and Turing machines. Theoretical Computer Science, 319:127-143, 2004.
• [10] J.-Ch. Delvenne, P. K°urka, and V. D. Blondel. Computational universality in symbolic dynamical systems. In M. Margenstern, editor, MCU 2004, number 3354 in Lecture Notes in Computer Science, pages 104-115. Springer-Verlag, 2005.
• [11] R. Devaney. An Introduction to Chaotic Dynamical Systems. Addison-Wesley, 1989.
• [12] B. Durand and Z. Róka. The Game of Life: universality revisited. In M. Delorme and J. Mazoyer, editors, Cellular Automata: a ParallelModel, volume 460 of Mathematics and its Applications, pages 51-74. Kluwer Academic Publishers, 1999.
• [13] Edward Fredkin and Tommaso Toffoli. Conservative logic. International Journal of Theoretical Physics, 21(3-4):219-253, 1981/82. Physics of computation, Part I (Dedham,Mass., 1981).
• [14] Peter Gács. Reliable cellular automata with self-organization. In 38th Annual Symposium on Foundations of Computer Science, pages 90-99, Miami Beach, Florida, 20-22 October 1997. IEEE.
• [15] E. M. Clarke Jr., O. Grumberg, and D. A. Peled. Model checking. MIT Press, 1999.
• [16] H. Rogers Jr. Theory of recursive functions and effective computability. MIT Press, Cambridge,MA, second edition, 1987.
• [17] R. Kaivola. Using automata to characterise fixed point temporal logics. PhD thesis, University of Edinburgh, 1996.
• [18] P. Koiran. A family of universal recurrent networks. Theoretical Computer Science, 168(2):473-480, 1996. Universal machines and computations (Paris, 1995).
• [19] P. Koiran,M. Cosnard, andM. Garzon. Computability with low-dimensional dynamical systems. Theoretical Computer Science, 132(1-2):113-128, 1994.
• [20] P. Koiran and Cr. Moore. Closed-form analytic maps in one and two dimensions can simulate universal Turing machines. Theoretical Computer Science, 210(1):217-223, 1999.
• [21] P. Kurka. On topological dynamics of Turing machines. Theoretical Computer Science, 174(1-2):203-216, 1997.
• [22] P. Kurka. Zero-dimensional dynamical systems, formal languages, and universality. Theory of Computing Systems, 32(4):423-433, 1999.
• [23] P. Kurka. Topological and Symbolic Dynamics, volume 11 of Cours Spécialisés. Société Mathématique de France, 2003.
• [24] C. G. Langton. Computation at the edge of chaos. Physica D, 42:12-37, 1990.
• [25] W. Maass and P. Orponen. On the effect of analog noise in discrete-time analog computations. Neural Computation, 10(5):1071-1095, 1998.
• [26] M. L. Minsky. Recursive unsolvability of Post's problem of "tag" and other topics in theory of Turing machines. Annals of Mathematics (2), 74:437-455, 1961.
• [27] M. Mitchell, P. T. Hraber, and J. P. Crutchfield. Dynamic computation, and the "edge of chaos": A reexamination. In G. Cowan, D. Pines, and D. Melzner, editors, Complexity: Metaphors, Models, and Reality, Santa Fe Institute Proceedings, Volume 19, pages 497-513. Addison-Wesley, 1994. Santa Fe InstituteWorking Paper 93-06-040.
• [28] Cr.Moore. Unpredictability and undecidability in dynamical systems. Physical Review Letters, 64(20):2354-2357, 1990.
• [29] Cr. Moore. Generalized shifts: Unpredictability and undecidability in dynamical systems. Nonlinearity, 4:199-230, 1991.
• [30] Cr. Moore. Dynamical recognizers: real-time language recognition by analog computers. Theoretical Computer Science, 201:99-136, 1998.
• [31] Cr. Moore. Finite-dimensional analog computers: Flows, maps, and recurrent neural networks. In C.S. Calude, J. Casti, and M. J. Dinneen, editors, UnconventionalModels of Computation. Springer-Verlag, 1998.
• [32] P. Orponen. A survey of continuous-time computation theory. In D.-Z. Du and K.-I Ko, editors, Advances in Algorithms, Languages, and Complexity, pages 209-224. Kluwer Academic Publishers, 1997.
• [33] D. Perrin and J.-E. Pin. Infinite Words (Automata, Semigroups, Logic and Games), volume 141 of Pure and Applied Mathematics. Elsevier, 2004.
• [34] H. T. Siegelmann. Neural Networks and Analog Computation: Beyond the Turing Limit. Progress in Theoretical Computer Science. Springer-Verlag, 1999.
• [35] H. T. Siegelmann and S. Fishman. Analog computation with dynamical systems. Physica D, 120:214-235, 1998.
• [36] K. Sutner. Cellular automata and intermediate degrees. Theoretical Computer Science, 296(2):365-375, 2003.
• [37] K. Sutner. Universality and cellular automata. In M. Margenstern, editor, MCU 2004, number 3354 in Lecture Notes in Computer Science, pages 50-59. Springer-Verlag, 2005.
• [38] A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42(2):230-265, 1936.
• [39] K. Weihrauch. Computable Analysis. Springer-Verlag, 2000.
• [40] S. Wolfram. A new kind of science. Wolfram Media, Inc., Champaign, IL, 2002.