Construction universality in purely asynchronous cellular automata

摘要

Universality in cellular automata (CAs), first studied by von Neumann, has attracted much research efforts over the years, especially for CA employing synchronous timing. This paper proposes a computation- and construction-universal CA with a von Neumann neighborhood that is updated in a purely asynchronous way, rather than by the conventional but less efficient way of simulating synchronous CAs on asynchronous CAs. The proposed asynchronous CA is capable of implementing self-reproducing machines. Our model employs strongly symmetric cells with 15 states.