Computational problems in spatially-extended discrete dynamical systems

复杂系统的典型特征是由大量相互作用非线性的元素组成。 复杂系统理论中最有趣的问题之一是复杂性工程问题，它要求设计一个复杂的系统来执行特定的任务。所提出的研究的主要目标是开发设计离散的，空间扩展的动力系统，可以执行最简单的计算任务之一，即相对于一些给定的属性的初始配置进行分类的方法。 这项研究的动机是密度分类任务，在细胞自动机理论中研究最广泛的计算问题之一。执行这些任务的元胞自动机（CA）有两个不动点，一个由全0组成，另一个由全1组成。我们称这些不动点为一致不动点。如果初始配置的密度小于0.5，自动机应该收敛到第一个一致不动点（全零）;如果密度大于0.5，它应该收敛到第二个一致不动点（全一）。虽然它是已知的，没有二进制CA可以执行这个任务的100%的准确性，许多近似的解决方案已经构建。此外，已经提出了涉及多个CA规则的完美解决方案，包括作者设计的两规则解决方案。遵循这一思想，我们将研究多规则确定性和概率性细胞自动机的计算，寻找可以计算全局量的系统，详细研究它们的动态，发现它们计算的机制，并最终开发用于构建基于细胞自动机的系统的方法，执行特定的计算。 该项目的第一部分将是系统的研究二CA，以描述和编目盆地的吸引力，他们的统一固定点。我们将确定CA中的一致不动点的吸引盆地特别大，我们将研究这些盆地的结构，试图正式描述它们。 在随后的阶段中，我们将搜索具有加性不变量的规则，以及在之前发现的规则的一致不动点的吸引盆中具有吸引子的规则。这将产生对初始配置进行分类的规则对，这些初始配置相对于可以根据有限长度的单词的出现次数来描述的某些属性。我们将详细分析这种对的动力学，试图建立它们的一般理论。然后，该理论将被用来扭转上述过程-也就是说，从所需的属性，以建立多规则动态系统分类配置相对于此属性。 进一步地，我们将把上面的扩展到概率规则和非正则拓扑。

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.