INFORM COMPUT | 带有通道状态的同步化规则的单向组织P系统

本文介绍由湖南大学的宋勃升, 曾湘祥课题组发表于Information and Computation 的研究成果：研究人员报道了一种使用同步化规则的带有通道状态的单向组织P系统，其中系统层面，规则的使用遵循极大并行；通道层面，规则的使用是顺序的；同时在使用的规则集合中引入同步的概念。通过通用性证明发现，在固定细胞数量和规则长度的情况下，添加同步性规则可以使得“状态”参数的数量下降，这说明同步化规则是提高带有通道状态的组织P系统计算能力的一个有效策略以及所提出的带有通道状态的同步化规则的单向组织P系统具有图灵通用性。

1

简介

膜计算是于1998年由欧洲科学院院士Gh.Pᾰun提出的一类生物启发式计算模型，用来模拟活细胞的结构，活动以及功能。在那之后，膜计算成为了自然计算领域中一个快速发展的领域。膜计算领域研究的计算模型一般称为P系统，它们是并行分布式设备。基于膜系统的结构，它们可以分为两种主要的类型：类细胞P系统，有一个可以用树来表示的层次结构；类组织或类神经P系统，有一个可以用图来表示的网络结构。

2021年，宋勃升[1]等人提出了带有通道状态的单向组织P系统，其中通道层面，每个通道上规则的使用是顺序的且规则的使用同时受通道状态的控制；系统层面，规则的使用遵循极大并行方式。除此之外，两个区域间物质的移动只在一个方向上进行。

本文主要介绍一种带有通道状态的同步化规则的单向组织P系统，不仅满足带有通道状态的单向组织P系统的特征，还在其之中引入了同步化规则。通过通用性证明可知，在控制细胞数量和规则长度的情况下，引入同步化规则后，仅分别需要3个状态，2个状态，2个状态就可以实现图灵通用性，由此可见，同步化规则是提高带有通道状态的组织P系统计算能力的一个有效策略（如表7所示）。

2

模型

3

结果

4

总结

本文主要介绍带有通道状态的同步化规则的单向组织P系统，并且证明当使用2个细胞，3个状态，规则极大长度为1；或者使用2个细胞，2个状态，规则极大长度为2；或者使用任意多细胞，2个状态，规则极大长度为1的所提出系统时，可以得到文章所介绍的系统具有图灵通用性。这些结果表明规则的同步化是增强带有通道状态的单向组织P系统计算能力的一个有效策略。

膜系统可以通过细胞分裂或者细胞分离来增加细胞的数量，产生指数数量的细胞，因此可以解决NP完全问题。如何构建具有细胞分裂或细胞分离和同步化规则的类组织P系统来解决计算难问题仍然是一个值得研究的问题。

参考资料

[1]B. Song, X.Zeng and A. Rodrĺguez-Patón. Monodirctional tissue P systems with channel states. Information and Computation, 2021, 546: 206-219.

Li Y, Song B, Zeng X. Rule Synchronization for Monodirectional Tissue-like P Systems with Channel States[J]. Information and Computation, 2022: 104895.

https://doi.org/10.1016/j.ic.2022.104895