Arithmetical Metabolic P Systems - Foundations on Natural and Artificial Computation - page 286

Arithmetical MP Systems compute functions according to the following:

h such that
f ( a 1 ,...,a k )=( b 1 ,...,b h ) is MP-computable if there exist an Arithmetical MP
System M in which, when the

k

Definition 5. (MP-Computable function) Afunction f : N → N

IN substances contain the values a 1 ,...,a k re-

spectively, setting the Start substance to 1, M eventually ends having 1 in its

Halt substance and the values b 1 ,...,b h in the OUT substances.

Moreover, M never reaches the value 1 in the Halt substance if and only if

f ( a 1 ,...,a k ) is undefined.

The Equational Metabolic Algorithm (1), expressed in algebraic terms in Def. 4,
can also be expressed as multiset operations. Given the substances a , b , c S ,

we use the polynomial representation for denoting the multisets α , β , γ such
as α = [ [ n a a + n b b + n c c + ... ] ] ,where n a ,n b ,n c ,... are the multiplicities for
each molecular species. The multiset sum is easily defined summing component
by component as, for example, [ [ a +2 b ] ] + [ [3 b + c ] ] = [ [ a +5 b + c ] ] . The limited
subtraction is analogously defined only if the subtrahend is less or equal then
the subtracter, while the multiplication of a number times a multiset follows the
distributive property of polynomials as for example 3

∈

× [ [ a +2 b ] ] = [ [3 a +6 b ] ] .

c , we can naturally read its reactants and prod-
ucts as multisets, using again with some abuse of notation, r − = [ [2 a + b ] ] and
r + = [ [ c ] ] respectively. Now we can use the multiset operations to express the
Equational Metabolic Algorithm (1), whereas, at each step i

Given a reaction r :2 a + b →

∈ N ,therule r

ϕ r ( X [ i ]) times the multiset r − and adds subtracts ϕ r ( X [ i ]) times the multiset

r + to the metabolic state X [ i ]:
X [ i +1]= X [ i ]+

r∈R

r + r −

r∈R

ϕ r ( X [ i ]) × − ϕ r ( X [ i ]) × . (2)

2.1 Simple Arithmetical MP Systems

In this section some introductory MP-computable functions are described in
order to get the reader acquainted with the Arithmetical MP Systems, MP
grammars and MP graphs. In MP graphs the flux regulators are written besides
the rule nodes and the graphical notations of Table 2.1 will be used.

Limited Subtraction. The limited subtraction, written as x y , is properly
defined only if the subtrahend can actually be subtracted from the subtracter.
More formally:

y = x

y
x otherwise .

− y if x ≥

: N × N → N , x

The Arithmentical MP system implements the operation in one step as shown in
Fig. 2, where the rule tries to expel x and y with a flux equals to the subtrahend