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.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
A control strategy on the computations in a one-catalyst P system is provided: the rules are assumed “colored” and in each step only rules of the same “color” are used. Such control leads to Turing universality for one-catalyst P systems with one membrane. Turing universality is also reached for purely catalytic P systems with two catalysts, and for purely catalytic P systems with only one catalyst and cooperating rules working in the so-called terminal mode.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.