A New Universal Cellular Automaton Discovered by Evolutionary Algorithms
A New Universal Cellular Automaton Discovered by Evolutionary Algorithms
复制标题
进化算法发现的一种新的通用元胞自动机
DOI：
10.1007/978-3-540-24854-5_16
复制
发表时间：
2004
期刊：
影响因子：
0.8
通讯作者：
Pierre Collet
中科院分区：
文献类型：
--
作者：
Emmanuel Sapin;O. Bailleux;J. Chabrier;Pierre Collet
在《元胞自动机理论的二十个问题》中，Stephen Wolfram 提出了“元胞自动机中计算普遍性和不可判定性的普遍性”。本文提供了答案的要素，因为它描述了如何使用进化算法寻找和发现生命游戏（生命）之外的另一种通用细胞自动机。本文包含一个演示，旨在表明所提出的 R 自动机既可以实现任何逻辑电路（逻辑通用性），也可以实现生命的模拟（图灵意义上的通用性）。
In Twenty Problems in the Theory of Cellular Automata, Stephen Wolfram asks “how common computational universality and undecidability [are] in cellular automata.” This papers provides elements of answer, as it describes how another universal cellular automaton than the Game of Life (Life) was sought and found using evolutionary algorithms. This paper includes a demonstration that consists in showing that the presented R automaton can both implement any logic circuit (logic universality) and a simulation of Life (universality in the Turing sense).