Serendip is an independent site partnering with faculty at multiple colleges and universities around the world. Happy exploring!

Deterministic and Non-deterministic Emergence: Non-deterministic Emergence

Non-deterministic Emergence


Inquiry approach 3
Non-deterministic emergence

Goal: to contribute to the ongoing creation and exploration of possibilities

Perception of time/evolution: essential as the parameter underlying emergence

Status of disorganization: the starting point and continuing contributor to exploration

If one thinks of the problem of "making sense of the world" as one of finding the "answer" then both the pattern approach and the deterministic emergence approach provide a guide to where one should be looking. The pattern approach encourages one to try and get through the noise to discern the pattern which makes explains why everything is (or should be) a particular way. The deterministic emergence approach encourages one to try and find the starting conditions and rules (itself a pattern) from which everything that is, both pattern and disorgnization, has emerged. But perhaps there is another way to "make sense of the world"? One that doesn't presume there is a secret pattern to be found either at the starting point or at the end? Perhaps one that does away with the primacy of pattern altogether?


"...we know all atoms to perform all the time a completely disorderly heat motion, which, so to speak, opposes itself to their orderly behavior and does not allow the events that happen between a small number of atoms to enrol themselves according to any recognizable laws. Only in the co-operation of an enormously large number of atoms do statistical laws begin to operate ...All the physical and chemical laws that are known to play an important part in the life of organisms are of this statistical kind; any other kind of lawfulness and orderliness that one might think of is being perpetually disturbed and made inoperative by the unceasing heat motion of the atoms" ... Erwin Schrödinger, What Is Life?, 1944

Perhaps what's important about the world isn't any particular pattern that the world imperfectly reflects, any primal pattern that it started with or is moving toward. Perhaps the world is instead an ongoing exploration of possible forms of existence, an exploration that both originates and continues to depend on randomness? If so, perhaps it is randomness that yields pattern rather than randomness being something that obscures patterns? And the reason why we see both patterns and disorganization is that without randomness there would be no patterns?

This idea is not so far-fetched as it might seem at first. It actually is random motion that drives, for example, the spreading out of cream in coffee. And it is random motion and interactions that produce pattern in chemical reactions. And the random falling apart of the sun that drives life on the earth. Furthermore, randomness in the form of mutations underpins the diversity of life on the earth is perhaps the best example of the mix of pattern and disorganization that we see all around us.

The idea that the world is about exploration, and hence that randomness rather than pattern is fundamental, also opens some intriguing new questions. Wolfram classified his cellular automata in terms of their differing abilities to create pattern and disorganization. But one might instead ask of them, how good are they at exploring? And would they be better if instead of being fully deterministic systems they incorporated some degree of randomness in their behavior?

This question can be answered with a further useful simplification of the cellular automata phenomena explored by Wolfram. Let's focus attention not on their two dimensional appearance but rather on the successive one-dimensional states they generate. Each of these is a linear array of light and dark patches. If n is the number of elements in the array, then there are 2n possible different arrays. If one is interested in the exploratory abilities of cellular automata, what one wants to know is how many of the 2n possibilities is realized by any given cellular automaton?

One can answer this question by using a modified version of Wolfram's cellular automaton that keeps track of the number of different one dimensional arrays that are generated a nine element array using any of the 256 possible rules discussed earlier. Several points quickly become clear by playing with it, as you can do using the model here (a summary of findings using this model is available here)...

  1. Some rules quickly settle into repetition of the same linear array and so don't ever exhibit most of the 2n possible outputs.
  2. Other rules never successively repeat the same linear array but do eventually begin cycling on a longer period, i.e. they repeat some linear array previously exhibited and from there on repeat a pattern of successive arrays. This is inevitable given an array of fixed length. Since there are only a finite number of possible arrays, the automaton must eventually start repeating itself.
  3. Most rules settle fairly quickly into either generating repeatedly the same one-dimensional array or into relatively short cycles. Hence most rules do not generate a significant number of the possible states, and are not good explorers.
  4. A small number of rules are distinctive in the length of their cycles and so in the number of states exhibited. Even these, however, do not generate all possible states from any of the starting conditions we have tested.
