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

作者：张海粟; 张松林; 陈桂生

来源：计算机科学, 2011, (07): 302-305.

• 计算涌现
• 受限生成过程
• 图灵机
• 复杂性分析 Computational emergence,Constrained generating procedure,Turing machine,Computing complexity

涌现描述了特定系统在超过某阈值时突然出现的现象,中间没有明显的过渡过程。提出了图灵机计算模型在时空复杂度上所表现出的计算涌现现象,引入了受限生成过程(Constrained Generating Procedure,CGP)模型来描述图灵机的计算过程,通过CGP模型刻画了机制参与次数、参与深度和平均参与度等3个涌现数字特征,提出了计算涌现的CGP分析方法并在3类典型图灵机计算过程中进行了验证分析。

• 单位
  中国人民解放军陆军工程大学