User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Turing universality in dynamical systems

Primary tabs

Delvenne, Jean-Charles [UCL]

A computer is classically formalized as a universal Turing machine. However over the years a lot of research has focused on the computational properties of dynamical systems other than Turing machines, such cellular automata, artificial neural networks, mirrors systems, etc. In this talk we review some of the definitions that have been proposed for Turing universality of various systems, and the attempts to understand the relation between dynamical and computational properties of a system.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès restreint
Publication date 2006
Language Anglais
Conference "2nd Conference on Computability in Europe (CiE 2006)", Swansea Univ, Dept Comp Sci, Swansea (Wales) (Jun 30-jul 05, 2006)
Journal information "Lecture Notes in Computer Science" - Vol. 3988, p. 147-152 (2006)
Peer reviewed yes
issn 0302-9743
e-issn 1611-3349
Publisher Springer-verlag Berlin (Berlin)
Affiliation UCL - FSA/INMA - Département d'ingénierie mathématique
Links
  1. Asarin E., Bouajjani A., Perturbed Turing machines and hybrid systems, 10.1109/lics.2001.932503
  2. Asarin Eugene, Maler Oded, Pnueli Amir, Reachability analysis of dynamical systems having piecewise-constant derivatives, 10.1016/0304-3975(94)00228-b
  3. Blum Lenore, Shub Mike, Smale Steve, On a theory of computation and complexity over the real numbers: $NP$- completeness, recursive functions and universal machines, 10.1090/s0273-0979-1989-15750-9
  4. Bournez Olivier, Cosnard Michel, On the computational power of dynamical systems and hybrid systems, 10.1016/s0304-3975(96)00086-2
  5. Davis, M.D.: A note on universal Turing machines. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp. 167–175. Princeton University Press, Princeton (1956)
  6. Delvenne, J.-Ch., Kůrka, P., Blondel, V.D.: Computational universality in symbolic dynamical systems. Fundamenta Informaticae 71, 1–28 (2006)
  7. Deutsch D., Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer, 10.1098/rspa.1985.0070
  8. Gacs P., Reliable cellular automata with self-organization, 10.1109/sfcs.1997.646097
  9. Koiran Pascal, Cosnard Michel, Garzon Max, Computability with low-dimensional dynamical systems, 10.1016/0304-3975(94)90229-1
  10. Koiran Pascal, Moore Cristopher, Closed-form analytic maps in one and two dimensions can simulate universal turing machines, 10.1016/s0304-3975(98)00117-0
  11. Langton Chris G., Computation at the edge of chaos: Phase transitions and emergent computation, 10.1016/0167-2789(90)90064-v
  12. Maass Wolfgang, Orponen Pekka, On the Effect of Analog Noise in Discrete-Time Analog Computations, 10.1162/089976698300017359
  13. Mitchell, M., Hraber, P.T., Crutchfield, J.P.: Dynamic computation, and the “edge of chaos”: A re-examination. In: Cowan, G., Pines, D., Melzner, D. (eds.) Complexity: Metaphors, Models, and Reality. Santa Fe Institute Proceedings, vol. 19, pp. 497–513. Addison-Wesley, Reading (1994)
  14. Moore Cristopher, Unpredictability and undecidability in dynamical systems, 10.1103/physrevlett.64.2354
  15. Moore C, Generalized shifts: unpredictability and undecidability in dynamical systems, 10.1088/0951-7715/4/2/002
  16. Moore Cristopher, Dynamical recognizers: real-time language recognition by analog computers, 10.1016/s0304-3975(97)00028-5
  17. Moore Cristopher, Recursion theory on the reals and continuous-time computation, 10.1016/0304-3975(95)00248-0
  18. Ollinger Nicolas, The Intrinsic Universality Problem of One-Dimensional Cellular Automata, Lecture Notes in Computer Science (2003) ISBN:9783540006237 p.632-641, 10.1007/3-540-36494-3_55
  19. Pour-El Marian Boykan, Richards Ian, Computability and noncomputability in classical analysis, 10.1090/s0002-9947-1983-0682717-1
  20. Siegelmann, H.T.: Neural Networks and Analog Computation: Beyond the Turing Limit. In: Progress in Theoretical Computer Science. Springer, Heidelberg (1999)
  21. Sutner, K.: Almost periodic configurations on linear cellular automata. Fundamenta Informaticae 58(3–4), 223–240 (2003)
  22. Blondel Vincent D., Bournez Olivier, Koiran Pascal, Tsitsiklis John N., The Stability of Saturated Linear Dynamical Systems Is Undecidable, 10.1006/jcss.2000.1737
  23. Weihrauch Klaus, Computable Analysis, ISBN:9783540668176, 10.1007/978-3-642-56999-9
  24. Wolfram, S.: A new kind of science. Wolfram Media, Inc, Champaign, IL (2002)
Bibliographic reference Delvenne, Jean-Charles. Turing universality in dynamical systems.2nd Conference on Computability in Europe (CiE 2006) (Swansea Univ, Dept Comp Sci, Swansea (Wales), Jun 30-jul 05, 2006). In: Lecture Notes in Computer Science, Vol. 3988, p. 147-152 (2006)
Permanent URL http://hdl.handle.net/2078.1/59970