Universal emulation

Given enough states, and a willingness to interpret the evolution --- say by sampling every second generation --- any cellular automaton can be emulated by a radius automaton of the same dimension.

Unfortunately four states, the number available in a half-CAM , is insufficient; emulation experiments cannot be performed with equipment having its present configuration.

Had it been possible, emulation of a Moore automaton would have been accomplished along the following lines. Any large neighborhood can be decomposed into smaller tiles, not forgetting to make allowance for overlap. Arriving at tiles, the size of neighborhoods in a radius automaton, and stopping with individual cells, we find a large hierarchy of subtitles.

The entire collection of subtitles is to become the state set of the emulating automaton, which still requires a rule of evolution. That rule consists in promoting small tiles into larger tiles until the size of the neighborhood of the automaton to be emulated is reached. At that point, the neighborhood evolves into a single state of a single cell according to the original rule; then the process commences anew.

The scheme is simple enough, yet the number of intermediate states is quite large; in one dimension it requires six states for a (2,1) automaton --- two are the original binary states, four more are pairs. Pairs of pairs overlap to form the original three cell neighborhood, whose image can be incorporated into the rule immediately.

A second rule, to accomplish the emulation, requires that a configuration of singlets turns into a configuration of pairs, which evolves back into singlets. To see pure singlets, only odd generations ought to be consulted, but they will evolve into each other following the first rule.

The evolution of mixed configurations, being irrelevant to the emulation, may be defined according to convenience.

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx