Design on the Fly:
experiments with complex systems

Tony Smith

TransForum developer and internet analyst

Complex systems researcher

Only 50 years ago

Perl into the unknown

Simple begets complex

Towards a research program

Beyond cellular automata

The simplest possible rule

The Tick Tock rule

The local Tick Tock mechanism can be defined completely in two English sentences:

If you prefer pictures

Or, in a simple enough graph transformation diagram:

triangle => node, shared edge => new edge

However part of the point of this experiment was to learn to see how networks evolve by looking mostly at quick and dirty output, so there won’t be too many pretty pictures.

Just enough about simplexes

A “naive” implementation

To find out what Tick Tock might do, the basic procedure was just to run it, but first it has to be able to be seeded with a range of initial network configurations. For any value of 5:

my $nodes = 5;
my @possible; # edge pool
for (my $i = 0; $i < $nodes; $i++) {
    for (my $j = 0; $j < $i; $j++) {
        push(@possible, "$j:$i");
    }
}

fills an array with all possible undirected links between 5 nodes—a pentatope.

Chose 7 links at random

Then for nearly any value of 7, and getting comfortable with array splicing and arrays of array refs:

my $edges = 7;
my @pairs; # select edges,
my @graph; # list connected nodes by node
while (@pairs < $edges) {
    my $pick = int(@possible * rand());
    my ($picked) = splice(@possible, $pick, 1);
    push(@pairs, $picked); # select edge
    my ($p, $q) = split(/:/, $picked);
    push(@{$graph[$p]}, $q); # list linked nodes by node
    push(@{$graph[$q]}, $p);
}

provides a seed configuation ready to iterate a few ticks.

Detect triangular faces

Emulating a tick takes a couple of steps within an outer loop.
First find the triangles:

(@triples, %edges) = ();
foreach my $edge (@pairs) {
    my ($p, $q) = split(/:/, $edge); # $p should always be < $q
    my (@plist, @qlist) = (); # find nodes joined to $p and $q
    foreach (@{$graph[$p]}) {push(@plist, $_) if $_ > $q}
    foreach (@{$graph[$q]}) {push(@qlist, $_) if $_ > $q}
    for (my $i = 0; $i < @plist; $i++) {
        for (my $j = 0; $j < @qlist; $j++) {
            if ($plist[$i] == $qlist[$j]) { # joined to both
                my $r = $plist[$i];
                push(@triples, "$p:$q:$r"); # triangular face
                push(@{$edges{"$p:$q"}}, $r); # list third
                push(@{$edges{"$p:$r"}}, $q); # vertices
                push(@{$edges{"$q:$r"}}, $p); # by edge
}   }   }   }

Next tick’s nodes and edges

then generate the next set of nodes and edges:

my @next = sort { # ordering helps spot persistent patterns
    my @a = split(/:/, $a);
    my @b = split(/:/, $b);
    $a[0] == $b[0] ? $a[1] == $b[1] ?
        $a[2] <=> $b[2] : $a[1] <=> $b[1] : $a[0] <=> $b[0];
} @triples;
%index = (); # new node numbers for old triangular faces
for (my $i=0; $i < @next; $i++) {$index{$next[$i]} = $i}
@pairs = (); # new edges
@graph = (); # list connected nodes by node
for (my $i = 0; $i < @next; $i++) {
    my $picked = $next[$i];
    my ($p, $q, $r) = split(/:/, $picked);
    pair($p, $q, $r, $i); # detect adjacent faces (new edges)
    pair($p, $r, $q, $i);
    pair($q, $r, $p, $i);
}

Stitching it all together

which needs a subroutine that, in its naive form, detects each pair of adjacent triangles twice, once from each side of their common edge:

sub pair { # detect adjacent faces (new edges)
    my ($p, $q, $r, $i) = @_;
    foreach (@{$edges{"$p:$q"}}) {
        unless ($_ == $r) { # ignore current face
            my $triple = join(':', sort {$a <=> $b} ($p, $q, $_));
                # adjoining face
            my $j = $index{$triple}; # new node number for face
            push(@pairs, "$i:$j") if $i < $j; # new edge
            push(@{$graph[$i]}, $j); # list linked nodes by node
}   }   }

To iterate the basic tick emulation from the preceding slides just add looping, termination and reporting.

Modest early expectations

The experiment begins

Starting with $nodes = 5 and $edges = 7 we get 4 distinct results:

[A] tick 1 (2 nodes, 1 edges):                         *
  node edges: 1 x 2 new nodes                         /|\
  edge faces: 1 x 4 old edges, 2 x 1                 *—+—*
[B] 1 (3, 2):                           *———*———*     \ /
  node edges: 1 x 2, 2 x 1               \ / \ /       *
  edge faces: 1 x 5, 2 x 2                *———*
