Notes

Chapter 3: The World of Simple Programs

Section 5: Substitution Systems


Growth rates [in substitution systems]

The total number of elements of each color that occur at each step in a neighbor-independent substitution system can be found by forming the matrix m where m[[i, j]] gives the number of elements of color j+1 that appear in the block that replaces an element of color i+1. For case (c) above, m = {{1, 1}, {1, 0}}. A list that gives the number of elements of each color at step t can then be found from init . MatrixPower[m, t], where init gives the initial number of elements of each color—{1, 0} for case (c) above. For large t, the total number of elements typically grows like λ^t, where λ is the largest eigenvalue of m; the relative numbers of elements of each color are given by the corresponding eigenvector. For case (c), λ is GoldenRatio, or (1+Sqrt[5])/2. There are exceptional cases where λ ==1, so that the growth is not exponential. For the rule {0->{0, 1}, 1->{1}}, m = {{1, 1}, {0, 1}}, and the number of elements at step t starting with {0} is just t. For {0->{0, 1}, 1->{1, 2}, 2->{2}}, m = {{1, 1, 0}, {0, 1, 1}, {0, 0, 1}}, and the number of elements starting with {0} is (t^2 - t + 2)/2. For neighbor-independent rules, the growth for large t must follow an exponential or an integer power less than the number of possible colors. For neighbor-dependent rules, any form of growth can in principle be obtained.


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