Carriers and Counters P Systems with Carriers vs. (Blind) Counter Automata

摘要

P systems with carriers are shown to be computationally complete with only a single membrane and two carriers. We argue that their power is due to the maximal parallelism required in the application of the rules. In fact, with a single carrier, these systems are equivalent to blind counter automata. Finally, with a single passenger restriction the systems are again computationally complete.