Dynamics of multidimensional symbolic systems

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。该项目旨在进一步加深我们对有限型（SFTs）和元胞自动机（CA）的高维移位的理解。从广义上讲，目标是描述它们的动态，并确定它们中不可能发生的动态类型。在最近的工作中，主要研究者和其他人应用递归理论和拓扑动力学的方法来描述与SFT和CA相关的一些经典动力学不变量的复杂性，例如它们的熵和方向动力学（子动力学）。该项目是该调查的继续。首席研究员希望将子动力学的分类扩展到co-rank 1行动（目前只知道co-rank 2和更高），并开始对完整动力学进行系统研究，这与从计算机科学中提取的复杂性的定量测量有关，而不是递归理论的定性测量。他还将研究SFTs，CA和其他动力系统之间的关系，特别是解决康托集上的行动可以近似由某些类型的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.