Abstract

Many of us, as computer scientists, are accustomed to computational systems that are of electronic nature. In my talk, I will present other computational systems, based on biology and biochemistry. A seminal paper in this field by Adleman shows a way of using molecular computation to solve a combinatorial problem by encoding a graph in DNA molecules. Păun introduced a new computational model, called P systems, which uses biological processes as inspiration for performing calculations. The former uses biological structures as hardware and was devised to perform a specific computation – solving the Hamiltonian path problem – while the latter was modelled to provide an alternative to current computational models – it is not intended to be implemented using biological structures, it rather uses them as an inspiration. I shall describe the two in more detail and talk about the computational power of P systems, while comparing it to that of other computational models that are in wider use.