3.12 Rules with Mixed Arity

So far essentially all the rules we have considered have “pure signatures” of the form m_k  n_k for some arity k. Continued growth is never possible unless the right-hand side of a rule contains some relations with the same arity as appear on the left. But, for example, it is perfectly possible to have growth in rules with signatures like 1₂  2₂2₁. Such rules produce unary relations, which can serve as “markers” for the application of the rule, but cannot themselves affect how or where the rule is used:

The 634 rules with signature 1₂  1₃1₂ all show very simple behavior (as do the 2212 rules with signature 1₂  1₃1₂1₁), with not even trees being possible. But among the 7652 1₂  1₃2₂ rules there are not only many trees, but also closed structures such as:

Previously we had only seen structures like the first one above in rules that depend on more than one relation. But as this illustrates, such structures can be produced even with just a single relation on the left:

The 44,686 rules with signature 1₂  2₃1₂ cannot even produce trees. Rules with signature 1₃  2₃1₂ can produce trees, as well as closed structures similar to those seen in 1₂  1₃2₂ rules.

A minimal way to add mixed arity to the left-hand sides of rule is to introduce unary relations—but the presence of these seems to inhibit the production of any more complex forms of behavior.

Looking at mixed binary and ternary left-hand sides, none of the 1,141,692 rules with signature 1₃1₂  1₃2₂ seem to produce even trees. But rules with signature 1₃1₂  2₃2₂ readily produce structures such as:

One can go on and look at rules with higher signatures, and probably the most notable finding is that—in keeping with the Principle of Computational Equivalence [1:12]—the overall behavior seen does not appear to change at all. Here are nevertheless a few examples of slightly unusual behavior found in 2₃1₂  3₃2₂ and 2₃1₂  4₃4₂ rules: