User menu

Turing universality in dynamical systems

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
  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)