Universal enzymatic numerical P systems with small number of enzymatic variables
Universal enzymatic numerical P systems with small number of enzymatic variables
复制标题
DOI：
10.1007/s11432-017-9103-5
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Zhiqiang Zhang;Tingfang Wu;A. Paun;L. Pan
中科院分区：
文献类型：
--
作者：
Zhiqiang Zhang;Tingfang Wu;A. Paun;L. Pan
数值P系统(简称NP系统)是一种受活细胞结构和经济学启发的分布式并行计算模型。酶数值P系统(简称ENP系统)是NP系统的一种变体，已成功地应用于移动机器人控制器的设计和实现。自从ENP系统被证明是图灵万能系统以来，人们已经做了大量的工作来简化通用系统，其中所考虑的复杂性参数是膜的个数、多项式生产函数的次数或系统中使用的变量的个数。然而，对于ENP系统达到普遍性至关重要的酶变量的数量还没有进行调查。在这里，我们考虑寻找通用ENP系统所需的最小数量的酶变量的问题。我们证明了对于以全并行或一并行方式工作的ENP系统，一个酶变量就足以达到普适性；而对于作为数字生成器的单并行ENP系统，两个酶变量就足以达到普适性。这些结果改进了最著名的结果，即对于全平行和单平行体系，酶变量的数目分别为13和52。
Numerical P systems (for short, NP systems) are distributed and parallel computing models inspired from the structure of living cells and economics. Enzymatic numerical P systems (for short, ENP systems) are a variant of NP systems, which have been successfully applied in designing and implementing controllers for mobile robots. Since ENP systems were proved to be Turing universal, there has been much work to simplify the universal systems, where the complexity parameters considered are the number of membranes, the degrees of polynomial production functions or the number of variables used in the systems. Yet the number of enzymatic variables, which is essential for ENP systems to reach universality, has not been investigated. Here we consider the problem of searching for the smallest number of enzymatic variables needed for universal ENP systems. We prove that for ENP systems as number acceptors working in the all-parallel or one-parallel mode, one enzymatic variable is sufficient to reach universality; while for the one-parallel ENP systems as number generators, two enzymatic variables are sufficient to reach universality. These results improve the best known results that the numbers of enzymatic variables are 13 and 52 for the all-parallel and one-parallel systems, respectively.