Table 11: Measure Theoretical Complexities

Measures of the information content of regular grammars for sets of configurations generated by evolution from disordered initial states.

This table gives values of a probabilistic analogue of the regular language complexity of table 10, in which the nodes of regular language graphs are weighted with the probabilities that they are visited.

Starting from a disordered state in which all possible configurations occur with equal probability, irreversible cellular automaton evolution can lead to ensembles in which different configurations occur with different probabilities. These ensembles can be described by probabilistic analogues of regular languages.

All the configurations that can occur after steps correspond to possible paths through the standard regular language graphs of table 10. To account for the different probabilities of different configurations, one may weight the nodes of the graph according to the probabilities that they are visited. In terms of these probabilities, one may then compute a measure theoretical complexity , where the sum runs over all nodes in the regular language graph. The table gives estimated values for this quantity. The last digit in each estimate is subject to statistical errors.

Table and concept by Peter Grassberger (Physics Department, University of Wuppertal).

previous  l  next