Computing Reviews

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: 11/23/16

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)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy