Cellular Automata get their Wires Crossed
This work addresses a fundamental geometric constraint in two-dimensional communication for cellular automata, providing a proof of concept for crossing channels without interference.
The paper formalizes the problem of crossing communication channels in two dimensions using cellular automata and demonstrates that it is possible to cross channels without compromising capacity. It also analyzes the efficiency of the proposed systems.
In three spatial dimensions, communication channels are free to pass over or under each other so as to cross without intersecting; in two dimensions, assuming channels of strictly positive thickness, this is not the case. It is natural, then, to ask whether one can, in a suitable, two-dimensional model, cross two channels in such a way that each successfully conveys its data, in particular without the channels interfering at the intersection. We formalize this question by modelling channels as cellular automata, and answer it affirmatively by exhibiting systems whereby channels are crossed without compromising capacity. We consider the efficiency (in various senses) of these systems, and mention potential applications.