Notes

Chapter 7: Mechanisms in Programs and Nature

Section 9: Origins of Simple Behavior


Nested lists

One can think of structures that annihilate in pairs as being like parentheses or other delimiters that come in pairs, as in the picture below.

A string of balanced parentheses is analogous to a nested Mathematica list such as {{{},{{}}},{}}. The Mathematica expression tree for this list then has a structure analogous to the nested pattern in the picture.

The set of possible strings of balanced parentheses forms a context-free language, as discussed on page 939. The number of such strings containing 2n characters is the n^th Catalan number Binomial[2n, n]/(n+1) (as obtained from the generating function (1 - Sqrt[1 - 4x])/(2x)). The number of strings of depth d (and thus taking d steps to annihilate completely) is given by c[{n, n}, d] - c[{n, n}, d - 1] where

c[{_, _}, -1] = 0; c[{0, 0}, _] = 1; c[{m_, n_}, _] := 0 /; n > m; c[{m_, n_}, d_] := Sum[c[{i, j}, d], {i, 0, m - 1}, {j, m - d, n - 1}]

Several types of structures are equivalent to strings of balanced parentheses, as illustrated below.


From Stephen Wolfram: A New Kind of Science [citation]