[C] 1 (3, 3):                   *———
  node edges: 2 x 3            /|\  \
  edge faces: 1 x 6, 3 x 1    * | *  *
    2 (1, 0):                  \|/  /     *
  node edges:                   *———     / \
  edge faces: 1 x 3                     *———*
[D] 1 (4, 6):             *
  node edges: 3 x 4      /|\          *
  edge faces: 2 x 6     *—+—*———*    /|\
    2 (4, 6):            \|/        *—+—*
  node edges: 3 x 4       *          \|/
  edge faces: 2 x 6                   *

Deeper into detours

BBEdit and OS X’s Terminal

What was going on?

For $nodes = 5 and $edges = 10 @next stabilises to:

0:3:4 1:12:13 2:23:24 3:4:6 3:4:9 3:5:6 3:6:9 3:8:9 4:6:7 4:6:9 
4:9:10 6:9:11 12:13:15 12:13:18 12:14:15 12:15:18 12:17:18 
13:15:16 13:15:18 13:18:19 15:18:20 21:36:37 22:46:47 23:24:26 
23:24:29 23:25:26 23:26:29 23:28:29 24:26:27 24:26:29 24:29:30 
26:29:31 32:36:38 33:46:48 34:36:40 35:46:49 36:37:38 36:37:40 
36:38:40 37:38:39 37:38:40 37:40:41 38:40:42 43:47:48 44:47:49 
45:48:49 46:47:48 46:47:49 46:48:49 47:48:49

which on careful inspection reveals 5 tetrahedra (3:4:6:9 12:13:15:18 23:24:26:29 36:37:38:40 46:47:48:49) each associated with 6 other “flag” nodes.

Some slightly larger seeds led to run away growth, so as the size of the dump of triangles data grew it became sensible to output @next to a file using a filename provided via $ARGV[0]

Visualising possibilities

Conceptually, Tick Tock nodes and links do not have spatial coordinates but it is easier for humans if you give them some, say via John N Huffman’s ancient ChemRote applet which uses plain text files to define, e.g. a regular tetrahedron:

CARTESIAN   4   6   MSC00000
vx(1)   1.000   1.000   1.000   1
vx(2)   1.000  -1.000  -1.000   1
vx(3)  -1.000   1.000  -1.000   1
vx(4)  -1.000  -1.000   1.000   1
ENDATOMS
  1    2
  1    3
  1    4
  2    3
  2    4
  3    4
ENDBONDS

Adding support scripts

Expect the unexpected

The power of edges

Testing boundaries

Time to refactor

Time to report

2D Projections


Density of the 5- and 6-simplex after 6 ticks, as projected from their 6D and 7D coordinate spaces to 2D.

A pause not a finish

“Missing” appendices

Life in a Tube

Rolling a tube out a few times can improve perception.

Blockades and Traps

Traps Evolve

Mapping Succession

At trap width w each trap state can be represented by a binary number < 2w and successor states calculated by some Perl:

w=1: 0→0 1→1 
w=2: 0→0 1→3 2→3 3→0 
w=3: 0→0 1→3 2→7 3→4 4→6 5→5 6→1 7→0 
w=4: 0→0 1→3 2→7 3→4 4→14 5→13 6→9 7→8 ...
 ... 8→12 9→15 10→11 11→8 12→2 13→1 14→1 15→0 

For w=4, three maps cover all succession:

5→13→1(→3→4→14→1) ..... 2 "hair", 4 loop
10→11→8(→12→2→7→8) ...... 2 hair, 4 loop
6→9→15(→0) ............ all eventually die

Loops, Dying and Hair

Some more Perl finds and counts loops, dying and hair tracks:

4:  Loops: 4x2
    Hair:  2 2
    Dies: 1 1 1 1
5:  Loops: 4 1
    Hair:  2
    Dies: 1 2 4 5 3 2 4 4
6:  Loops:
    Hair: 
    Dies: 1 3 3 5 5 7 14 10 8 2 2 2 2
7:  Loops: 12 4 1
    Hair:  18 12 10 10 6 8 4 2 4
    Dies: 1 4 4 1 1 3 5 6 4 2 2 2 2
8:  Loops: 12x2 4x3
    Hair:  55 30 30 32 16 18 12 8 4
    Dies: 1 6 8

Exhaustive Survey w≤23

Sample Survey 24≤w≤70

Monster Taming

Slowing and Stopping

Analysis and Conclusions

About this slide show

This presentation uses an adaptation of:
S5: A Simple Standards-Based Slide Show System
by Eric Meyer, available from:
http://www.meyerweb.com/eric/tools/s5/

S5 is a slide show format based entirely on XHTML, CSS, and JavaScript. With one file, you can run a complete slide show and have a printer-friendly version as well. The markup used for the slides is very simple, highly semantic, and completely accessible. Anyone with even a smidgen of familiarity with HTML or XHTML can look at the markup and figure out how to adapt it to their particular needs. Anyone familiar with CSS can create their own slide show theme. It's totally simple, and it's totally standards-driven.