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 mi, 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 + 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 (t2 - 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.



Image Source Notebooks:

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