Fluctuation-Driven Asynchronous Cellular Automaton and Its Computational Universality
Cellular automata are widely considered as a fundamental architecture for nano-computers and quantum computers based on molecular self-assembly technology.In such a situation,the complexity of cellular automata will directly affect their efficiency of parallel distributed computing,together with the feasibility of physical implementation.The simplest model of all asynchronous cellular automata in the literatures employs three cellular states and three transition rules,which can construct all logic circuits and thus hold the computational universality equivalent to Turing machine(Turing universali-ty).In order to further reduce the complexity of universal asynchronous cellular automata,this paper proposes a new model,which requires only three cellular states and two transition rules.The smaller number of transition rules is mainly attributed to the new circuit elements and the design of large-scale distributed circuits.Different from the logic gates of synchronous circuits,the novel circuit elements can effectively utilize the random fluctuations of signals,whereby they may promise po-tential applications via nano-technologies such as single-electron tunnel transistors.In addition to Turing universality,this paper explicitly provides a scalable and distributed scheme to construct parallel logic circuits,which enables our proposed asynchronous cellular automaton to realize the same parallel computing capability as synchronous cellular automata.
国家科技期刊平台
NSTL
万方数据
