Computational problems in spatially-extended discrete dynamical systems

空间扩展离散动力系统中的计算问题

• 批准号: RGPIN-2015-04623
• 负责人: Fuks, Henryk
• 金额: $ 0.8万
• 依托单位: Brock University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758511
• 关键词: Computational; problems; spatially; extended; discrete

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.

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