Article ID Journal Published Year Pages File Type
434383 Theoretical Computer Science 2014 13 Pages PDF
Abstract

We prove that arbitrary single-tape Turing machines can be simulated by uniform families of P systems with active membranes with a cubic slowdown and quadratic space overhead. This result is the culmination of a series of previous partial results, finally establishing the equivalence (up to a polynomial) of many space complexity classes defined in terms of P systems and Turing machines. The equivalence we obtained also allows a number of classic computational complexity theorems, such as Savitch's theorem and the space hierarchy theorem, to be directly translated into statements about membrane systems.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , ,