Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Numerical P systems with migrating variables
Zhang Z., Wu T., Păun A., Pan L. Theoretical Computer Science641 (C):85-108,2016.Type:Article
Date Reviewed: Nov 23 2016

P systems are a model of computation inspired by biology. A P system is a theory of cells and their biochemistry. It has simple programs distributed over a hierarchical set of membranes. Each membrane has a dynamic mix of chemicals. Each program models a biochemical reaction.

Numerical P systems are similar but based, tenuously, on economic models. The membranes have variables with numerical values. Each program has a “production function,” a formula to calculate a new value. It also has a “repartition protocol” that distributes the new value over nearby variables. Commonly, a program evaluates a value, multiplies it by a number, and distributes the product equally over that number of targets. If several programs distribute values to a single variable, then the values are totaled. Some programs (“enzymatic”) include a condition to enable them. All the programs can either execute in parallel or serially. There are also baroque rules for when variables are cleared before receiving their values.

Given the power of these programs, it is not surprising to me that they are as powerful as Turing machines. The paper proves many results about several varieties of P systems as generators, recognizers, and computers. Typically, a proof is generated by simulating one of the register machines popularized by Marvin Minsky. The proofs are straightforward. The paper is short and simple and follows the normal ways of establishing universality. Theorists and teachers may be interested in yet another model of computation.

Reviewer:  Richard Botting Review #: CR144940 (1702-0143)
Bookmark and Share
  Editor Recommended
Featured Reviewer
Would you recommend this review?
Other reviews under "General": Date
Science, computers, and people: from the tree of mathematics
Ulam S., Birkhäuser Boston Inc., Cambridge, MA, 1986. Type: Book (9789780817632762)
May 1 1988
Topology for computing
Zomorodian A., Cambridge University Press, New York, NY, 2009.  258, Type: Book (978-0-521136-09-9), Reviews: (2 of 2)
Sep 21 2010
The Cauchy-Schwarz master class: an introduction to the art of mathematical inequalities
Steele J., Cambridge University Press, New York, NY, 2004. Type: Book (9780521546775)
Sep 16 2004

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 2004™
Terms of Use
| Privacy Policy