Chapter 3: The World of Simple Programs

Section 10: Symbolic Systems

Properties [of example symbolic system]

All initial conditions eventually evolve to expressions of the form Nest[, , m], which then remain fixed. The quantity expr //. { 0, x_[y_] 2x + y} turns out to remain constant through the evolution, so this gives the final value of m for any initial condition. The maximum is Nest[2# &, 0, n] (compare page 906), achieved for initial conditions of the form Nest[#[]&, , n]. (By analogy with page 1122 any expression can be interpreted as a Church numeral u = expr //. { 2, x_[y_] yx} = 22m, so that expr[a][b] evolves to Nest[a,b,u].) During the evolution the rule can apply only to the inner part FixedPoint[Replace[#, [x_] x] &, expr] of an expression. The depth of this inner part for initial condition [][][][][] is shown below. For all initial conditions this depth seems at first to increase linearly, then to decrease in a nested way according to

FoldList[Plus, 0, Flatten[Table[{1, 1, Table[-1, {IntegerExponent[i, 2] + 1}]}, {i, m}]]]

This quantity alternates between value 1 at position 2j and value j at position 2j - j + 1. It reaches a fixed point as soon as the depth reaches 0. For initial conditions of size n, this occurs after at most Sum[Nest[2# &, 0, i] - 1, {i, n}] + 1 steps. (See also page 1145.)

Image Source Notebooks:

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