Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
434383 | Theoretical Computer Science | 2014 | 13 Pages |
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
Artiom Alhazov, Alberto Leporati, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron,