On the classifiability of cellular automata

被引：8
作者：
Baldwin, JT
Shelah, S
机构：
[1] Univ Illinois, Dept Math Stat & Comp Sci, Chicago, IL 60680 USA
[2] Hebrew Univ Jerusalem, Dept Math, IL-91904 Jerusalem, Israel
[3] Univ Wisconsin, Madison, WI USA
来源：
THEORETICAL COMPUTER SCIENCE | 2000年 / 230卷 / 1-2期
基金：
美国国家科学基金会;
关键词：
classification; cellular automata; Turing machines;
D O I：
10.1016/S0304-3975(99)00042-0
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Based on computer simulations Wolfram presented in several papers conjectured classifications of cellular automata into four types. We show a natural formalization of his rate of growth suggestion does not provide a classification (even probabilistically) of all cellular automata: For any rational p,q, 0 less than or equal to p, q with p + q = 1, there is a cellular automata A(p,q) which has probability p of being in class 3, probability q of being in class 4. We also construct an automata which grows monotonically at rate log t, rather than at a constant rate. (C) 2000 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：117 / 129
页数：13
相关论文
共 9 条
1