Computational problems in spatially-extended discrete dynamical systems

点击翻译按钮获取中文摘要

A complex system is typically characterized as being composed of a large number of elements whose interactions are non-linear.  One of the most interesting problems in the theory of complex systems is the complexity engineering problem, which calls for designing a complex system to perform a particular task. The main objective of the proposed research is to develop methods for designing discrete, spatially extended dynamical systems that can perform one of the simplest computational tasks, namely classifying initial configurations with respect to some given property.The motivation for this research is the density classification task, one of the most widely studied computational problems in the theory of cellular automata. Cellular automaton (CA) performing these tasks has two fixed points, one consisting of all zeros and the other, consisting of all ones. We will call these fixed points uniform. If the density of the initial configuration is less than 0.5, the automaton should converge to the first uniform fixed point (all zeros); if the density is greater than 0.5, is should converge to the second one (all ones). Although it is known that no binary CA can perform this task with 100% accuracy, many approximate solutions have been constructed. Moreover, perfect solutions involving more than one CA rule have been proposed, including two-rule solution designed by the author. Following this idea, we will study computation in multi-rule deterministic and probabilistic cellular automata, search for systems that can compute global quantities, study their dynamics in detail, discover mechanisms by which they compute, and ultimately develop methods for constructing cellular automata based systems that perform specific computations. The first part of the project will be the systematic study of binary CA, in order to describe and catalogue basins of attraction of their uniform fixed points. We will identify CA in which basins of attraction of uniform fixed points are particularly large, and we will study the structure of these basins, attempting to describe them formally. In subsequent stages, we will search for rules that have additive invariants and that have attractors in basins of attractions of uniform fixed points of rules discovered earlier. This will yield pairs of rules classifying initial configurations with respect to some property that can be described on terms of numbers of occurrences of words of finite length. We will analyze dynamics of such pairs in detail attempting to build their general theory. The theory will then be used to reverse the aforementioned process - that is, starting from the desired property, to build multi-rule dynamical system classifying configurations with respect to this property.Further ahead, we will extend the above to probabilistic rules and to nonregular topologies.