This paper proposes a computationally universal square lattice asynchronous cellular automaton, in which cells have merely two states. The transition function according to which a cell is updated takes as its arguments the states of the cells at orthogonal or diagonal distances 1 or 2 from the cell. The proposed cellular automaton is inner-independent―a property according to which a cell’s state does not depend on its previous state, but merely on the states of cells in its neighborhood. Playing a role in classical spin systems, inner-dependence has only been investigated in the context of synchronous cellular automata. The asynchronous update mode used in this paper allows an update of a cell state to take place―but only so with a certain probability―whenever the cell's neighborhood states matches an element of the transition function’s domain. Universality of the model is proven through the construction of three circuit primitives on the cell space, which are universal for the class of Delay-Insensitive circuits.

doi: