Universal pattern generation by cellular automata

被引：19

作者：

Kari, Jarkko ^{[1
]}

机构：

[1] Univ Turku, Dept Math, FI-20014 Turku, Finland

来源：

THEORETICAL COMPUTER SCIENCE | 2012年 / 429卷

基金：

芬兰科学院;

关键词：

Cellular automata; Universal constructor; Pattern generation; Collatz problem;

D O I：

10.1016/j.tcs.2011.12.037

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We construct a reversible, one-dimensional cellular automaton that has the property that a finite initial configuration generates all finite patterns over its state alphabet. We also conjecture that a related cellular automaton satisfies the stronger property that every finite pattern gets generated in every position, so that the forward orbit of the finite initial configuration is dense. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：180 / 184

页数：5

共 10 条

[1]

[Anonymous], 2002, A New Kind of Science

[2] Dynamical properties of expansive one-sided cellular automata [J].