Affiliations: [a] School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. [email protected] | [b] College of Information Science and Engineering, Hunan University, Changsha 410082, Hunan, China. [email protected]
Correspondence:
[*]
Address for correspondence: College of Information Science and Engineering, Hunan University, Changsha 410082, Hunan, China.
Note: [†] Also affiliated at: School of Electric and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China
Abstract: P systems are a class of parallel computational models inspired by the structure and functioning of living cells, where all the evolution rules used in a system are initially set up and keep unchanged during a computation. In this work, inspired by the fact that chemical reactions in a cell can be affected by both the contents of the cell and the environmental conditions, we introduce a variant of P systems, called P systems with rule production and removal (abbreviated as RPR P systems), where rules in a system are dynamically changed during a computation, that is, at any computation step new rules can be produced and some existing rules can be removed. The computational power of RPR P systems and catalytic RPR P systems is investigated. Specifically, it is proved that catalytic RPR P systems with one catalyst and one membrane are Turing universal; for purely catalytic RPR P systems, one membrane and two catalysts are enough for reaching Turing universality. Moreover, a uniform solution to the SAT problem is provided by using RPR P systems with membrane division. It is known that standard catalytic P systems with one catalyst and one membrane are not Turing universal. These results imply that rule production and removal is a powerful feature for the computational power of P systems.
Keywords: Bio-inspired Computing, Membrane Computing, Catalytic P System, Universality, SAT Problem
