Prev: Intro CA
Next: Generic CAs

TODO List
  • REF: Toffoli using CA to explore implication of discrete particles
  • REF Wolfram using 3D CA to only find transition table to gain understanding



CA as a paradigm system


(Concepts: patterns as default expectation, (evolved) patterns as not necessarily optimal, models for baseline expectations)

Cellular automata have been used as paradigm systems in various study areas:

In all cases the main defining point is the discrete nature of the formalism in combination with local interactions and complexity arising from the emergence of mesoscale patterns. For instance, Toffoli used a CA to explore the implications of discrete particles (particle concept) and contrast that to field theory (continuous variables) (REF). Wolfram even went as far as to consider the entire universe as a 3D CA in which one only had to find the transition table in order to gain full understanding (REF).

Important to note is that CAs are not bad PDEs (partial differential equations), but are instead really a different concept which allows us to focus on different aspects (such as discrete entities and local interactions). To illustrate this point we consider the following model of B-cell nodule formation in lymph nodes (Hogeweg 1989). In lymph nodes, the B cells are clumped within a mass of T cells, forming B cell modules. Both cell types enter the lymph node randomly. Two obvious questions are (i) how are these nodules formed, and (ii) why did the system evolve this pattern? This was studied with the following model:

Hogeweg_1989_lymphnodes_fig2.png
The model is a CA that represents a crosssection of a lymph node. The state of each gridpoint represents the absence/presence of a T or B cell, and the next state function is defined in terms of birth/death and influx/efflux of cells. We assume random influx of T and B cells. T cells proliferate independently while B cells only proliferate with local help of T cells. Finally cells have a constant efflux from the system.
This simple model leads to a striking observation. In the model B-cell nodules form, including higher density of B cells at the edge of nodules (i.e. where they are stimulated by T cells), as is observed in actual lymph nodes. This result demonstrates that such patterns need not be the result of an active process or mechanism (no such mechanism was included in the model), and does not require a functional explanation (i.e. how is the pattern "good" for the system?). Actually, in this case the question can be reversed: how "bad" is it for the system? Namely, patterns with clumped B cells tend to slow the B cell - T cell interactions needed for proliferation. Hence, proliferation would be optimized if the system would be well-mixed. It is however very hard to remain well mixed when proliferating locally!

This example illustrates two important points:
  • patterns need not be products of optimization or come about by some specific mechanism (here it is actually optimal to be well-mixed!)
  • patterns as default expectation: our default expectation should probably more often be non-homogeneity because interactions are local.

CAs provide a powerful modeling formalism to study the effects of local interactions in discrete entities while allowing for mesoscale patterns to arise and add to the dynamics in the system. As such they have been used as paradigm systems. Important is that such models can offer us baseline expectations for a given system.

Next: Generic CAs


References

Burks AW (1970) Essays of cellular automata, Univ. of Illinois Press.
Hogeweg P (1988) Cellular Automata as paradigm for ecological modelling. Applied mathematics and computation 27:81-100 pdf
Hogeweg P (1989) Local T-T cell and T-B cell interactions: a cellular automaton approach, Immunology Letters, Volume 22, Issue 2, 113-122. DOI
von Neumann J (1966) Theory of Self reproducing automata. University of Illinois Press 388pp
Toffoli T & Margolus N (1987) Cellular automata machines: New environment for modelling. MIT press.
Wolfram S (1984a) Cellular automata as models for complexity. Nature 311:41 Download PDF
Wolfram S (1984b) Universality and complexity in Cellular automata Physica D 10D7-12. DOI












(NOTES FROM COURSE 2006-2007)

CAs as a paradigm system
1) Experimental mathematics, artificial physics (Ulam)
2) Artificial Life (van Neumann, Langton)
3) New physics (Wolfram)
- Toffoli: physics using particle concept (based theory) to contrast with field theory (continuous variables)
- Wolfram: viewing the universe as a 3D CA: to understand the universe we just need to find the transition table.

Note: CAs are not BAD PDEs: instead it is really a different concept.

4) A paradigm system for locally interacting entities AND a more specific modelling tool (Hogeweg)

Case Study: Lymphnodes
Grid with RANDOM influx T and B cells, with proliferation cells where T grow without B but not vice-versa.
Results show B-cell modules arising including the stronger EDGE effect of nodules AND the modules tapering lengthwise into the lymph node. This demonstrates that such patterns need not require an active process. Therefore the question of how good it is for the system (i.e. functional perspective) can be reversed: could be BAD because patterns slow B-T cell interaction needed for proliferation. However it is extremely hard to remain well mixed when proliferating locally.
Point: Not always true that pattern is something optimized or comes about by specific mechanism.
Point: Our default expectation should be NON-HOMOGENEITY