文档摘要：元胞自动机被广泛认为是基于分子自组装技术制造量子计算机、纳米计算机的基本架构,而元胞自动机的复杂度直接影响其并行分布式计算效率以及物理实现的可行性.现有复杂度最低的异步元胞自动机使用3个元胞状态和3条变迁规则能够构造所有逻辑电路,具备与图灵机等价的计算通用性(图灵通用性).为进一步降低通用异步元胞自动机的复杂度,本文提出新型电路元件以及基于该元件的逻辑电路设计方法.不同于同步电路的逻辑门元件,新型电路元件能够有效处理信号的随机波动,对单电子隧道晶体管等纳米材料技术有积极的应用价值.据此,本文提出新的异步元胞自动机模型,该模型仅需3个元胞状态和2条规则,比现有的通用模型复杂度低.除图灵通用性外,本文通过设计大规模分布式逻辑电路,进一步证明所提的异步元胞自动机具备与所有同步元胞自动机同等的计算能力.
Abstract：Cellularautomataarewidelyconsideredasafundamentalarchitecturefornano-computersandquantumcomputersbasedonmolecularself-assemblytechnology.Insuchasituation,thecomplexityofcellularautomatawilldirectlyaffecttheirefficiencyofparalleldistributedcomputing,togetherwiththefeasibilityofphysicalimplementation.Thesimplestmodelofallasynchronouscellularautomataintheliteraturesemploysthreecellularstatesandthreetransitionrules,whichcanconstructalllogiccircuitsandthusholdthecomputationaluniversalityequivalenttoTuringmachine(Turinguniversali-ty).Inordertofurtherreducethecomplexityofuniversalasynchronouscellularautomata,thispaperproposesanewmodel,whichrequiresonlythreecellularstatesandtwotransitionrules.Thesmallernumberoftransitionrulesismainlyattributedtothenewcircuitelementsandthedesignoflarge-scaledistributedcircuits.Differentfromthelogicgatesofsynchronouscircuits,thenovelcircuitelementscaneffectivelyutilizetherandomfluctuationsofsignals,wherebytheymaypromisepo-tentialapplicationsvianano-technologiessuchassingle-electrontunneltransistors.InadditiontoTuringuniversality,thispaperexplicitlyprovidesascalableanddistributedschemetoconstructparallellogiccircuits,whichenablesourproposedasynchronouscellularautomatontorealizethesameparallelcomputingcapabilityassynchronouscellularautomata.
作者：黄鑫 李佳 葛亮 宋伟Author：HUANGXin LIJia GELiang SONGWei
作者单位：重庆大学计算机学院,重庆400044
刊名：电子学报 ISTICEIPKU
Journal：ActaElectronicaSinica
年，卷(期)：2024, 52(5)
分类号：TP301TN40
关键词：元胞自动机 异步更新 布朗运动 延迟不敏感电路 通用性
Keywords：cellularautomaton asynchronoustransition brownianmotion delay-insensitivecircuit universality
机标分类号：TP393.08TP181TQ323.7
在线出版日期：2024年7月22日
基金项目：随机波动驱动的异步元胞自动机及其计算通用性[
期刊论文] 电子学报--2024, 52(5)黄鑫 李佳 葛亮 宋伟元胞自动机被广泛认为是基于分子自组装技术制造量子计算机、纳米计算机的基本架构,而元胞自动机的复杂度直接影响其并行分布式计算效率以及物理实现的可行性.现有复杂度最低的异步元胞自动机使用3个元胞状态和3条变迁规...参考文献和引证文献
参考文献
引证文献
本文读者也读过
相似文献
相关博文
关键词：元胞自动机,异步更新,布朗运动,延迟不敏感电路,通用性,
|
|
1
