E42 Simple Discrete Dynamic Systems

Every time you press the Play button on the E42 interface, the program proves a complex theorem of logic.
Therefore each E42 output is a representation of a formal conclusion from a logical proof.
QED

Assume that there exist some number of entities relating to each other. The number of entities (here called nodes) will be indicated by N. Let each entity (node) take input from a few of the other entities (through connections with those other entities). The number of connections (inputs) that each node has will be indicated by K. In the general case, each entity could have any number of states, but in a boolean case entities take on two states. The two states are ON (state = 1) and OFF (state = 0). Imagine N small light bulbs arranged in a simple array, some of them ON and others OFF. Imagine, also, that across time individual lights will flash on and off so that as we watch the array of lights we will see twinkling patterns. What makes a particular light turn on or turn off? What leads to these patterns of twinkling lights that change over time?

The image at the right shows an illustrative example with N = 16 nodes shown in blue and a mass of (untraceable) connections shown in red. How the nodes are connected is arbitrary and will be discussed below. The figure is meant only to give a general sense that a set of nodes (blue) are richly connected to each other (red lines); the figure does not make apparent the details of those connections.

We next will consider the logic (or boolean algebra) that leads to these twinkling patterns.

Nodes. As a specific case for explaining how E42 works, consider an N, K Boolean system (e.g., Kauffman, 1993) that has N = 4 nodes and K = 2 inputs to each node. Name the four nodes, in order, A, B, C, D. Each node has two discrete states, 0 or 1. The state (0 or 1) of a node at time T+1 is determined by the relation between its two inputs at time T. The discrete time change from T to T+1 is called an iteration of the system.

Wiring. Wiring refers to how the four nodes are connected to each other--which nodes give input to which other nodes. The wiring of the 4-Node Standard system is arbitrary; its purpose is to create a simple example. Figure 1 shows the (arbitrary) connections among the four nodes of 4-Node Standard. Arrows originate in nodes that are sending input and end in nodes receiving input . Notice that node A receives input from nodes C and D, as does node B. Similarly, nodes C and D both receive input from nodes A and B. Thus, there are feedback loops between A and C, between A and D, between B and C and between B and D. A and B (as well as C and D) are not directly connected; any influence each has on the other is indirect. The same is true for C and D.

(More formally the nodes can be construed as vertices and the connections as edges.) top

Logical operators. The system is relational. The relation between a node’s K=2 inputs at time T will determine that node's future state at time T+1. In Table 1 a "0" means OFF and a "1" means ON. Table 1 shows the (arbitrarily chosen) relations that determine the T+1 state of each of the four nodes in our 4-Node Standard. While the nature of these relations can be quite general (e.g., Barabasi, 2002), in N, K systems they are typically standard logical relations. Notice in Table 1 that the state of node A at time T+1 is determined by the logical OR operator between inputs from nodes C and D at time T. Similarly inputs to B are related by the logical exclusive OR (XOR), and two inputs to C and to D are related by AND and OR respectively. The set of operators used here are arbitrary except that, after working several examples by hand, this set was found to generate and example that has characteristics that are useful for learning the main points of discrete dynamic systems.

State Vectors. To keep track of the changing states for all four nodes we define a state vector. At time T, the state vector, S(T), is defined such that the first position in the vector represents the state of A, the second position the state of B, and so on. In this way the expression S(1) = {1100} means that, at time T=1, A = 1, B = 1, C = 0, and D = 0. At any point in time, T, the state of the system (the combination of all four states of all four nodes) is fully described by S(T). For any different point in time, T", the state of the system (that is the states of all of its node) would be describe by S(T").

State Space. The state space is a matrix of all possible state vectors that can occur. In this simple system, we won't write out that matrix, but every possible state vector that can occur will be shown in the leftmost four columns of Table 2, below. top

Parameters of the System. The system is specified by the number of nodes, N, and the number of connections per node, K. It is also critically specified by the wiring diagram (Figure 1). It is further specified by the truth tables (logical relations) which determine the future state of each node in relation to the K other nodes it receives input from. Later, for more advanced systems will introduce other parameters like whether a node is self-referencing (that is, checks its own state) or not.

Variables of the System. Once a system is specified, the major variables of interest are the state vectors, S(T) and the index indicating which iteration (T) the system currently resides in. top

