Discrete Dynamics Lab: 1992-1999

Andrew Wuensche
Santa Fe Institute, Santa Fe, New Mexico, USA

Keywords: Software, Cybernetics, Discrete systems

Abstract Reviews current software issues. Discusses and analyses the interactive graphics program for designing, evaluation and investigation of the dynamics of discrete dynamical networks - Discrete Dynamics Lab (DDLab). Considers basics, configurations, classification, tools, design, application, neural nets, the user-interface, living with DDLab, new features and distribution. Full references are included.

Basics

Discrete Dynamic Lab (DDLab) is an interactive graphics program for designing, evaluation and investigation of the dynamics of discrete dynamical networks. This is a tool for the building of models and producing valuable results in complexity, emergent behaviours, neural networks, cognitive sciences and many aspect of theoretical biology. DDLab is aimed to assist computer scientists, physicists, mathematician, biologists and cognitive scientists on their way in the field of complex systems.

Following its name, the dynamics of discrete systems is a main object of the program. The architectural realisations of the discrete systems range from cellular automata (one-, two- and three-dimensional lattices with binary state) to Boolean networks with arbitrary connections between the elements and heterogeneous rules. All parameters of the systems are discrete: space, state and time. A model system can be imagined as a collective of finite automata connected into a network by direct couplings. Every automaton updates its current state depending on the states of other automata, at the previous time step, which are connected to it by the "wires". The update rule, a state transition rule, is represented by a look-up table or by Boolean expressions. All elements of a network update their states in parallel and synchronously (updating can also be sequential). In a typical trial some initial states are assigned to all elements of the network and the system is allowed to iterate. During the iterations the topology of network connections remains stationary. The program may iterate networks forward and backward; displays time-space patterns, and builds global transitions graphs and basins of attraction in the global space. A global transition graph of the discrete system is a directed graph, where every node uniquely represents a global state of the system and two nodes A and B are connected by an arc if the configuration corresponding to node A is transformed into the configuration corresponding to node B by the parallel application of the state transition rule to all elements of the network.

All parameters of the discrete models can be flexibly set, reviewed and changed (they can also be altered during the evolution of the system). The program provides users with various statistical measures and data gathering techniques.

In this brief review we simply enlighten several features of DDLab and some of the results obtained with help of DDLab, which are of great importance for systems theory and cybernetics, including the theory of complex systems in particular. A review like this is not the place to discuss the software in detail or to give all the results that may be obtained in such different and numerous fields. Therefore, a list of relevant publications is provided to which the interested reader may refer.

Garden-of-Eden configurations

A configuration C of a discrete system is a non-constructible configuration, or Garden-of-Eden configuration, if there is no configuration of the system that can be transformed into C by applying the state transition rules to the elements of the system (Moore, 1962). The leaves of the global transition graphs represent the Garden-of-Eden configurations. How do we use DDLab to investigate the relationship between modes of space-time dynamics of the discrete systems and the amount of Garden-of-Eden configurations? From the profile of the in-degree histogram for various classes of transition rules (Wuensche, 1999) we can infer that the rules with a very high frequency of the Garden-of-Eden configurations are responsible for ordered dynamics. The rules with a low number of Garden-of-Eden configuration produce chaotic-like space-time behaviour. The complex rules are somewhere in between. DDLab was successfully applied to the construction of hierarchies of the cellular automata rules, which exhibit various sets of the non-constructible blocks of cell states. Moreover, it was demonstrated that unreachable states of one-dimensional neural networks, population systems and minimalist multi-agent collectives can be detected and analysed in DDLab, subject to careful encoding (Adamatzky, 1999).

Classification of cellular automata

Both Wolfram's idea (Wolfram, 1984) and Langton's conjecture (Langton, 1990) found their place in the expressive capabilities of DDLab. Fine tuning of the local transition rules allows the user to observe space-time patterns corresponding to ordered dynamics (the system falls in a spatially homogeneous state or a short cycle of periodic patterns), complex dynamics (localised interacting structures, or gliders, emerge in the evolution, some propagate others remain stationary) and chaotic dynamics (the behaviour of the system is unpredictable, chaotic and aperiodic). Several parameters provide a useful guide to the user wishing to investigate the hierarchy of behavioural complexity in DDLab: the lambda parameter (Langton, 1990), the Z parameter (Wuensche and Lesser, 1992), the Garden-of-Eden density, the profile of the in-degree histograms, and Derrida plots (Derrida and Stauffer, 1986). Input-entropy is another measure incorporated in DDLab for the automatic classification of discrete dynamical systems (Wuensche, 1999). It is calculated by keeping track of the frequency ("look-up frequency") of the updates of the rule-table. In the automatic method for classifying transition rules, the mean input-entropy is plotted against the standard deviation of the input-entropy (Wuensche, 1999). In the diagram the chaotic rules are concentrated in the domains corresponding to maximal mean entropy and lowest standard deviation. Ordered rules span along the domain with near-zero standard deviation and lower values of mean entropy. The complex rules are scattered in the large domain of relatively high values of standard deviation; the domains are projected quite uniformly on the mean entropy axis.

Tools for investigation of computation universality

A system is dynamically computation universal if it realises a functionally complete system of Boolean functions, namely implements universal logical gates in its dynamics. Usually it is assumed that binary signals travel in space and perform computation by colliding with other travelling signals (Adamatzky, 1998). The billiard ball model (Fredkin and Toffoli, 1982) is a classic example. The theory and application of particle machines (Steiglitz et al., 1988; Squier and Steiglitz, 1994) are even more attractive; there the particles propagate and compute as a result of collisions, and the units of information are encoded in the vector states of the particles. In cellular automata models quanta of information are represented by gliders (Berlekamp et al., 1982). The DDLab software program presents an efficient automatic method for finding complex rules of cellular automata that exhibit rich glider dynamics. Methods for filtering domains (Hanson and Crutchfield, 1997) in space-time patterns form the most rigorous tool for the visual detection of gliders, and subsequent selection of glider rules. In DDLab forward and backward filtering can be done "online" while the cellular automaton evolves, for any rule. Also, having established the relationship between complex rules and movable localised structures, we can apply the full power of the automatic classification of cellular automata to search for the complex rules, which support gliders, and hence are computation universal.

Design of automata networks

This is probably the oldest and still not completely solved problem of systems and automata theory. Given a time sequence of automaton states, find the minimal automaton that realises such a sequence (Adamatzky, 1997). The problem was extended in DDLab toward the "inverse problem" of automata networks. Given the basin of attraction field, find the minimal network corresponding to this map. In DDLab this is done via reduction of the fully connected network to a network with the "effective" degree of connections.

Application to genetic networks

Genes in cells control each others activity through the coding of transcription factors, maintaining the different patterns of gene expression that make up the different cell types in a developing organism. In this way genes can either express or suppress the activity of some other genes. A Boolean network represents the dependence relations between the genes. An element of the network is a gene, which takes one of two states: active or inactive. Setting up the relations between the genes we obtain a model of the genetic regulatory network (Kauffman, 1993). DDLab helps us to look at genetic regulatory networks as discrete dynamical systems. From this point of view the outcomes of the architecture of the genetic networks become more understandable. The analogies are quite explicit: attractors of network dynamics represent cell types whereas the trajectories of the global evolution of the network portray pathways of differentiation within a given cell (Kauffman, 1993; Somogyi et al., 1997).

Neural nets and cognition

A Boolean network can certainly be seen as a reduced to bare bones model of a neural network. A neuron takes two states: excited and rest; it become excited if some of its neighbours (nodes connected to the neuron in the network) are excited. In the Boolean network model the activities of the neurons are synchronised, i.e. their states are updated in parallel. If we prefer to use synaptic terminology then we can assume that neurons taking a 1 state send excitatory signals to their neighbours, while neurons in the 0 states send inhibitory signals. Neural nets are usually open systems; the incoming and outgoing terminals can be easily arranged in the model. The attractor basins and sub-trees of the Boolean networks can represent the features of neural networks responsible for the phenomenon of memory (on a high scale of abstraction). However, binary states of the neurons do not let us to go far beyond the McCulloch-Pitts paradigm (McCulloch and Pitts, 1943). The flexible wiring scheme allows us to build almost any type of simple neural circuits, including multiple-layer networks as in the brain's cortex or visual systems. In this way DDLab can be used as some kind of pre-processing CAD for an idealised evaluation of all possible aspects of the global dynamics of particular designs of neural networks.

User interface

DDLab is a scientific program written by an expert for experts. Therefore, anyone familiar only with word processors will spend a considerable amount of time learning how to navigate through numerous menus and options and how to make the program eventually produce the necessary results. However, a careful reading of the manual helps to considerably reduce the introductory period. On the other hand, strong motivation and some preliminary background in cellular automata theory would facilitate the efficient use of the program from the very beginning.

Can we live without DDLab?

Most of us do. You can certainly write a program by yourself. If you would not like to, there are several alternatives. To simply draw nice pictures of the space-time evolution of one-, two- or three-dimensional cellular automata one can use any of the numerous simulators that can be easily found on the Internet. However we have never found any cellular automata related software, other than DDLab, that produces global transition graphs. Also there are only a few good graph-drawing programs of any kind.

GraphViz, the graph visualisation software (Ellson et al., 1998), is one of them. Two programs of the packet - dot and neato - are of exact interest to us. Using dot you can draw directed graphs as hierarchies while neato is intended to draw undirected graphs using the Kamada-Kamai spring model, i.e. the graphs are aesthetically optimised. The programs display global transition graphs for small (up to ten cells) binary cellular automata but cannot handle larger ones. So, we see that even brilliant graph-drawing programs do not take into account the whole specifics of global transition graphs of discrete systems.

