Research Group on Natural Computing

In 1936 A. Turing showed the existence of a universal machine able to simulate any Turing machine given its description. In 1956, C. Shannon formulated for the first time the problem of finding the smallest possible universal Turing machine according to some critera to measure its size such as the number of states and symbols. Within the framework of Membrane Computing different studies have addressed this problem: small universal symport/antiport P systems (by considering the number of membranes, the weight of the rules and the number of objects as a measure of the size of the system), small universal splicing P systems (by considering the number of rules as a measure of the size of the system), and small universal spiking neural P systems (by considering the number of neurons as a measure of the size of the system). In this paper the problem of determining the smallest possible efficient P system is explicitly formulated. Efficiency within the framework of Membrane Computing refers to the capability of solving computationally hard problems (i.e. problems such that classical electronic computer cannot solve instances of medium/large size in any reasonable amount of time) in polynomial time. A descriptive measure to define precisely the notion of small P system is presented in this paper.