|
Yousuke Takada, Teijiro Isokawa, Ferdinand Peper, Nobuyuki Matsui 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. Keywords: Asynchronous cellular automata; Delay-insensitive circuits; Register machine; Construction universality; Self-reproduction doi:10.1016/j.jcss.2006.04.006 |