3.1 The Representation of Rules

Having introduced our class of models, we now begin to study the general distribution of behavior in them. Like with cellular automata [1:2] and other kinds of systems defined by what can be thought of as simple computational rules [1:3, 4, 5], we will find great diversity in behavior as well as unifying trends.

Any one of our models is defined by a rule that specifies transformations between collections of relations. It is convenient to introduce the concept of the “signature” of a rule, defined as the number of relations of each arity that appear on the left and right of each transformation.

Thus, for example, the rule

has signature 2₂4₂ (and involves a total of 4 distinct elements). Similarly, the rule

has signature 1₃1₂2₃2₂ (and involves 5 distinct elements).

So far, we have always used letters to indicate elements in a rule, to highlight the fact that these are merely placeholders for the particular elements that appear in the configuration to which the rule is applied. But in systematic studies it is often convenient just to use integers to represent elements in rules, even though these are still to be considered placeholders (or pattern variables), not specific elements. So as a result, the rule just mentioned can be written:

It is important to note that there is a certain arbitrariness in the way rules are written. The names assigned to elements, and the order in which relations appear, can both be rearranged without changing the meaning of the rule. In general, determining whether two presentations of a rule are equivalent is essentially a problem of hypergraph isomorphism. Here we will give rules in a particular canonical form obtained by permuting names of elements and orders of relations in all possible ways, numbering elements starting at 1, and using the lexicographically first form obtained. (This form has the property that DeleteDuplicates[Flatten[{lhs,rhs}]] is always a sequence of successive integers starting at 1.)

Thus for example, both

and

would be given in the canonical form:

From the canonical form, it is possible to derive a single integer to represent the rule. The basic idea is to get the sequence Flatten[{lhs,rhs}] (in this case {1, 2, 3, 4, 4, 5, 3, 3, 2, 4, 3, 4, 5, 1, 5, 2, 6, 7, 8}) and then find out (through a generalized pairing or “tupling” function [3]) where in a list of all possible tuples of this length this sequence occurs [4]. In this example, the result is 310528242279018009.

But unlike for systems like cellular automata [5][1:p53][6] or Turing machines [1:p888][7] where it is straightforward to set up a dense sequence of rule numbers, only a small fraction of integers constructed like this represent inequivalent rules (most correspond to non-canonical rule specifications).

In addition—for example for applications in physics—one is usually not even interested in all possible rules, but instead in a small number of somehow “notable” rules. And it is often convenient to refer to such notable rules by “short codes”. These can be obtained by hashing the canonical form of the rule, but since hashes can collide, it is necessary to maintain a central repository to ensure that short codes remain unique. In our Registry of Notable Universes [8], the rule just presented has short code wm8678.