We have now specified the 4-Node Standard system completely. Start the system in any combination of states (i.e., in any state vector) and all future states will be fully determined.

Deterministic
State Transitions. To examine this flow of deterministic causality look at Table 2 which lists the state transitions. The left four columns (gray) define the full state space, that is, for any given time T, they list every possible state vector from {0000} to {1111}. In this simple system, there are no other combinations of states for the four nodes than those listed in the left four (gray) columns.

Pop-up Table of Logical Relations among the four nodes to help you compute the state transitions

For each row in Table 2, the state vector in the left-hand four columns at time T deterministically flows to the corresponding state vector in the right-hand four columns at T+1.
For example, Table 2 (row 9)shows that if at T the system is in state vector {1000}, where only node A is in state 1, then at T+1 the system will go to {0001} where only node D is in state 1. This transition can be derived using the logical relations in Table 1.
[The derivation might seem obvious to you; in case it is not, I will go through the steps: Given {1000} at T, at T+1 node A will change to 0 (since nodes C and D are both 0 at T). On the other hand, node D will change from state 0 at T to state 1 at T+1 because D takes on state 1 if either A or B or both are a 1, which is the case at time T.]

By similar reasoning, nodes B and C do not change states. Other state transitions in Table 2 are left to the inspection of the reader. top

Attractor Basins. Now we are in a position to describe the behavior of the system, which is characterized by three attractor basins. Examine the first line of Table 2, and note that if the 4-Node Standard system starts in state vector {0000} at T, then it remain in state {0000} at T+1, which means that at T+2 it must remain in {0000} and so on forever. The system is in an attractor basin which we will call Basin 3. The Attractor for Basin 3 has period of one: that is, it is a fixed point attractor. We also so that Basin 3 has length L=1. Basin 3 can be written as: [{0000} to repeats {0000} etc….]

Even this simple system has basins of greater complexity than Basin 3. As already noted, if the system at T is in state vector {1000} then at T+1 it moves to {0001}. Where does it go after that? Looking up {0001} in Table 2 (second row), it moves to {1100} on the next iteration, which itself transforms to {0011} on the iteration after that. But {0011} transforms into {1000} which is where we started. So the system has fallen into another basin, 2, that at has period four or length L=4, i.e., it repeats any state vector every four iterations. The Attractor Cycle of Basin 2 can be written as: [{1000} to {0001} to {1100} to {0011} to repeats {1000}etc… ]. A third basin, Basin 1, can be found in Table 2 and is shown in Figure 2(a). top

Tributaries and Attractors. Figure 2 (a, b, c) illustrates the three basins of the 4-Node Standard system. Notice that the two period four basins (2 and 1) both have one or more tributaries. A tributary (transient) is a state vector that leads directly (or indirectly through other tributaries) into a basin. A system passes through a tributary state vector only once on its way to a basin. Once in a basin, the system’s behavior cycles through the same set of state vectors.

Perturbations. Once in a basin, the system will remain there unless it is perturbed. Perturbation consists of changing one or more states in a state vector. For example if the system is in Basin 3 and something external to the system changes node A from 0 to 1, the resulting state vector {1000} means that the system has been perturbed into basin 2. Now it will cycle endlessly through the four state vectors of 2.

Similarly, if the system is in basin 2 at {1000}and at something perturbs node C from 0 to 1, the resulting state vector {1010} is a tributary of basin 1 (see Figure 2 c). On the next iteration, T+1, {1010} will transform into {1111} which will then transform at T+2, into {1011}, at T+3 into {1001}, at T+4 into {1101} and finally at T+5 back into {1111}.

E42 must be perturbed by an external influence, that is, the user. Presumably complex living systems can be perturbed by external influences and have the ability to perturb themselves.

Self-organization, Emergence, and the Origins of Order. In Figure 2 we see hints of the kind of self-organization that Kauffman proposed as the organization of order in evolution. we will discuss the idea of emergence elsewhere.

This is pretty much what Bateson meant by: " (6) The description and classification of these processes of transformation discloses a hierarchy of logical types immanent in the phenomena."

A revision of Bateson's sixth criterion is required since Emergent Levels and Logical Levels are fundamentally different. Logic levels are based on the logic of logic and emergent levels (if I may vastly summarize) are based on the logic of dreams OR on some other functional relation. (see Malloy, Grinder, and Bostic St. Clair)

A Basin's Attractor Cycle Matrix. A basin cycle matrix (B) is the ordered list of all state vectors that occur in a basin's (attractor) cycle. For example, the basin matrix for basin 1 is (it is hard to make brackets in HTML, so that part of standard matrix notation is missing):

Since a basin's attractor is circle, cycling repeatedly through all its state vectors, there is no natural state vector to call the first state vector. We have therefore taken the convention that basin matrices are rotated until they start with (in row 1) the vector with the lowest Boolean value. There is no reason for that choice except that it is easy to calculate, unique, and every basin must have one such vector. Having a standardized starting point makes finding the same basin in an archive of basin matrices much easier. It also allows us to adjust phase transitions among basins for future analyses, but such analyses don't concern us here.

The full state space of a system will include all the Attractor Cycle matrices plus all the tributaries. top

Calculation, The First Difficulty. The 4-Node-Standard example we worked with is extremely simple. While the systems we will work with are not very large as such simulations go, they often involve 100 nodes with three, four, or even five connections to each node and result in tens, even hundreds, of basins. Calculating the logic by hand in such cases is too onerous to contemplate--thus the motive for the construction of a program to do the logic.

Representation, The Second Difficulty. So our program, E42, saves us the huge cognitive load along with the time and effort of deriving complex logical proofs of the recursive, dynamic moves of a logic based system. Even skipping the sort of work demonstrated in Tables 1 and 2 above (but for much more complies cases), the results of the derivations are themselves very complex. Tables of 0's and 1's, like Table 2, don't lead to instant insight or even comprehension. And when the tables are hundreds of columns wide and thousands of rows deep, the question of representation is crucial. Representation will be considered in depth on the Representation web page, but will be briefly addressed here because some knowledge of how the results of logical derivations are represented is required to understanding pages such as the Differences in Differences page.

Nodes Frame. One solution to representation is the Node Frame which represents the theoretical nodes as a matrix of dark and light green squares twinkling on and off as the logical calculations are being made in real time. See the 4-Node Standard Exampl as Twinkling Nodes we've just analyzed.

For something as simple as the 4-Node Standard Example, the node frame may be sufficient for extracting dynamic patterns. In general we have found it to be very difficult to perceive the pattern in the flow of logic using that frame. It changes constantly over time and leaves no history. The changes in the pattern are very difficult to remember particularly if the patterns are long. For example, how can I tell if this very long pattern I am currently looking at is different from another long pattern that I saw minutes ago, and, if they are different, specifically how. One frozen moment of output from the Nodes Frame is superimposed on Figure 3 below. To see an example of nodes twinkling dynamically click on: See a second, more complex example of twinkling nodes (Requires Java Plug in)

The Flow of State Vectors. Figure 2 shows the flow of state vectors in the three basins. It is a well-organized and comprehensible figure. Why not express logical derivations in that format. The essence of Figure 2 is actually just three lists of state vectors. The easiest way to list state vectors is simply to put one on each line of list. To see how uninformative that is click here to see a list of state vectors for a system with only 36 nodes and three basins when the basin lengths are L=6, L=8, and L=32. It is very difficult to generate insights into the meaning of the logical derivations when their results are presented in that format.

Smilie 3. The name of Smilie 3 is due historically to a cross language miscommunication from Chinese to English and back. While we are fond of it (and it is buried so deeply in the code that changing it would be heavy work) you can think of it as an arbitrary name. Figure 3 shows output from Smilie 3 for the three basins of the system we have been studying, 4-Node-Standard.

A Historical Trace Smilie 3 leaves a trace of the history of the state vectors through which the system has recently passed. It replaces a 0 with a white space and a 1 with a black space. It also represents the state vectors as columns rather than rows (which is the natural format for written text).

Or in an enlarged form
(the letters A through H correspond in spirit to the numbers above):

Grid. Smilie 3 generates its output on a grid. A system's Nodes constitute the vertical dimension of the grid and Time (Iterations) constitute the horizontal dimension.

Blank Area. The blank, upper part of the grid is for special instrumentation nodes and do not concern us here, therefore since those nodes aren't active that area is empty of output.

Gray Line. The Nodes of a system always are represented below a gray horizontal line that separates them from instrumentations nodes when they are used.

