Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
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
 
 
General (G.0 )
 
 
Computability Theory (F.1.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date

Type: Journal
Feb 1 1986
Science, computers, and people: from the tree of mathematics
Ulam S., Birkhäuser Boston Inc., Cambridge, MA, 1986. Type: Book (9789780817632762)
May 1 1988
Computer science: a mathematical introduction
Lew A., Prentice-Hall, Inc., Upper Saddle River, NJ, 1985. Type: Book (9789780131642522)
Jul 1 1986
more...

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