Dynamics of multidimensional symbolic systems

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。本项目旨在进一步加深我们对有限型（SFTs）和元胞自动机（CA）的高维位移的理解。广义地说，目标是描述它们的动态，并识别不可能发生在它们中的动态类型。在最近的工作中，首席研究员和其他人应用递归理论和拓扑动力学的方法来描述与SFTs和CA相关的一些经典动态不变量的复杂性，例如它们的熵和方向动力学（子动力学）。这个项目是这项调查的延续。首席研究员希望将子动力学的分类扩展到co-rank 1行动（目前只知道co-rank 2和更高的行动），并开始对完整动力学进行系统研究，这与从计算机科学中提取的复杂性的更多定量测量有关，而不是递归理论的定性测量。他还将研究SFTs， CA和其他动力系统之间的关系，特别是解决Cantor集上的哪些动作可以被某些类型的SFTs近似。该项目的重点是一类动力系统产生于无限的离散元素的集合，其中只有“附近”的元素相互作用。这些模型被广泛用作理论模型和在许多科学和工程领域的模拟，如热力学、流体动力学、准晶体理论、信息论和计算机科学，仅举几例。在这种情况下，确定这样的系统可以代表哪些动态以及它们的理论限制是什么，并确定更适合研究和使用的子类是一个基本问题。最近在这个领域有了精确的结果，这个项目的目标是在这个方向上继续研究。

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).This project aims to further our understanding of higher-dimensional shifts of finite type (SFTs) and cellular automata (CA). Broadly speaking, the goal is to describe their dynamics and identify types of dynamics that cannot occur in them. In recent work the principal investigator and others have applied methods from recursion theory and topological dynamics to describe the complexity of some classical dynamical invariants associated to SFTs and CA, such as their entropy and directional dynamics (subdynamics). This project represents a continuation of that investigation. The principal investigator hopes to extend the classification of subdynamics to co-rank 1 actions (currently only co-rank 2 and higher are known) and begin a systematic study of the full dynamics, which are related to more quantitative measures of complexity drawn from computer science rather than the qualitative ones of recursion theory. He will also study the relation between SFTs, CA, and other dynamical systems, specifically addressing which actions on the Cantor set can be approximated by certain types of SFTs.The project focuses on the class of dynamical systems arising from infinite collections of discrete elements in which only "nearby" elements interact. Such models are widely used as theoretical models and in simulation in many areas of science and engineering, such as thermodynamics, fluid dynamics, the theory of quasi-crystals, information theory, and computer science, to name just a few. In that context, it is a fundamental problem to determine which dynamics such systems can represent and what their theoretical limitations are and to identify subclasses that are more amenable to study and use. Precise results in this field have come to light recently, and this project aims to continue research in this direction.