Substantially similar conclusions come from explorations of an 11 element array and a 19 element array (see here for a summary of results). It is interesting that the rule categories Wolfram developed are clearly different than the ones we would create using our criteria (% of states explored), and it would be interesting to explore further the relation between how each of the criteria categorizes particular rules. For present purposes, what is even more interesting is the following conjecture based on our observations:


there does not exist a single set of rules and initial conditions that will generate all possible linear arrays


The conjecture leads to the interesting suggestion that deterministic systems may be fundamentally limited in their exploratory capacity relative to non-deterministic ones. A linear array of elements in which the state of each element is independently and randomly varied will over time generate all possible linear arrays. That a deterministic cellular automaton won't is reminiscient of the limitations on logical systems first described by Gödel and to the similar limit on computational systems established by Turing. This observation may also provide a further reason to approach understanding the world not as a problem of locating a basic, primal pattern but rather of understanding (and participating in) the process of exploration and creation.

If making sense of the world involves ongoing exploration/creation, an interesting question is what methods/procedures facilitate that process? Random variation will generate all linear patterns but will take a long time to do it. Will some combination of deterministic and non-deterministic processes do it more rapidly? The answer to that question is yes, as you can find out for yourself using a cellular automata in which you can introduce varying amounts of randomness into the otherwise deterministic system. In this case, one can add to the cellular automaton varying amounts of indeterminacy (randomness) and see whether that enhances their exploratory capacity and whether there is some optimal level of indeterminacy that does so in different cases.

Deterministic systems, as exemplified by Wolfram's analysis of cellular automata, have enormous generative power, including the ability to generate stastically random patterns. And there is clearly explanatory power in presuming deterministic systems as a foundation for inquiry. At the same time, deterministic systems are clearly limited in their generative capabilities (see also Chaitin). Non-deterministic emergence, in which randomness is inherent in the universe, would yield phenomena difficult to make sense of using forms of inquiry that start from a presumption that randomness is itself a by-product of deterministic emergence. Accepting genuine randomness as a significant causal element in its own right may in this case be a more effective perspective for inquiry.




<< back
Non-deterministic Emergence
next >>



Posted by Paul Grobstein and Laura Cyckowski 11 Dec 2008.


Bill Huber's picture

The conjecture

Last night (4/12/10) I presented this conjecture ("there does not exist a single set of rules and initial conditions that will generate all possible linear arrays") to the Haverford College Problem Solving Group for its consideration. This is a collective of BiCo and high school students who have been meeting weekly (since fall 2005) to discuss interesting and challenging mathematical problems. They succeeded in proving the conjecture, assuming the "array" is of a fixed size (cyclically closed upon itself, as usual) and contains more than one cell. (They noted that the conjecture is false for a one-cell array, but that's not a useful model of any universe!)

The two least "interesting" states of any CA are those in which all cells are in the same condition: all on or all off. The group proved that a CA that reaches at least one of these uninteresting states cannot visit all possible states, no matter what the initial state is.

This result suggests the conjecture would be more interesting and important were it modified to exclude such trivial departures from the "perfect explorer" behavior. Many such modifications are possible; I won't go into them here, except to note that the behavior of a CA in a universe with a prime number of cells differs in some important ways from the behavior of a CA (using the same rule) in universes with composite numbers of cells. This is because composite-size universes admit states that are effectively those of strictly smaller universes; namely, states that remain the same after a nontrivial cyclic permutation of the cells. (The two uninteresting states can be seen from this point of view as being the two states of a one-cell universe, cyclically repeated.)

With the onset of end-of-semester pressures, no participant was willing to commit to writing down the details, but I'm sure several of them (one at BMC, one at HC, one at Friends' Central) are able and might be interested in discussing these ideas further. If we do manage to document the discussion, it will eventually appear on the group's Web page, which is in the process of migrating from Blackboard to the HC math department pages.

Post new comment

The content of this field is kept private and will not be shown publicly.
To prevent automated spam submissions leave this field empty.
4 + 14 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.