next up previous contents
Next: Arden's lemma Up: The Garden of Previous: Excluded states for

Symbolic equations

Diagrams can be represented by connection matrices, through which many properties of the diagram can be deduced more readily than from the diagram itself. There is another representation, in terms of regular expressions, which is often useful. To see how this works, let us try to express the diagram through a set of symbolic equations. Let nodes be represented by capital letters, links by small letters. Then the two-stage de Bruijn diagram for Rule 22 can be written in the form

In such an equation, ``products'' represent concatenation and are usually written without any explicit operator sign, and ``sums'' represent alternative choices and may be read as ``or.'' The symbol represents a null string and acts like a one in products. It is included in the equations to signify that one can get to a node by doing nothing; that is, by following a null link.

A system of equations is ``solved'' in much the same way that a system of algebraic equations would be solved. The distributive law holds, and any variable (the nodes) may be substituted by an equivalent expression. The process of elimination would eventually leave a single variable defined in terms of constants, following which the whole chain of substitutions could be unravelled to obtain the values of all the variables.

There is just one technical point, however, which concerns the procedure to be followed when the same variable occurs on both sides of an equation, as in

An attempt to write

and thence

is very suggestive but hardly justified in a system which lacks any trace of subtraction, division, infinite series, convergence, and the like.

The correct procedure is to set about a series of substitutions

and observe the general form of the result

It is the first term which refuses to disappear; in the context of arithmetic, multiplication, and a numerical a less than 1, it could be argued that its magnitude eventually becomes arbitrarily small and hence it can safely be neglected. Here the argument might run along the lines, that if the symbolic a is not the null chain, then the first term becomes arbitrarily long and can safely be ignored if we are seeking finite solutions to the symbolic equation.

The case is special, because it really doesn't define anything; any value of X whatsoever, including b, will work. On the other hand, if b is empty and a is not null, the solution must be empty because otherwise we would be requiring X to be equal to something strictly longer than itself. That, however, is a different matter.

next up previous contents
Next: Arden's lemma Up: The Garden of Previous: Excluded states for

Harold V. McIntosh