Transfinite complexity

Wolfram divides CA into four classes. The first three are somewhat regular, and the last  is really complex. Such a classification  reminds of the counting system of the primitive man: One, two, three, many (infinity). Can’t we generate additional classes with different complexities?

We might apply here Cantor’s method for determining  set  cardinality. The first transfinite number is called aleph-sub-zero. It is the cardinal number of the set of positive integers, also called countably infinite.  Each CA is defined by a triplet {Rule, r, k}, where r is the number of neighbors and, k the color.

The set of positive integers may be regarded as a CA{Rule, 0, 1}. Rule means add one to the current state, no neighbors, and one color.  Next  is CA{Rule, 1, 2}. Since we  can  establish a one-to-one correspondence with the positive integers, its cardinality is aleph-sub-zero.  Rule is finite (<=256).  Some of the CA in this set  e.g., CA{rule = 30}, CA{rule = 110}, generate a complexity which belongs to  Wolfram’s class-4.  Raising {r, k} step by step, we shall soon conclude that the cardinality of all discrete CA in Wolfram’s book  is aleph-sub-zero.

None has cardinality C which is the cardinality of the set of real numbers.

One wonders, given CA{Rule[Real], r [Real], k[Real]}, might it be possible to generate complexity more complex than that generated by aleph-sub-zero CA? If so, how universal is CA{Rule 110}, which obviously cannot emulate the complexity of CA{Rule[Real], r [Real], k[Real]}?

Back to complexity index