|
|
Jia Lee*, Susumu Adachi, Ferdinand Peper, Shinro Mashiko National Institute of Information and Communications Technology, Nanotechnology Group, 588-2 Iwaoka, Iwaoka-cho, Nishi-ku. Kobe 651-2401, Japan Received 6 June 2004; received in revised form 13 October 2004 Available online 9 December 2004 |
Abstract |
| Asynchronous cellular automata (ACA) are cellular automata that allow cells to update their states independently at random times. Because of the unpredictability of the order of update, computing on ACA is usually done by simulating a timing mechanism to force all cells into synchronicity after which well-established synchronous methods of computation can be used. In this paper, we present a more effective method of computation based upon a 4-state two-dimensional ACA with von Neumann neighborhood that is based on the construction in the cellular space of delay-insensitive circuits, a special type of asynchronous circuits, whose operations are robust to arbitrary delays in operators or interconnection lines. We show that this novel ACA model can be used to construct a universal Turing machine, which suffices to prove its computational universality. ©2004 Elsevier Inc. All rights reserved. Keywords: Cellular automata; Asynchronous; Delay-insensitive circuits |