Computability limits in membrane computing

Modern silicon computers have been rapidly advancing in power following Moore's law, but we are fast approaching the natural limits of current designs. In order to continue advancements in computing, we need to develop new computing models and the natural world is a logical step to look for inspiration. Various natural computations have been studied under the umbrella of molecular computing including a new branch known as membrane computing. Membrane computing aims to develop models and paradigms that are biologically motivated. It identifies an unconventional computing model, namely a P system, which abstracts from the way living cells process chemical compounds in their compartmental structure. These systems are a class of distributed, maximally parallel computing devices of a biochemical type. Many models of P systems have been introduced and most have been shown to be computationally complete, i.e., they are universal (equivalent to Turing machines). We examine some restricted models of P systems and characterize their computing power as well as investigate fundamental complexity issues such as universality versus nonuniversality, determinism versus nondeterminism, hierarchies in terms of the number of membranes or the size of the symbol alphabet, and parallel mode versus asynchronous mode of computation.