Identification of Universality Beyond Turing-completeness in an α-asynchronous Cellular Automaton
Wenli Xu, Jia Lee, Sihai Yu and Shuji Kawasaki
A cellular automaton (CA) is a bio-inspired and parallel computing paradigm, whereby how to reduce the model’s complexity but without compromising its computing power is a crucial subject. A typical example is the α-asynchronous cellular automaton (α-ACA) in (Lee. et al, 2005), which has the least complexity among all CAs of the same type and is able to implement a universal Turing machine, i.e., it is Turing complete. The reduced complexity, however, comes at a cost that makes the ACA hard to realize the full functionalities of asynchronous circuits, especially of those circuits that can process an arbitrary number of signals in parallel. Such deficiency may raise a question about the parallel computing ability of the model. Because massive parallelism is an inherent feature of a CA and constitutes the basis for simulating various complex structures, including artificial intelligent systems and life, this paper attempts to identify a further universality of the α-ACA beyond the Turing-completeness. To this end, an effective scheme is proposed to explicitly construct a large-scale asynchronous circuit out of a restricted set of elements, which enables the ACA to simulate a universal synchronous cellular automaton via time-space rescaling, rather than a universal Turing machine. As a result, the α-ACA may possibly utilize its massive parallelism into universal computations as efficiently as other synchronous CAs or bio-inspired systems.
Keywords: Cellular automaton, stochastic updating, delay-insensitive circuit, universality, simulation
DOI: 10.32908/jca.v18.230724