Dimension of the Cantor set in the context of cellular automata

224 Views Asked by At

I'm reading the book "Cellular Automata and Complexity" by Wolfram. On page 426 he gives a very intuitive picture showing why any cellular automaton state $\{0,1\}^\infty$, can be uniquely identified with a point in the Cantor set:enter image description here

The above construction applies to any generalized Cantor set, not just the familiar ternary one. The screenshot from wikipedia below shows an intuitive formula giving the fractal dimension of a generalized Cantor set. enter image description here

So my question: all of this seems to imply that the fractal dimension of $\{0,1\}^\infty$ completely depends on your choice of $\gamma$? Why is the fractal dimension not fixed? The reason I am asking this, is because on the next page Wolfram goes on to say: "The dimension of the Cantor set of all possible configurations for an infinite one-dimensional cellular automaton is 1. A disordered ensemble, in which each possible configuration occurs with equal probability, thus has dimension 1." How can $\{0,1\}^\infty$ have dimension 1? Does this mean that Wolfram arbitrarily sets $\gamma=0$?

Furthermore he says that irreversible time evolution causes the cellular automaton's state space to contract to an attractor that is a Cantor set with fractal dimension $<1$ and gives an example, where the top line represents $\{0,1\}^\infty$ and the lines below represent the ensemble of cellular automaton configurations on each subsequent time step:

Does this imply that time evolution of the cellular automaton simply alters the value of $\gamma$?

To summarize: the notion of fractal dimension is essential in the theory of dynamical systems, but in the case of cellular automata, it seems that this concept is meaningless since it depends of your choice of $\gamma$. The point of an attractor is that after a certain time, certain configurations in the state space are no longer accessible. However, as the attractor is a Cantor space and each Cantor space (regardless of its dimension) can be identified with $\{0,1\}^\infty$, it seems that even in the infinite time limit, all configurations remain accessible.

1

There are 1 best solutions below

6
On

Hausdorff dimension is an invariant of a metric space, not a topological space. So it depends on a choice of metric. The Cantor set, as a topological space, embeds into $\mathbb{R}$ in a number of different ways and each of these gives it a different induced metric and so a priori a potentially different Hausdorff dimension.

In other words, there is no such thing as "the fractal dimension of the Cantor set," only the fractal dimension of the Cantor set equipped with a metric, and in particular the fractal dimension of the Cantor set equipped with a particular embedding into $\mathbb{R}$ (or any other metric space).

I have no idea what notion of dimension Wolfram is referring to in the excerpt you quote.

Edit:

The point of an attractor is that after a certain time, certain configurations in the state space are no longer accessible. However, as the attractor is a Cantor space and each Cantor space (regardless of its dimension) can be identified with $\{0,1\}^\infty$, it seems that even in the infinite time limit, all configurations remain accessible.

I don't understand the details of this example but this doesn't follow. The attractor may be a smaller and different Cantor set, which is not the entire original state space.