Anyway, in all these cases we lose the advantages of the "all-in-one" approach. And certainly we have to do a lot of "home work" if we do not use DDLab: none of the available programs implement such a detailed analysis of the discrete dynamics and topology of global transition graphs as DDLab does. That is, DDLab might be useful even for the "high-end" users and experts in complex systems.

New features

The DDLab software has been regularly updated since 1992. The new version was released at the start of 1999. The set of new features include visualisation of space-time dynamics and analysis of three-dimensional cellular automata, (up to 40 x 40 x 40 cells), flexible methods for biasing random wiring, wiring without intersection inside the neighbourhood, and filtering. Also the inverse problem of the reconstruction of the Boolean network from the global transition graph was further developed.

Distribution

The compiled software together with the manual can be downloaded from the DDLab Web sites at www.ddlab.com or www.cogs.susx.ac.uk/users/andywu/ddlab.html, where links to numerous examples and colour illustrations can also be found, as well as the manual in HTML format.

DDLab is free of charge for personal non-commercial users. For further details, and all inquires concerning licensing, research and consulting refer to the Discrete Dynamics, Inc. Web site www.ddlab.com/ddinc, or e-mail andyw@cybermesa.com

Andrew Adamatzky
Intelligent Autonomous Systems Lab,
University of the West of England, Bristol, UK

References

Adamatzky, A. (1997), "Automatic programming of cellular automata: identification approach", Kybernetes, Vol. 26, pp. 126-39.
Adamatzky, A. (1998), "Universal dynamical computation in multidimensional excitable lattices", Int. J. Theor. Phys., Vol. 37, pp. 3069-108.
Adamatzky, A. (1999), "Nonconstructible blocks in 1D cellular automata: minimal generators and natural systems", Appl. Math. Computation, Vol. 99, pp. 77-91.
Berlekamp, E., Conway, J. and Guy, R. (1982), Winning Ways, Vol. 2, Academic Press, New York, NY.
Derrida, B. and Stauffer, D. (1986), "Phase transitions in two-dimensional Kauffman cellular automata", Europhys. Lett., Vol. 2, pp. 739.
Domain, C. and Gutowitz, H., "The topological skeleton of cellular automaton dynamics", Physica D, Vol. 103, pp. 155-68.
Ellson, J., Gansner, E., Koutsofios, E. and North, S. (1998), "GraphViz. tools for viewing and interacting with graph diagrams", AT&T Laboratories, (www.research.att.com/sw/tools/graphviz/).
Fredkin, E. and Toffoli, T. (1982), "Conservative logic", Int. J. Theor. Phys., Vol. 21, pp. 219-53.
Hanson, J.E. and Crutchfield, J.P. (1997), "Computational mechanics of cellular automata", Physica D, Vol. 103, pp. 169-89.
Kauffman, S.A. (1993), The Origin of Order, Oxford University Press, Oxford.
Langton, C.G. (1990), "Computation at the edge of chaos: phase transition and emergent computation", Physica D, Vol. 42, pp. 12-37.
McCulloch, W.S. and Pitts, W. (1943), "A logical calculus of the ideas immanent in nervous activity", Bull. Math. Biophys., Vol. 15, pp. 115-26.
Moore, E.F. (1962), "Machine models of self-reproduction", Proc. Symp. Appl. Math., Vol. 14, pp. 17-33.
Somogyi, R., Fuhrman, S., Askenazi, M. and Wuensche, A. (1997), "The gene expression matrix: Towards the extraction of genetic network architectures", Nonlinear Analysis - Theory, Methods and Applications, Vol. 30, pp. 1815-24.
Steiglitz, K., Kamal, I. and Watson, A. (1988), "Embedded computation in one-dimensional automata by phase coding solitons", IEEE Trans. Comp., Vol. 37, pp. 138-45.
Squier, R.K. and Steiglitz, K. (1994), "Programmable parallel arithmetic in cellular automata using a particle model", Complex Syst., Vol. 8, pp. 311-23.
Wolfram, S. (1984), "Universality and complexity in cellular automata", Physica D, Vol. 10, pp. 1-35.
Wuensche, A. (1994), "The ghost in the machine: basins of attraction of Random Boolean networks", in Artificial Life III, Santa Fe Institute of Studies in the Sciences of Complexity, Addison-Wesley, Reading, MA.
Wuensche, A. (1999), "Classifying cellular automata automatically; finding gliders, filtering, and relating space-time patterns, attractor basins, and the Z parameter", Complexity, Vol. 4, pp. 47-66.
Wuensche, A. and Lesser, M.J. (1992), The Global Dynamics of Cellular Automata; An Atlas of Basin of Attraction Fields of One-Dimensional Cellular Automata, Santa Fe Institute Studies in the Sciences of Complexity, Addison-Wesley, Reading, MA.