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

摘要

涌现描述了特定系统在超过某阈值时突然出现的现象,中间没有明显的过渡过程.提出了图灵机计算模型在时空复杂度上所表现出的计算涌现现象,引入了受限生成过程(Constrained Generating Procedure,CGP)模型来描述图灵机的计算过程,通过CGP模型刻画了机制参与次数、参与深度和平均参与度等3个涌现数字特征,提出了计算涌现的CGP分析方法并在3类典型图灵机计算过程中进行了验证分析.%The complexity of computational models can also put up some emergence properties around several certain critical values. This paper surveyed some computational emergence behaviors, and built their Constrained Generating Procedure(CGP) model. We introduced the CGP mechanic participating times, participating depth and average participating degree,and then analyzed the critical values of emergence properties on 3 typical Turing machine computation processes.