NKS Midwest, reduction & emergence

Invariants, native primitives, and computation


Paul-Jean LeTourneau of Wolfram Research, a former student of Stuart Kaufman, gave a fine pure NKS talk in the afternoon of the first day.  I want to discuss a few of the issues it raises because they seem to me to go beyond the specific case he was analysing. 

His rule system is ECA 146, and the point he noticed in analysing it is that this rule differs from the well-known additive rule 90 only in cases of adjacent blacks within the pattern.  Which in turn are produced in rule 90 (or 146, necessarily) by runs of white of even length.  Therefore, in any region in which there are neither adjacent black cells nor even runs of white, the evolution must be identical to rule 90.  Then the idea is to track these things through various evolutions of rule 146.  And he finds persistent structures, which themselves meander about on the background, can annihilate in pairs, etc.  These are present but not obvious in the rule 146 evolution, but comparing what rule 146 and rule 90 do from the same initial lets them pop out.

What is of more general interest about this?  One question is whether these localized structures might be manipulated to get the rule to perform meaningful computations, which would be a step toward solving the “class 3 problem” in the affirmative.  The class 3 problem being the question, are there class 3 random-looking rules that are universal?  Wolfram’s principle of computational equivalence (PCE) predicts there are, but this has not been proven.  All the simple rule universality proofs to date have exploited localized structures and their predictability in constructing analogs to practical computer components.  Class 3s might have been thought to lack the necessary local stability to support programming, though PCE conjectures otherwise.  This may be of broader information-theoretic interest – class 3s are thought of as “maximum entropy” systems, and appear to be computationally irreducible.  But universality is a strictly stronger attribute than irreducibility, leaving the class 3 question – are many instances of apparent complexity reducible but not universal, or are most universal?  So this is a pure NKS issue broader than the rule system itself.

But there are others, tangential to the core concerns of NKS, perhaps, but not to philosophy and issues of reductionism.  Notice these patterns refer to invariants of the evolution of rule 146, but to invariants that exceed the scope of its native primitive states.  The case of runs of even length is a particularly fine instance of that, not being a single pattern but a whole class of them.  (Those are not, however, strictly preserved by the evolution – instead they always give rise to a black-pair particle at some point, which then is preserved, up to collisions with like particles etc).

Next notice that regions of the rule seem to behave with the same additivity as rule 90, where information always passes through unchanged, at maximum (we say, “light”) speed.  While the regions marked by non-rule-90 behaving subpatterns move more slowly, and interact in a non-information-preserving way (e.g. a particle collision leading to both ceasing, has many possible time-inverse pre-images, etc).  As though two rules were operating on the same lattice, one having the information transfer properties we associate with light, the other having the information transfer properties we associate with matter (at least, macroscopically).  But it is a single underlying rule – there are simply many possible subpatterns that behave the first way because the deviations from additivity in the rule cannot arise without special subpatterns being present.  To me this is a fine example of emergence.

Notice further that in principle the two regimes are reducible to a single underlying rule (146), but to understand its internal complex behavior it may actually be superior to decompose into a simpler rule followed “some of the time” (additive rule 90) and to analyse the behavior of the “emergent” particles (black cell pairs and their even-white-run generators) “empirically”.  Why?  Because the reducibility of the rule-90 portion of the behavior can be exploited fully, if it is separated off from the non-additive remainder.

The point is to notice that these relationships (among levels of analysis, apparent particles, reduction, simplification, “factoring” of laws, etc) can arise in a purely formal system, for entirely analytical reasons.  They are not facts about physics.  They are practical realities of formalism and analysis itself.