基于受限生成过程模型的计算涌现分析.pdf

《基于受限生成过程模型的计算涌现分析.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第38卷第7期计算机科学Vo1．38NO．72011年7月ComputerScienceJuly2O11基于受限生成过程模型的计算涌现分析张海栗张松林陈桂生。(解放军理工大学指挥自动化学院南京210007)(解放军理工大学通信工程学院南京210007)(中国电子设备系统工程研究所北京100141)。摘要涌现描述了特定系统在超过某阈值时突然出现的现象，中间没有明显的过渡过程。提出了图灵机计算模型在时空复杂度上所表现出的计算涌现现象，引入了受限生成过程(ConstrainedGeneratingProcedure，CGP)模型

2、来描述图灵机的计算过程，通过CGP模型刻画了机制参与次数、参与深度和平均参与度等3个涌现数字特征，提出了计算涌现的CGP分析方法并在3类典型图灵机计算过程中进行了验证分析。关键词计算涌现，受限生成过程，图灵机，复杂性分析中图法分类号TP301．5文献标识码AComputationalEmergenceanditsConstrainedGeneratingProcedureModelZHANGHai—suZHANGSong-lin。CHENGui—sheng。(SchoolofCommandAutomation，PIAUni

3、versityofScienceandTechnology，Nanjing210007，China)(SchoolofTelecommunication，PIAUniversityofScienceandTechnology，Naming210007，China)0(InstituteofElectronicSystemEngineering，Beijing100141，China)。AbstractThecomplexityofcomputationalmodelscanalsoputupsomeemergencepro

4、pertiesaroundseveralcert~lincriticalvalues．ThispapersurveyedsoIrlecomputationalemergencebehaviors，andbuilttheirConstrail1e(iGeneratingProcedure(CGP)mode1．WeintroducedtheCGPmechanicparticipatingtimes，participatingdepthandaveragepartici～patingdegree，andthenanalyzedt

5、hecriticalvaluesofemergencepropertieson3typicalTuringmachinecomputationprocesses．KeywordsComputationalemergence，Constrainedgeneratingprocedure，Turingmachine，Computingconlplexity具体研究结论目前更加少见，文献[3，4，6，8]从小可计算性的1引言角度宏观地讨论了不同计算任务的涌现的筹异问题，如通过特定系统所产生的涌现现象往往随着行为机制的数量增振荡机

6、方式所构造出的停机函数不可判的计算复杂性和加和积累而“出乎意料”地表现出来。因此，如何描述、再现甚任务的计算复杂性之间的涌现区别等，但是均没有从涌现机至控制特定系统中这种看似难以重复的过程已经成为目前复理上建立完整的分析模型。杂性研究的重点]。在可计算性研究领域，基于图灵机模型基于主体(Agent)的受限生成过程模型(Constrained的计算实现过程往往也会表现出某种涌现特性一个用来GeneratingProcedureModel，CPG)最早由Holland提出／。实现+．y功能的、设计合理的图灵机计算过程是简单的，

7、而在CGP模型中，主体是对系统中产生涌现现象的各要素的概计算．72·的过程必须在．27+的简单设计上使其进一步复括，通过给主体赋予机制(Mechanism)米刻画其能动性，而机杂化(包括增加状态、跳转和步骤等)才能得到结果。如果再制间的相互作用则用于描述主体问的柑互影响。文献[1，7，将难度提高，考虑一个计算的图灵机过程，则计算的复杂9]等详细分析了与神经网络、西洋跳棋和元胞自动机相关的性将可能会成倍增加。可是，在图灵机所有这些成倍增加的几个实例，并通过CGP模型描述了其特征和涌现现象。计算复杂性后面，起支撑作用的不过仅仅

8、是4条简单指令：写不论在可计算性理论还是在计算涌现中，诸如图灵机、算0，写1，左移和右移。随着计算任务的多样化和复杂化，通过盘机和递归函数等计算模型及其计算过程的研究都是最基础简单指令的组合所得到的动态的、不断增长的复杂性表现出的。本文通过抽象图灵机的4条基本指令，将其映射为主体一种具有涌现特点的复杂演