Study On Parallel Computing Universality Of Asynchronous Cellular Automata With Von Neumann Neighborhood

Cellular Automata is a discrete model that could complete complex computing and simulate phenomena of natural. So as a kind of cellular automata, Asynchronous Cellular Automata(ACA) evolution without central clock make it more difficult to study. Emulating transition of synchronous Game of Life in Asynchronous Cellular Automata is an approach to demonstrate its computational universality. Intrinsically universal of cellular automata makes a cellular automata to simulate another cellular automata, Game of Life(GL) is one of the most famous Cellular Automata for its simple transition rules with complex behavior, such as self-replication, massive parallel computation and simulation in bionics. Especially there exists completely simulation of GL under 8-states Asynchronous Cellular Automata with Moore neighborhood and hundreds of transition rules. To simulate a cellular automata one has to simulate transition rules of cellular automata also information transfer among cells. In this paper, we design a Circuit which could compute transition rules of GL and information transfer among cells, the circuit is Delay-Insensitive Circuit(DI-Circuit) that has been proved its computing universal with computational correctness and facility in design. The DI-Circuit is so-well embedded in ACA that we can simulate GL cell by the circuit with uniformly array. We simulate evolution of GL in 5-state and 4-state ACA with von Neumann neighborhood and tens of transition rules, separately.Even though, space consumption, to emulate cell of GL, is different in different cellular automata, but the result is no different in global evolution. 4-state Cellular Automata with von Neumann neighborhood have been proved its computing ability, In this paper we can achieve the computational universal and parallel computing of 4-state ACA by simulate GL.