On the power of enzymatic numerical P systems (Q715056)

The paper studies the computing power of a class of numerical P systems introduced in the framework of autonomous robot control. In numerical P systems, numerical variables evolve in the compartments of a cell-like structure by means of so-called production-repartition programs. Such a program is made of a production function (usually a polynomial) and a repartitioning protocol. The production function is evaluated in each computational step on the current values of the variables in the compartment, and the result is distributed among the variables of the neighboring compartments according to the repartitioning protocol. The values assumed by a specified ``output'' variable are said to be computed by the system. Enzymatic numerical P systems are variants where enzymes, that is, variables, are attached to the evolution programs: a program can be used only if the value of the enzyme is greater than the value of any other variable involved in the ``production part'' of the program. The authors use the characterization of recursively enumerable sets of numbers as the positive values of polynomials with integer coefficients to show that any recursively enumerable set of numbers can be generated by enzymatic numerical P systems where the programs are used in the sequential (one program in each membrane in one computational step) or all-parallel (all programs in each membrane in all computational steps, the values of the variables can be shared by several programs), in the later case even if the system is deterministic. They also show the same result for systems with one-parallel rule application (a maximal set of programs in each membrane in each computational step, the variables cannot be shared) using a register machine characterization of recursively enumerable sets.