Symport/Antiport P systems with three objects are universal

TitleSymport/Antiport P systems with three objects are universal
Publication TypeJournal Papers
Year of Publication2005
AuthorsPaun, G., Pazos-Sierra J., Pérez-Jiménez M. J., & Rodríguez-Patón A.
Journal TitleFundamenta Informaticae
PublisherIOS Press
Place PublishedWarsaw, Poland
Volume64
Pages353-367
Abstract

The operations of symport and antiport, directly inspired from biology, are already known to be rather powerful when used in the framework of P systems. In this paper we confirm this observation with a quite surprising result: P systems with symport/antiport rules using only three objects can simulate any counter machine, while systems with only two objects can simulate any blind counter machine. In the first case, the universality (of generating sets of numbers) is obtained also for a small number of membranes, four.

KeywordsMembrane computing, register machine, symport/antiport, Turing computability
URLhttp://portal.acm.org/citation.cfm?id=1227085.1227115&coll=GUIDE&dl=GUIDE&CFID=2475207&CFTOKEN=63580860
Issue1-4
ISSN Number0169-2968