A New Kind Of Science by Stephen Wolfram
Questions left unassailed:
Correspondence? Say we can find ruleset(s) for some automata that imitate a known physical process. Can we class the outcomes, so that we can find borders between behaviors? Can we then look for changes in outcome classes and further test the automata-ruleset?
Composition? Do we have a model that supports composing of disparate objects (put some sugar in water, keep putting sugar in, get crystals after a while)? Or do we end up having to find automata-rulesets for each and every interaction?
In the end, it seems more a book on some cool stuff you can do with Mathematica than a start to something.
... despite the simplicity of their rules, the behavior of the programs was often far from simple. Indeed, even some of the very simplest programs that I looked at had behvior that wa as complex as anything I had ever seen...
Perhaps immediately most dramatic is that it yields a resolution to what has long been considered the single greatest mystery of the natural world: what secret it is that allows nature seemingly to effortlessly to produce so much that appears to us so complex.
Principle of Computational Equivalence: that whenever one sees behavior that is not obviously simple -- in essentially any system -- it can be thought of as corresponding to a computation of equivalent sophistication.
In class 1, the behavior is very simple, and almost all initial conditions lead to exactly the same uniform final state.
In class 2, there are many different possible final states, but all of them consist just of a certain set of simple structures that eitehr remain the same forever or repeat every few steps.
In class 3, the behavior is more complicated, and seems in many respects random, although triangles and other small-scale structures are essentially always at some level seen.
And finally, as illustrated on the next few pages, class 4 involves a mixture of order and randomness: localized structures are produced which on their own are fairly simple, but these structures move around and interact with each other in very complicated ways.
But I believe that it will be essentially impossible to find such a formulation (ruleset for automata) without already knowing the rule. And as a result, my guess is that the only realistic way to find the rule in the first place will be start from some very straightforward representation, and then just to search through large numbers of possible rules in this representation.