Measuring complexity in automata networks: The effects of rule-space uniformity, connectivity and synchrony

Abstract

This thesis examines the nature of complexity in automata networks, and in particular, the necessary conditions for its emergence. We begin with two hypotheses: that highly restricted automata networks will not have sufficient freedom to develop complexity; and additionally that complete freedom will not promote the emergence of complexity, hence that complexity is more likely at intermediate levels of restriction. In summary this is what we have found, but in detail the situation is far more convoluted.

Three constraints are identified that control the restriction inherent in automata networks: the uniformity of rule-tables in the network, the connectivity structure between automata, and the degree of synchrony inherent in the network's update procedure. Each of these three constraints is then systematically explored followed by an examination of complexity as the three constraints are altered in parallel.

A number of complexity metrics were defined for as operational definitions. We find that quasi-random rule-tables produce on average a higher level of complexity; that as the topology of the network is changed, complexity is maximised at different regions; and that on average synchronised update produces higher levels of complexity.

The results in the final experimental chapter raise questions as to the nature of complexity. Contrary to our expectations the different metrics find complexity in different regions of the constraint space. There are two possible perspectives on this. One is to conclude that complexity is inherently a multi-faceted concept, and that different regions of the constraint space may generate complexity in different ways. The alternative, of course, is to conclude that our metrics do not measure complexity at all; we believe, however, our arguments show that the metrics do in fact measure something corresponding to natural definitions of complexity.

Our overall conclusions are that constraints shape the 'type' of complexity observed in networks, and that this behaviour is best explained as understanding the nature of complexity to be a multi-faceted phenomenon, not as a single property of a system. Furthermore, complexity is not a robust property; small changes in the restrictive parameters can dramatically affect the complexity values obtained.