Homeostasis Tissue-Like P Systems.

Tissue P systems provide distributed parallel devices inspired by actual biological reality, where communication rules are used for object exchange between cells (or between cells and the environment). In such systems, the environment continuously provides energy to cells, so the cells are very dependent on the objects in the environment. In biology, there is a mechanism called homeostasis, that is, an internal organism is independent from the external conditions, thus keeping itself relatively stable. Inspired by this biological fact, in this paper, we assume that the environment no longer provides energy for cells, introducing multiset rewriting rules into tissue P systems, thereby constructing a novel computational model called homeostasis tissue-like P systems. Based on the model, we construct two uniform solutions in feasible time. One solution is constructed to solve the 3-coloring problem in linear time in standard time, and the other solution is constructed to solve the SAT problem with communication rules and multiset rewriting rules of the length at most 3 in time-free mode. Moreover, we prove that the constructed system can generate any Turing computable set of numbers using communication rules and multiset rewriting rules with a maximal length 3, working in the mode of standard time and time-free, respectively. The results show that our constructed system does not rely on the environment and reflects the phenomenon of biological homeostasis. In addition, although the system runs in time-free way, it not only has Turing university, but also can effectively solve NP-complete problem.