Tick Tock*

Implementation algorithms on a digital computer

The naive algorithm “A” for Tick Tock generation has been largely superceded by algorithm “B” based on a conjecture about emergent mechanisms in the generative process, a conjecture which is known to be true for seeds up to and including the 6-simplex, but which needs either a refactored implementation of B to validate for larger seeds, or some other form of proof.

In Perlish pseudo code where:

$a, $b, ... are nodes at t; $p, $q, ... are nodes at t+1
@nodes is a list of nodes at t
@edges is a list of node pairs representing the edges at t
%dests is a hash by node of lists of the other ends of the edges at t
@faces is a list of node triples in which each pair is an edge at t
%oppos (A) is a hash by edge of the opposite nodes of each face containing that edge
@oppos (B) is a list of nodes at t+1 created using a given edge at t
%child is a hash by triple at t of generated nodes at t+1
@tetra (A) is a list of node quadruples in which each pair is an edge at t

(It is fundamental to both algorithms that the nodes for each edge, face, etc. are kept in node order, so the edges in $a:$b:$c are $a:$b, $a:$c, $b:$c. This requires some small list sorts which have not been shown for the sake of simplicity.)

Algorithm A (data stored in file system):

@nodes and @edges are given initially

foreach $a:$b in @edges {push %dests[$a], $b; push %dests[$b], $a}
foreach $a:$b in @edges {
    foreach $c in %dests[$a] and %dests[$b] {
        push @faces, $a:$b:$c
        push %oppos[$a:$b], $c for 3 pairs in $a:$b:$c
    }
}
foreach sort @faces {push %child[$a:$b:$c], $p}
foreach $a:$b:$c=>$p in %child {
	foreach $a:$b:$d in %oppos, $d≠$c {
	    $q = %oppos[$a:$b:$d]
	    push @edges, $p:$q
    } for 3 pairs in $a:$b:$c
}

Historically this algorithm first just output bulk statistics such as node and link count, but as soon as it became obvious that interesting stuff was going on, saving the final content of @faces was added. Once significant simple structures were detected, algorithm A was reimplemented to work with 3D wireframe data and then with higher dimensional coordinates. Other reasonably simple algorithms were also developed to extract a wider range of structure statistics from the saved @faces data before a more general approach was identified.

Algorithm B (data stored in a database):

@nodes, @edges, @faces and @tetra are given initially

foreach sort @faces {push %child[$a:$b:$c], $p}
foreach $a:$b in @edges {push %dests[$a], $b; push %dests[$b], $a}
foreach $a:$b:$c:$d in @tetra {
    $p = %child[$a:$b:$c] for 4 triples in $a:$b:$c:$d
    push @edges, $p:$q unless exists @edges[$p:$q] for 6 pairs in $p:$q:$r:$s
    push @faces, $p:$q:$r for 4 triples in $p:$q:$r:$s
    push @tetra, $p:$q:$r:$s and record it as the child of $a:$b:$c:$d
}
foreach $a:$b in @edges {
	push @oppos, $child[$a:$b:$c] foreach $c in $dests[$a] and $dests[$b];
	$order = @oppos;
	while $p = shift @oppos {
	    while $q = shift @oppos { 
            push @edges, $p:$q unless exists @edges[$p:$q]
            recur ($p:$q, @oppos, 1)
        }
    }
}

Recursively generate t+1 simplex $p:$q:$r:... child of t edge $a:$b

sub recur (@curr, @todo, $deep) {
    $deep++
    while $r = shift @todo {
    	push @curr, $r
        new $simplex (order=$deep, nodes=@curr)
        $child($a:$b) = $simplex if $deep = $order;
        foreach $p in @curr {@simplex[$p, $deep]++}
        recur (@curr, @todo, $deep) if @todo
    }
}

The conjecture underpinning algorithm B is that in any graph generated by Tick Tock, not including original seeds, only edges and nodes but no faces nor higher simplexes can be shared between more than one of the simplexes in the generated graph. Of course much more than that is shared within each generated (or seed) higher order simplex, an observation which is a large part of the justification for refocusing on simplexes rather than arbitrary graphs as seeds.

Given a list of their component nodes (@oppos), the other components of a simplex can be computed by the simple recursion shown which, provided the conjecture holds for higher simplexes, does not need to check for prior creation of anything other than edges. (Enough data has been produced via algorithm A to validate the conjecture once algorithm B has been implemented for 7-simplex and higher and there is good reason to believe that any breakdown of the conjecture would be almost certain to show at 7- or 8-.)

3D projected coordinate data have now been derived from the Tick Tock database, at least for the evolution of the pentatope, the 5-simplex and the 6-simplex.

From the perspective of subsequent analysis and representation of Tick Tock evolution, Algorithm B has a further major advantage in keeping track of:

  1. structural relationships between one tick and the next, in particular the parenting of nodes by faces, tetrahedra by tetrahedra and n-simplexes (including other tetrahedra) by edges which are common to n+1 faces (as shown in the above recursion); and
  2. counts of the edges, faces, tetrahedra, etc. to which a node belongs which are the first step in determining the local node topology which becomes increasingly diverse in and beyond 6-simplex joining units, these counts having been omitted from the pseudocode, again for simplicity.

It is important to recognise that the hints of increasing algorithmic complexity emerging with algorithm B in no way reflect the Tick Tock generative process itself which remains extremely simple, but rather reflect my desire to better appreciate its unfolding by collecting as much data as could possibly be useful along the way. The basic mechanism takes one graph and creates another. Everything else is data asked of it by an observer privileged to stand outside this particular evolving series of graphs.