Delvenne, Jean-Charles
[UCL]
Kurka, Petr
[]
Blondel, Vincent
[UCL]
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.
Bibliographic reference |
Delvenne, Jean-Charles ; Kurka, Petr ; Blondel, Vincent. Decidability and universality in symbolic dynamical systems. In: Fundamenta Informaticae, Vol. 74, no. 4, p. 463-490 (2006) |
Permanent URL |
http://hdl.handle.net/2078.1/95264 |