Emulation of dynamical systems within cellular automata

元胞自动机内动力系统的仿真

• 批准号: 229162-2006
• 负责人: Yassawi, Reem
• 金额: $ 0.73万
• 依托单位: Trent University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2006
• 资助国家: 加拿大
• 起止时间: 2006-01-01 至 2007-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=339949
• 关键词: Emulation; dynamical; systems; within; cellular

A cellular automaton is a deterministic dynamical system where elements are discrete lattices, each cell of the lattice takes a value from a finite alphabet, and a configuration evolves according to some local interaction rule. Thus cellular automata lend themselves to computational technologies. A subsystem of the cellular automaton is a set which is invariant under the action of the automaton. In this proposal we study what kinds of abstract dynamical systems can be emulated by a cellular automaton. For example given a self-similar system, can one find a cellular automaton, and a subsystem of that automaton which is "identical" to the self-similar system? The motivation behind this proposal is the notion that some cellular automata can be capable of "universal computation".

元胞自动机是一个确定性的动力系统，其中的元素是离散的晶格，晶格的每个单元从有限的字母表中取一个值，一个构型根据某种局部相互作用规则进化。因此，元胞自动机为计算技术提供了便利。元胞自动机的一个子系统是一个在自动机作用下不变的集合。在这个方案中，我们研究了什么样的抽象动力系统可以用元胞自动机来模拟。例如，给出一个自相似系统，人们能找到一个元胞自动机，以及该自动机的一个子系统与自相似系统“相同”吗？这一提议背后的动机是这样一个概念，即一些元胞自动机能够进行“通用计算”。