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.