Membrane Computing: Main Ideas, Basic Results, Applications

Abstract

Membrane computing is a branch of natural computing whose initial goal was to abstract computing models from the structure and the functioning of living cells. The research was initiated about five years ago (at the end of 1998), and since that time the area has been developed significantly from a mathematical point of view. The basic types of results of this research concern the computability power (in comparison with the standard Turing machines and their restrictions) and the efficiency (the possibility to solve computationally hard problems, typically NP-complete problems, in a feasible time and typically polynomial). However, membrane computing has recently become attractive also as a framework for devising models of biological phenomena, with the tendency to provide tools for modelling the cell itself, not only the local processes. This chapter surveys the basic elements of membrane computing, somewhat in its “historical” evolution: from biology to computer science and mathematics and back to biology. The presentation is informal, without any technical detail, and an invitation to membrane computing intended to acquaint the nonmathematician reader with the main directions of research of the domain, the type of central results, and the possible lines of future development, including the possible interest of the biologist looking for discrete algorithmic tools for modelling cell phenomena.