随机波动驱动的异步元胞自动机及其计算通用性

Fluctuation-Driven Asynchronous Cellular Automaton and Its Computational Universality

元胞自动机被广泛认为是基于分子自组装技术制造量子计算机、纳米计算机的基本架构,而元胞自动机的复杂度直接影响其并行分布式计算效率以及物理实现的可行性.现有复杂度最低的异步元胞自动机使用3个元胞状态和3条变迁规则能够构造所有逻辑电路,具备与图灵机等价的计算通用性(图灵通用性).为进一步降低通用异步元胞自动机的复杂度,本文提出新型电路元件以及基于该元件的逻辑电路设计方法.不同于同步电路的逻辑门元件,新型电路元件能够有效处理信号的随机波动,对单电子隧道晶体管等纳米材料技术有积极的应用价值.据此,本文提出新的异步元胞自动机模型,该模型仅需3个元胞状态和2条规则,比现有的通用模型复杂度低.除图灵通用性外,本文通过设计大规模分布式逻辑电路,进一步证明所提的异步元胞自动机具备与所有同步元胞自动机同等的计算能力.

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 universality).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 potential 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.