Small Computationally Complete Symport/Antiport P Systems

Abstract

It is known that P systems with symport/antiport rules simulate the register machines, i.e., they are computationally complete. Hence, due to the existence of universal register machines, there exist computationally complete subclasses of symport/antiport P systems with a number of rules limited by a constant. However, there was no estimation of this number in the literature. In this article, we first give a simple estimation of this constant, and then we show that the number can be reduced by grouping together several instructions of the simulated variant of the register machines. Finally, a universal P system with symport/antiport having only 44 rules is obtained.