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.
Alhazov, A., Leporati, A., Mauri, G., Porreca, A., Zandron, C. (2014). Space complexity equivalence of P systems with active membranes and Turing machines. THEORETICAL COMPUTER SCIENCE, 529, 69-81 [10.1016/j.tcs.2013.11.015].
Space complexity equivalence of P systems with active membranes and Turing machines
ALHAZOV, ARTIOM;LEPORATI, ALBERTO OTTAVIO;MAURI, GIANCARLO;PORRECA, ANTONIO ENRICO;ZANDRON, CLAUDIO
2014
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.