Chapter 3: The World of Simple Programs

Section 10: Symbolic Systems

Other [symbolic systems] rules

If only a single variable appears in the rule, then typically only nested behavior can be generated—though in an example like e[x_][_] -> e[x[e[e][e]][e]] it can be quite complex. The left-hand side of each rule can consist of any expression; e[e[x_]][y_] and e[e][x_[y_]] are two possibilities. However, at least with small initial conditions it seems easier to achieve complex behavior with rules based on e[x_][y_]. Note that rules with no explicit e's on the left-hand side always give trees with regular nested structures; x_[y_] -> x[y][x[y]] (or x_->x[x] in Mathematica), for example, yields balanced binary trees.

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