Definition of "Cellular Automata"

Cellular Automata

Cellular automata have their origin in systems described by [John von Neumann] and [Stanislaw Marcin Ulam] in the 1940s.

Cellular automata are - by definition - dynamical systems which are discrete in space and time, operate on a uniform, regular lattice - and are characterised by "local" interactions.

Broadening

In more recent times there has been some interest in similar cellular systems which are aperiodic - or are spatially non-uniform.

One possibility is that the term "cellular automata" could be broadened to include these new systems. Another is that a new category be proposed that includes these dynamical systems. I propose the name "local automata".

For broadening

The word "cellular" does not immediately suggest a system of cells where all the cells are necessarily identical - and consequently its current technical use is misleading and counter-intuitive.

The term "cellular automata" was created before there was any significant understanding of the importance of non-uniform cellular automata - and before aperiodic tilings were well-known. If the term had been assigned in more modern times, it seems likely that aperiodic tilings would not have been neglected in the definition.

The current usage doesn't "carve nature at the joints". The non-uniform and aperiodic systems under discussion share so much with cellular automata that it makes little sense to place them in a separate category.

Those involved in working with discrete non-uniform cellular systems generally call them "non-uniform cellular automata". Similarly those developing discrete aperiodic cellular systems call give them names like "cellular automata on a quasi-crystal" and "cellular automata on Penrose tiles". They do this despite the fact that these are oxymorons under the current definition.

In fact non-uniform cellular systems are all cellular automata under today's definition anyway. I.e. every non-uniform cellular automaton is isomorphic to some uniform cellular automaton with more state per cell, and part of its state in a fixed, static configuration. Seen in this light the restriction of uniformity seems useless and superflous.

A broadening of the term would simply be a reflection of modern usage.

Against broadening

The proposed redefinition no-longer results in a clear division between dynamical systems which are cellular automata and those that are not. Being a cellular automata becomes a matter of degree - since practically all discrete systems exhibit some degree of locality - in that the maximum distance a signal travels in any time step is rarely the same as the maximum distance between any two components.

It makes the term "cellular automata" less specific - and thus less useful - just to include a few rare cases that hardly anybody is interested in anyway. Practically everyone deals with local, uniform systems. The term should reflect the most common usage.

The term is too-well established by historical usage to think about changing it at this stage - and attempts to do so would just cause confusion. The term "Local automata" is available - you can use that instead.

Okaay... but what do you really think?

I am in favour of broadening the term.

The points in favour of broadening are correct.

We don't need two slightly different definitions for local dynamical systems - which seems to be the other main option.

There's no good reason why the question of whether a system is a cellular automata or not should have a binary answer.

Non-uniform cellular automata do seem to be of significant interest.

Aperiodic tesselations are not limited to Penrose-like structures - and may gain in significance due to natural occurrence.

Historical precident should not have the last word when it comes to the definitions of terms - and I doubt much in the way of confusion would result from the change.

Questions

Q: What about spatially infinite, temporally infinite discrete, local systems where a finite number of different rules are applied on different time-steps, without the order of their application ever repeating - would those qualify as "Local automata"?

A: No - they are not.

Q: Are there any aperiodic automata that are "uniform" - in that they apply the same rule in each cell?

A: That appears to depend - in part - on whether there are any single-tile aperiodic tesselations. At the time of writing, that is an open question.