Notes

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[e, e, m], which then remain fixed. The quantity expr //. {e -> 0, x_[y_] -> 2^x + 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[#[e]&,e,n]. (By analogy with page 1122 any e expression can be interpreted as a Church numeral u=expr //. {e->2, x_[y_]->y^x}=2^2^m, 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[#, e[x_] -> x] &, expr] of an expression. The depth of this inner part for initial condition e[e][e][e][e][e] 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 2^j and value j at position 2^j-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.)


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