Computer Science – Computational Complexity
Scientific paper
2004-04-08
Computer Science
Computational Complexity
23 pages; a shorter version is submitted to conference MCU 2004 v2: minor orthographic changes v3: section 5.2 (collatz functi
Scientific paper
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.
Blondel Vincent
Delvenne Jean-Charles
Kurka Petr
No associations
LandOfFree
Decidability and Universality in Symbolic Dynamical Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Decidability and Universality in Symbolic Dynamical Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decidability and Universality in Symbolic Dynamical Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-158515