Lecture Notes in Computer Science, 2010, Volume 5957/2010, 461-478, DOI: 10.1007/978-3-642-11467-0_31

An Efficient Simulation of Polynomial-Space Turing Machines by P Systems with Active Membranes

Andrea Valsecchi, Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri and Claudio Zandron

View Related Documents

Abstract

We show that a deterministic single-tape Turing machine, operating in polynomial space with respect to the input length, can be efficiently simulated (both in terms of time and space) by a semi-uniform family of P systems with active membranes and three polarizations, using only communication rules. Then, basing upon this simulation, we prove that a result similar to the space hierarchy theorem can be obtained for P systems with active membranes: the larger the amount of space we can use during the computations, the harder the problems we are able to solve.

Fulltext Preview

Image of the first page of the fulltext document