Small Red rectangle. A small red rectangle occurs in Figure 3 (but not on the actual Smilie 3 output). This is to indicate first row of output (the row that corresponds to Node 1 of 4-Node-Standard system). Thus the four nodes of our example read downward from the gray line, starting with the row that has the small red rectangle.

[For your convenience click here to pop up a separate page with the Figure 2 basin structure and state vectors so you can make comparisons. You may need to re-size that page.]

1 or C (Basin 2). (The red number refers to Figure 3a while the red letter refers to Figure 3b.) The state vectors for Basin 2 are {0001, 1100, 0011, 1000}. Look between the gray line and the bottom of the grid, below the red 1 or C , to the first, leftmost, column. The top two grid squares of that column are Black (=ON); the bottom two squares are White (=OFF). This corresponds to a state vector = {1100} which is second in the list for Basin 2. The next state vector in Basin 2 is {0011}. Notice that the second column (iteration) from the top is White, White, Black, Black which corresponds to {0011}. The main trick is that state vectors are usually written as text in horizontal strings while Smilie 3 represents them as columns. The third column similarly corresponds to the next state vector. Finally the fourth column, White, White, White, Black corresponds to {0001} which finishes the cycle of the basin.

Basin Basin 3: The Space Between. In the space between A and B, and between all the other letters, the system was allowed to run four iterations in Basin Basin 3. Thus, there are four columns in which all the cells are white corresponding to {0000}.

2 or D (Basin 2) and Phase Relations. In the next four columns (beneath 2 or D ) Basin 2 runs again for four iterations. But this time it begins with {0001} and so is White, White, White, Black. Notice how a different starting point in the basin makes the visual pattern appear different. This is the issue of phase relations; the same dynamic in a different phase can appear different. Pop up Figure 3 Image

3 or B (Basin 1). The four columns under C are from Basin 1 starting with state vector {1111} and proceeding through the cycle of that basin.

4 or A (Basin 1) and Phase Relations. The four columns under D are another pass through Basin 1, this time starting at state vector {1011}. Once again, comparison with C indicates that the same dynamic expressed in a difference phase produces a different visual representation.

5 and 6: Multiple cycles. Areas E and F show multiple passes through Basins 2 and 1. Notice that a pattern is generated in multiple cycles that is not apparent in a single cycle (A through D). This is an important aspect of representation; some relations can be discerned by examining a historical trace that runs across several cycles through the basin.

7and 8: Another Phase Shift. G and H show multiple cycles through 2 and 1 again, this time starting 2 at a different phase of its cycle than at E while starting 1 in the same cycle as F. As you can see, phase shift still has a perceptual impact but not so strongly.

Phase shifts. An ancillary insight gained from this example is that phase shifts matter to human perception. Therefore having a convention (like starting all basin matrices with the lowest Boolean) allows a way of knowing what phase a basin is in (relative to the arbitrary standard).

See Smilie3 Output Dynamically. After all this formal analysis it would be instructive to actually watch the historical trace created as Smilie3 runs. Demonstration of Smilie3 for 4-Node Standard system

How the results of a long logical derivation are represented is crucial to how humans understand the meaning of the derivation and whether any insights will be gained from them. We have some hints of that at this point. A fuller discussion can be found at Representing Dynamic Relations

Criteria of Mind

(1) Mind is an aggregate of interacting parts or components.
[Nodes]
(2) The interaction between parts of mind is triggered by difference.
[Inputs to Nodes = 0 or 1 State of other Nodes]
(3) Mental process requires collateral energy.
[Other Discussions
e.g., Kauffman's Work Cycle
e.g., Grinder, Bostic & Malloy under development ]
(4) Mental process requires circular (or more complex) chains of determination.
[Boolean Net]
(5) In mental process the effects of difference are to be regarded as transforms (i.e., coded versions) of the difference which preceded them.
[TAO Transforms]
(6) The description and classification of these processes of transformation discloses a hierarchy of logical types immanent in the phenomena.
[Hierarchies of Stimulus Similarity]
[Emergence]

