细胞自动机的可分类性

On the Classifiability of Cellular Automata

突出了输入和输出的惯例在描述信息内容方面与一个计算的动态性相对立的重要性 .Wolfram在许多的文章中都提到的将细胞自动机分为四类的方法 ,其中有关增长率的建议的一种自然的形式化并不能给出对所有的细胞自动机进行分类的方法 :对任意的有理数p ,q(p ,q≥ 0 )且满足p +q =1 ,存在一个细胞自动机Ap,q它在第三类中的概率为p,在第四类中的概率为q .还构造了一个以logt的速度 ,而不是以常数速度单调递增的自动机 .

This paper highlights the importance of input and output conventions in describing the information content as opposed to the dynamics of a computation.Wolfram presented in several papers conjectured classifications of cellular automata into four types,but this paper shows a natural formalization of this rate of growth suggestion which does not provide a classification of all cellular automata:for any rational p,q(p,q≥0)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.This paper also constructs an automata which grows monotonically at rate log t,rather than at a constant rate.