And my results An axiom system for statements about the rule 110 cellular automaton.

Most immediately obvious is a very high level of complexity in the behavior of many systems whose underlying rules are much simpler than those of most systems in standard mathematics textbooks.

Then within Mathematica various transformations and tests were done on this expression—with for example every program in these notes being formatted and broken into lines using rules similar to Mathematica StandardForm .

And this for example allows SIS to generate higher depth formulas somewhat smaller than the minimal DNF for the first three steps of rule 30 evolution.

But if more complicated transformations are allowed—say corresponding to rules in a multiway system—the problem rapidly becomes intractable (see page 765 ).

Yet I suspect that the randomness they use is often generated by quite simple rules (see page 1011 )—so that in principle it could be predictable.

The smallest product of these numbers is 24 (compare note below), and the rule he gave in this case is: Note that these results concern Turing machines which can halt (see page 1137 ); the Turing machines that I consider do not typically have this feature.

One example of a single combinator system can be found using {s  j[j], k  j[j[j]]} , and has combinator rules (whose order matters): {j[j][x_][y_][z_]  x[z][y[z]], j[j[j]][x_][y_]  x} The smallest initial conditions in this case that lead to unbounded growth are of size 14; two are versions of those for s , k combinators above, while the third is j[j][j[j]][j[j]][j[j][j[j][j]]][j[j][j]] .

Logic circuits [from cellular automata] The rules for the cellular automaton shown here are {{0, 1, 1 | 3}  1, {0, 3, 3}  3, {1, 0, 0 | 1 | 3}  1, {1, 1, 3}  4, {1, 3, 0}  3, {1, 3, 3}  2, {2, 1, 3}  3, {2, 3, 0}  2, {2, 0, _}  4, {3, 3, 0}  3, {4, 0, 0 | 1 | 2 | 4}  2, {4, 3, 3}  3, {4, 1, 3}  1, {4, 3, 0}  4, {_, _, _}  0} The initial conditions are given by Flatten[Block[{And, Or}, Map[{0, 2 (# + 1)} &, expr, {-1}] //. {!

Representations [for symbolic expressions] Among the representations that can be used for expressions are: Typical transformation rules are non-local in all these representations.