I shall argue that the phenomena which we call thought, evolution, ecology, life, learning occur only in systems that satisfy these criteria.
(Bateson, 1979, pp. 85, 86)
[Kauffman's Evolutionary Theory re Boolean Nets]

Morphogenic Insights.

Morphogenesis (Self-organized form) is a theory about how the actual ontological form (e.g., camouflage) comes into being in a given existential being. Suppose that a genetic change occurs in a particular being due to mutation or recombination (e.g., sexual mixing of genes). What form will that being take? Self-organizing processes inherent in the interplay of processes within that being will determine which particular pattern of form emerges. Later, selective pressures of a given environment will determine if the the being who has assumed that form gets to reproduce or not.

The insights described here are no more than what Turing described in 1952, but here perhaps they are expressed in a form that makes them more accessible to more people. The core concept is that form emerges from the interplay of nonlinear recursive processes. Most importantly, form in question is not in any way to be found in any of the processes that are interacting (they have, of course, their own form). There is nothing like the visually evocative striped patterns we're labeling here as "Zebra Stripes" anywhere in the truth tables or transition matrices of E42. What we are calling the striped form is a result of the interplay of all the logical relations as they play in unison and as they are expressed in the visual medium of the Smilie representation. In the same way, the argument goes, there is the form of a human being is nowhere to be found in the genetic code. Rather, the human form is found in the interplay of the genetic variables as they play in unisou and as they are expressed in the medium of the cells. (Remember, fetal stem cells do not know what kind of cell to become except in relation to the cells around them.)

Defeating "the Argument from Design." Turing's insight, and the insights of all the researchers on emergent systems and self-organization who have followed is profound. The emergence of complex and elegant order from processes that don't contain those levels order does not require an external, intelligent designer. The new order, as surprising and as complex as it is, is found to be a mathematical and logical consequence of the interaction of well defined processes. This does not require the universe to BE those mathematical and logical processes (this is all just a model) but assuming that the universe is a interplay of some sorts of processes then those processes themselves would be susceptible to generating such self-organized, emergent order.

Self Organization: Escaping the Infinite Regress of Reductionism. Another part of the insight is that we do not need to be caught in the infinite regress of reductionistic thinking, which, as a parody, would have us all be subatomic physistis since everything we're interested in would reduce that. The new alternative is that whole orders of form self-organize from the interplay of variables at any level. And these new orders are to be understood fully only at their own level. As Holland (1998, p. 227) states it, "When macrolaws can be fromulated, the behavior of the whole pattern can be described without recourse to the microlaws... that determine the behavior of its components."

Of course, causal reduction to a lower levels of analysis is explicitly included in this new alternative--the human form (or, in the case of E42, the zebra stripes) is caused by the interplay of the genetic (or truth table) operations. But what arises from that interplay is not to be found in those processes per se. We can eat our reductionistic cake and escape its stomach ache. A choreographer can express herself fully with the human form and not be a geneticist to do it. AND she can be a geneticist if she likes, knowing that the human form requires a genetic base. We can live in a universe of determinisic processes and we can be poets, or, at least, wish to be.

At this point we have introduced the major terms in a vocabulary that will allow a conceptual discussion of discrete dynamic systems.

Table 1. Logical relations among nodes in the "4-Node Standard" discrete dynamic system
Node A			Node B			Node C			Node D
OR			XOR			AND			OR
C at T	D at T	A at T+1	C at T	D at T	B at T+1	A at T	B at T	C T+1	A at T	B at T	D T +1
0	0	0	0	0	0	0	0	0	0	0	0
0	1	1	0	1	1	0	1	0	0	1	1
1	0	1	1	0	1	1	0	0	1	0	1
1	1	1	1	1	0	1	1	1	1	1	1

Basin(1)=		1001
		1101
		1111
		1011

Table 2. State Transition Table for the "4-Node Standard" system
T				T + 1
A	B	C	D	A	B	C	D
0	0	0	0	0	0	0	0
0	0	0	1	1	1	0	0
0	0	1	0	1	1	0	0
0	0	1	1	1	0	0	0
0	1	0	0	0	0	0	1
0	1	0	1	1	1	0	1
0	1	1	0	1	1	0	1
0	1	1	1	1	0	0	1
1	0	0	0	0	0	0	1
1	0	0	1	1	1	0	1
1	0	1	0	1	1	0	1
1	0	1	1	1	0	0	1
1	1	0	0	0	0	1	1
1	1	0	1	1	1	1	1
1	1	1	0	1	1	1	1
1	1	1	1	1	0	1	1

Table 3. Camouflage-like striped patterns
The first four columns (a to d) are four basins from the same dynamic system. The fifth column (e) is a basin from a different dynamic system.
a	b	c	d	e