细胞自动机的可分类性

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