Affiliations: Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Academiei 5, Chişinău, MD-2028, Moldova. artiom@math.md | Faculty of Informatics, Vienna University of Technology, Favoritenstr. 9, 1040 Vienna, Austria. rudi@emcc.at
Note: [] Address for correspondence: Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Academiei 5, Chişinău, MD-2028, Moldova
Abstract: Computational completeness is known for P systems with two catalysts and purely catalytic P systems with three catalysts as well as for P systems with one bi-stable catalyst. We complete this picture by showing computational completeness for purely catalytic P systems with one bi-stable catalyst and one catalyst. Moreover, we present some concrete universal P systems, e.g., for P systems with one multi-stable catalyst and for P systems with multiple catalysts. Furthermore, we optimize the descriptional complexity of Minsky's reduction from register machines with an arbitrary number of registers to register machines with only two registers. In that way, we are able to transform the universal machines U22 and U20 of Korec into weakly universal register machines with only two decrementable registers, one even with unencoded output. Based on these universal register machines, we then construct small universal P systems with one bi-stable catalyst and one catalyst as well as small universal purely catalytic P systems with three catalysts. With respect to the number of rules, the smallest universal P systems can be obtained with multi-stable catalysts and with multiple catalysts. The number of rules in all these systems can be further reduced by adding the concept of toxic objects (a specified subset of objects), where all computation branches not evolving all toxic objects in every computation step do not yield a result.
