Computer Science – Computational Complexity
Scientific paper
2009-10-21
Journal of Complex Systems, 19(1), 2010
Computer Science
Computational Complexity
28 pages. This version includes the conjecture relating the transition coefficient to computational universality. Camera ready
Scientific paper
A method for studying the qualitative dynamical properties of abstract computing machines based on the approximation of their program-size complexity using a general lossless compression algorithm is presented. It is shown that the compression-based approach classifies cellular automata (CA) into clusters according to their heuristic behavior, with these clusters showing a correspondence with Wolfram's main classes of CA behavior. A compression based method to estimate a characteristic exponent to detect phase transitions and measure the resiliency or sensitivity of a system to its initial conditions is also proposed. A conjecture regarding the capability of a system to reach computational universality related to the values of this phase transition coefficient is formulated. These ideas constitute a compression-based framework for investigating the dynamical properties of cellular automata and other systems.
No associations
LandOfFree
Compression-based investigation of the dynamical properties of cellular automata and other 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 Compression-based investigation of the dynamical properties of cellular automata and other systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression-based investigation of the dynamical properties of cellular automata and other systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-143899