基于对象进化规则的内稳态组织膜系统

作者：罗跃国^*; 江赟; 谭海军; 章英; 范会联

来源：电子学报, 2019, 47(01): 100-104.

• 膜计算
• 膜系统
• 类组织膜系统
• 时间无关
• 内稳态

膜系统通常也称为P系统,是一类分布式并行计算模型.本文提出了一种基于类组织膜系统的新变体——基于对象进化规则的内稳态组织膜系统.在这类系统中,去除了"环境中可以包含任意多份物质"这个条件,并引入了对象进化规则.通过模拟注册机,证明了任何图灵可计算数都可通过该类膜系统产生.为了建立容错性能更好的计算系统,将时间无关的概念引入到这类系统中,证明了在时间无关模式下,构建的识别内稳态组织膜系统可以在线性时间内得到三着色问题统一解.证明结果表明,这类模型求解NP完全问题具有较好的计算效率.

• 单位
  长江师范学院; 重庆工商大学