Emulation of dynamical systems within cellular automata

点击翻译按钮获取中文摘要

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".