The Didigm Reflective Cellular Automaton

November 2007, Chris Pressey, Cat's Eye Technologies

Introduction

Didigm is a reflective cellular automaton. What I mean to impart by this phrase is that it is a cellular automaton where the transition rules are given by the very patterns of cells that exist in the playfield at any given time.

Perhaps another way to think of Didigm is: Didigm = ALPACA + Ypsilax.

Didigm as Parameterized Language

Didigm is actually a parameterized language. A parameterized language is a schema for specifying a set of languages, where a specific language can be obtained by supplying one or more parameters. For example, Xigxag is a parameterized language, where the direction of the scanning and the direction of the building of new states are parameters. Didigm "takes" a single parameter, an integer. This parameter determines how many colours (number of possible states for any given cell) the cellular automaton has. This parameter defaults to 8. So when we say Didigm, we actually mean Didigm(8), but there are an infinite number of other possible languages, such as Didigm(5) and Didigm(70521).

The languages Didigm(0), Didigm(-1), Didigm(-2) and so forth are probably nonsensical abberations, but I'll leave that question for the philosophers to ponder. Didigm(1) is at least well-defined, but it's trivial. Didigm(2) and Didigm(3) are semantically problematic for more technically interesting reasons (Didigm(3) might be CA-universal, but Didigm(2) probably isn't.) Didigm(4) and above are easily shown to be CA-universal.

(I say CA-universal, and not Turing-complete, because technically cellular automata cannot simulate Turing machines without some extra machinery: TMs can halt, but CAs can't. Since I don't want to deal with defining that extra machinery in Didigm, it's simpler to avoid it for now.)

Colours are typically numbered. However, this is not meant to imply an ordering between colours. The eight colours of Didigm are typically referred to as 0 to 7.

Language Description

Playfield

The Didigm playfield, called le monde, is considered unbounded, like most cellular automaton playfields, but there is one significant difference. There is a horizontal division in this playfield, splitting it into regions called le ciel, on top, and la terre, below. This division is distinguishable — meaning, it must be possible to tell which region a given cell is in — but it need not have a presence beyond that. Specifically, this division lies on the edges between cells, rather than in the cells themselves. It has no "substance" and need not be visible to the user. (The Didigm Input Format, below, describes how it may be specified in textual input files.)

Magic Colours

Each region of the division has a distinguished colour which is called the magic colour of that region. The magic colour of le ciel is colour 0. The magic colour of la terre is colour 7. (In Didigm(n), the magic colour of la terre is colour n-1.)

Transition Rules

Definition

Each transition rule of the cellular automaton is not fixed, rather, it is given by certain forms that are present in the playfield.

Such a form is called une salle and has the following configuration. Two horizontally-adjacent cells of the magic colour abut a cell of the destination colour to the right. Two cells below the rightmost magic-colour cell is the cell of the source colour; it is surrounded by cells of any colour called the determiners.

This is perhaps better illustrated than explained. In the following diagram, the magic colour is 0 (this salle is in le ciel,) the source colour is 1, the destination colour is 2, and the determiners are indicated by D's.

002
DDD
D1D
DDD

Application

Salles are interpreted as transition rules as follows. When the colour of a given cell is the same as the source colour of some salle, and when the colours of all the cells surrounding that cell are the exact same colours (in the exact same pattern) as the determininers of that salle, we say that that salle matches that cell. When any cell is matched by some salle in the other region, we say that that salle applies to that cell, and that cell is replaced by a cell of the destination colour of that salle.

"The other region" refers, of course, to the region that is not the region in which the cell being transformed resides. Salles in la terre only apply to cells in le ciel and vice-versa. This complementarity serves to limit the amount of chaos: if there was some salle that applied to all cells, it would apply directly to the cells that made up that salle, and that salle would be immediately transformed.

On each "tick" of the cellular automaton, all cells are checked to find the salle that applies to them, and then all are transformed, simultaneously, resulting in the next configuration of le monde.

There is a "default" transition rule which also serves to limit the amount of chaos: if no salle applies to a cell, the colour of that cell does not change.

Salles may overlap. However, no salle may straddle the horizon. (That is, each salle must be either completely in le ciel or completely in la terre.)

Salles may conflict (i.e. two salles may have the same source colour and determiners, but different destination colours.) The behaviour in this case is defined to be uniformly random: if there are n conflicting salles, each has a 1/n chance of being the one that applies.

Didigm Input Format

I'd like to give some examples, but first I need a format to given them in.

A Didigm Input File is a text file. The textual digit symbols 0 through 9 indicate cells of colours 0 through 9. Further colours may be indicated by enclosing a decimal digit string in square brackets, for example [123]. This digit string may contain leading zeros, in order for columns to line up nicely in the file.

A line containing only a , symbol in the leftmost column indicates the division between le ciel and la terre. This line does not become part of the playfield.

A line beginning with a = is a directive of some sort.

A line beginning with =C followed by a colour indicator indicates how many colours (the n in Didigm(n)) this playfield contains. This directive may only occur once.

A line beginning with =F followed by a colour indicator as described above, indicates that the unspecified (and unbounded) remainder of le ciel or la terre (whichever side of , the directive is on) is to be considered filled with cells of the given colour.

Of course, an application which implements Didigm with some alternate means of specifying le monde, for example a graphical user interface, need not understand the Didigm Input Format.

Examples

Didigm is immediately seen to be CA-universal, in that you can readily (and stably) express a number of known CA-universal cellular automata in it. For example, to express John Conway's Life, you could say that colour 1 means "alive" and colour 2 means "dead", and compose something like

002002001001
222122112212 ... and so on ...
212212212121 ... for all 256 ...
222222222222 ... rules of Life ...
=F3
,
=F2
22222
21222
21212
21122
22222

Because the magic colour 7 never appears in la terre, il n'y a aucune salle dans la terre et donc tout le ciel est toujours la meme chose.

There are of course simpler CA's that are apparently CA-universal that would be possible to describe more compactly. But more interesting (to me) is the possibility for making reflective CA's.

To do this in an uncontrolled fashion is easy. We just stick some salles in le ciel, some salles in la terre, and let 'er rip. Unfortunately, in general, les salles in each region will probably quickly damage enough of the salles in the other region that le monde will become sterile soon enough.

A rudimentary example of something a little more orchestrated follows.

3333333333333
3002300230073
3111311132113
3311321131573
3111311131333
3333333333333
=F3
,
=F1
111111111111111
111111131111111
111111111111574
111111111111333
311111111111023
111111111111113

The intent of this is that the 3's in la terre initially grow streams of 2's to their right, due to the leftmost two salles in le ciel. However, when the top stream of 2's reaches the cell just above and to the left of the 5, the third salle in le ciel matches and turns the 5 into a 7, forming une salle dans la terre. This salle turns every 2 to the right of a 0 in le ciel into a 4, thus modifying two of les salles in le ciel. The result of these modified salles is to turn the bottom stream of 2's into a stream of 4's halfway along.

This is at least predictable, but it still becomes uninteresting fairly quickly. Also note that it's not just the isolated 3's in la terre that grow streams of 2's to the right: the 3's on the right side of la salle would, too. This could be rectified by having a wall of some other colour on that side of la salle, and I'm sure you could extend this example by having something else happen when the stream of 4's hit the 0 in that salle, but you get the picture. Creating a neat and tidy and long-lived reflective cellular automaton requires at least as much care as constructing a "normal" cellular automaton, and probably in general more.

History

I came up with the concept of a reflective cellular automaton (which is, as far as I'm aware, a novel concept) independently on November 1st, 2007, while walking on Felix Avenue, in Windsor, Ontario.

No reference implementation exists yet. Therefore, all Didigm runs have been thought experiments, and it's entirely possible that I've missed something in its definition that having a working simulator would reveal.

Happy magic colouring!
Chris Pressey
Chicago, Illinois
November 17, 2007