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]}?