On Evolutionary Lineages of Membrane Systems

摘要

We introduce a simple model of P system motivated by certain restrictions found in biological systems. Its computational power is rather limited and corresponds to that of a finite transducer. An important characteristics of the model is its interactive behavior. Then we study the computational power of evolutionary lineages of such P systems. Referring to known results from the structural complexity theory (Karp and Lipton, Wiedermann and van Leeuwen), we show that a super-Turing computational potential can emerge in non-uniform lineages of these restricted P systems. Furthermore, key features of our model are related to lineages of biological systems. In this way, our results provide another argument supporting the thesis from and others that a super-Turing potential is naturally and inherently present in evolution of living organisms.