Verifying a P system generating squares

1 Verifying a P system generating squares Mario J. P´ erez-Jim´ enez Fernando Sancho-Caparrini Dpto. Ciencias de la Computaci´ on e Inteligencia Artificial Universidad de Sevilla, Espa˜ na f Mario.Perez,Fernando.Sancho g @cs.us.es Abstract. In [1], an example of a P system generating exactly all the squares of natural numbers greater than 1 is given. Nevertheless, only an informal reasoning of this result is presented. In this paper we study a similar P system to it (only one evolution rule is modified). A formalization of the syntax of the P system following [3] is given, and we state the verification of the given P system through soundness and completeness: (a) every successful computation of the P system generate a square greater or equal to 1 (soundness); (b) every natural number greater or equal to 1 is the output of a successful computation of the system (completeness). Then we establish the formal verification through the study of the critical points of the computations of the P system that give to us important information to characterize the successful computations. 1. Introduction In October 1998, Gheorghe P˘aun ([1]) introduces a new computability model, of a distributed parallel type, based on the notion of membrane structure. This model, called transition P system, start from the observation that the processes which take place inthe complex structure of a living cell can be considered computations. Following [1], we can consider the P systems as devices which generate numbers: the sum of multiplicities of objects in the output membrane is the generated number. In [1], the following P system, where 4 membrane is the output one. Also, it is said that the set of natural numbers generated by the above P system is N () = f n 2 : n  1 g . 2M.J. P´erez-Jim´enez, F. Sancho-Caparrini /Verifying a P system generating squares 4 3 2 1 a f a a f a b’ b’δ b’ b f f b b ( c , in ) 4 f f f f a δ > P sistema Π This paper is structured in the following way. In section 2 some preliminaries about formalization of transition P systems is presented, following [3]. In section 3 the formal syntax, following section 2, of  is given. In section 4 characterizations of successful computations of above P system is established. In section 5 we show that the output of every successful configuration of  encodes the square of a natural number greater than 1 (soundness of the P system) and, also that the square of every natural number greater than 1 is generated by some successful computation of  (completeness of the P system). 2. Preliminaries about transition P systems Following [3], a membrane structure is a rooted tree, where the nodes are called membranes, the root is called skin, and the leaves are called elementary membranes. Usually, we represent a rooted tree by an ordered pair such that the first component of the pair is the root of the tree and the second component is the adjacency list that consists of n list, one for each vertex i . The list for vertex i contains just those vertices adjacent from i . Acell ( or super-cell ) over an alphabet, A , is a pair ( ; M ) , where  = ( V (  ) ; E (  )) is a membrane structure (we consider E  (  ) as follows: ( x; y ) 2 E  (  ) () y is a child of x in  ), and M is an application, M : V (  ) ! M ( A ) (the set of multisets over A ). Let ( ; M ) a cell over an alphabet, A . Let x 2 V (  ) . An evolution rule associated to x is a 3-tuple r = ( ~ d r ; ~v r ; Æ r ) where ~ d r is a multiset over A ; ~v r is a function with domain V (  ) [ f her e; out g and range contained in M ( A ) where her e; out = 2 V (  ) (here 6 = out); and Æ r 2 f: Æ; Æ g , with : Æ; Æ = 2 A ( : Æ 6 = Æ ). Acollection R of evolution rules associated to C is a function with domain V (  ) such that for every membrane x 2 V (  ) , R x = f r x 1 ;::: ;r x s x g is a finite set (possibly empty) of (evolution) rules associated to x . A priority relation over R is a function,  , with domain V (  ) such that for every membrane x 2 V (  ) ,  x is a strict partial order over R x (possibly empty). Atransition P-system is a 4-tuple  = ( A; C 0 ; R ; i 0 ) , where A is a non-empty finite set (usually called base alphabet); C 0 = (  0 ; M 0 ) is a cell over A ; R is an ordered pair ( R;  ) where R is a collection of (evolution) rules associated to C 0 , and  is a priority relation over R ; and i 0 is a node of  0 , which specifies the output membrane of  . M.J. P´erez-Jim´enez, F. Sancho-Caparrini /Verifying a P system generating squares 3 Aconfiguration, C , of a P system, =( A; C 0 ; R ; i 0 ) with C 0 = (  0 ; M 0 ) , is a cell C = ( ; M ) over A , where V (  )  V (  0 ) , and  has the same root as  0 . The configuration C 0 will be called the initial configuration of  . Let x 2 V (  0 ) . We say that the (evolution) rule r 2 R x is semi-applicable to C if: (a) the membrane associated to node x exists in C , that is, x 2 V (  ) ; (b) dissolution is not allowed in root node, that is, if x is the root node of  , then Æ r = : Æ ; (c) the membrane associated to x has all the necessary objects to apply the rule, that is, ~ d r  M ( x ) ; and (d) nodes where the rule tries to send objects (by means of in y ) are children of x , that is, 8 y 2 V (  )( ~v r ( y ) 6 = ~ 0 ! ( x; y ) 2 E  (  )) . We say that the rule r 2 R x is applicable to C , if it is semi-applicable to C and there is no semiapplicable rules in R x with higher priority. That is: :9 r 0 ( r 0 2 R x ^  x ( r 0 ; r ) ^ r 0 semi-applicable to C ) . We will say that ~p 2 N N is an applicability vector over x 2 V (  ) for C , and we will denote it as ~p 2 Ap ( x; C ) , if:(a) the node is still alive, that is, ~p 6 = ~ 0 ) x 2 V (  ) ; (b) it has correct size, that is, 8 j ( j > s x ! ~p ( j ) = 0) , (where s x is the number of rules associated to x ); (c) every rule can be applied as many times as the vector ~p indicates, that is, 8 j (1  j  s x ! ~p ( j )  N Ap ( r x j ; C; x )) ; (d) all the rules can be applied simultaneously, that is, P s x j =1 ~p ( j )  ~ d r x j  M ( x ) ; and (e) it is maximal, that is, :9 ~v 2 N N ( ~p < ~v ^ ~v 2 Ap ( x; C )) . We will say that P : V (  0 ) ! N N is an applicability matrix over C , denoted P 2 M Ap ( C ) , if for every x 2 V (  0 ) we have that P ( x ) 2 Ap ( x; C ) . We define ( P ; C ) = f x : x 2 V (  ) ^ 9 j (1  j  s x ^ P x ( j ) 6 = 0 ^ Æ r x j = Æ ) g If P is an applicability matrix over C = ( ; M ) and V (  ) = f i 1 ;::: ;i k g , then we denote P = (( p i 1 1 ; : : : ; p i 1 s i 1 ) ;::: ; ( p i k 1 ;::: ;p i k s i k )) . For each node x 2 V (  ) , we define the donors of x for C in the application of P as follows: D on ( x; P ; C ) = 8 > < > : ; ; if x 2 ( P ; C ) f y 2 V (  ) : y 2 ( P ; C ) ^ x  y ^ ^ 8 z 2 V (  )( x  z  y ! z 2 ( P ; C )) g ; if x = 2 ( P ; C ) We define the execution of P over C , denoted P ( C ) , as the configuration of  , C 0 = (  0 ; M 0 ) , where:   0 is the rooted tree obtained from  by means of: – V (  0 ) = V (  )  ( P ; C ) –If x; y 2 V (  0 ) , then: ( x; y ) 2 E  (  0 ) , 9 x 0 ; : : : ; x n 2 V (  )( x 1 ;::: ;x n  1 2 ( P ; C ) ^ x 0 = x ^ x n = y ^ 8 i (0  i < n ! ( x i ; x i +1 ) 2 E  (  )))  M 0 ( x ) = 8 > < > : M 00 ( x ) [ [ y 2 D on ( x;P ;C ) M 00 ( y ) ; if x = 2 ( P ; C ) ; ; if x 2 ( P ; C ) We will say that a configuration C 1 of a P system  yields a configuration C 2 by a transition in one step of  , denoted C 1 )  C 2 , if there exists a non–zero applicability matrix over C 1 , P , such that P ( C 1 ) = C 2 . 4M.J. P´erez-Jim´enez, F. Sancho-Caparrini /Verifying a P system generating squares The computation tree of a P system  , denoted Comp () , is a rooted labeled maximal tree defined as follows: the root of the tree is the initial configuration, C 0 , of  . The children of a node are the configurations that follow in one step of transition. Nodes and edges are labeled by configurations and applicability matrices, respectively, in such way that two labeled nodes C; C 0 are adjacent in Comp () , by means an edge labeled with P , if and only if P 2 M Ap ( C )  f 0 g ^ C 0 = P ( C ) . The maximal branches of Comp () will be called computations of  . We will say that a computation of  halts if it is a finite branch. The configurations verifying M Ap ( C ) = f 0 g will be called halting configurations. We say that a computation C  C 0 )  C 1 )  ::: )  C n of a P system  = ( A; C 0 ; R ; i 0 ) is successful if this computation halts and i 0 is a leaf of the rooted tree  n , where C n = (  n ; M n ) . Then we will say that configuration C n is successful, and n is the length of C . The numerical output of a successful computation, C , is O ( C ) = j M C n ( i 0 ) j where C n is the successful configuration of C . The output of a P system  is O () = f O ( C ) : C is a successful computation of  g . Let  = ( A; C 0 ; R ; i 0 ) a P system. The set of natural numbers generated by  , denoted N () , is defined as follows: N () = f O ( C ) : C is a successful computation of  g . 3. Formalization of the syntax of the P system  Next, we are going to formalize the syntax of the P system  , following the definitions of above section. The P system  is a 4–tuple ( A; C 0 ; R ; i 0 ) , where: (a) The base alphabet is A = f a; b; b 0 ; ; f g . (b) The initial configuration, C 0 = (  0 ; M 0 ) , is defined as follows:  0 = (1 ; ((1 ; 2) ; (2 ; 1 ; 3 ; 4) ; (3 ; 2) ; (4 ; 2))) That is,  0 is the membrane structure given by means of the following rooted tree: 1 2 43 M 0 is the application from f 1 ; 2 ; 3 ; 4 g to M ( A ) defined as: M 0 (1) = M 0 (2) = M 0 (4) = ; y M 0 (3) = f af g . (c) R = ( R;  ) , where:  R is a collection of rules associated to C 0 ; that is, R is an application with domain in f 1 ; 2 ; 3 ; 4 g , defined as: R (1) = R (4) = ; , R (2) = f r 2 1 ; r 2 2 ; r 2 3 ; r 2 4 g y R (3) = f r 3 1 ; r 3 2 ; r 3 3 g , where: – r 2 1 = ( d r 2 1 ; v r 2 1 ; Æ r 2 1 ) , with d r 2 1 = f b 0 g , v r 2 1 : f 1 ; 2 ; 3 ; 4 g [ f her e; out g ! M ( A ) given as v r 2 1 (1) = v r 2 1 (2) = v r 2 1 (3) = v r 2 1 (4) = v r 2 1 ( out ) = ; ; v r 2 1 ( her e ) = f b g , and, also, Æ r 2 1 =  Æ . M.J. P´erez-Jim´enez, F. Sancho-Caparrini /Verifying a P system generating squares 5 – r 2 2 = ( d r 2 2 ; v r 2 2 ; Æ r 2 2 ) , with d r 2 2 = f b g , v r 2 2 : f 1 ; 2 ; 3 ; 4 g [ f her e; out g ! M ( A ) given as v r 2 2 (1) = v r 2 2 (2) = v r 2 2 (3) = v r 2 2 ( out ) = ; ; v r 2 2 (4) = f  g ; v r 2 2 ( her e ) = f b g , and also, Æ r 2 2 =  Æ . – r 2 3 = ( d r 2 3 ; v r 2 3 ; Æ r 2 3 ) , with d r 2 3 = f f f g , v r 2 3 : f 1 ; 2 ; 3 ; 4 g [ f her e; out g ! M ( A ) given as v r 2 3 (1) = v r 2 3 (2) = v r 2 3 (3) = v r 2 3 (4) = v r 2 3 ( out ) = ; ; v r 2 3 ( her e ) = f f g , and, also, Æ r 2 3 =  Æ . – r 2 4 = ( d r 2 4 ; v r 2 4 ; Æ r 2 4 ) , with d r 2 4 = f f g , v r 2 4 : f 1 ; 2 ; 3 ; 4 g [ f her e; out g ! M ( A ) given as v r 2 4 (1) = v r 2 4 (2) = v r 2 4 (3) = v r 2 4 (4) = v r 2 4 ( out ) = ; ; v r 2 4 ( her e ) = f a g , and, also, Æ r 2 4 = + Æ . – r 3 1 = ( d r 3 1 ; v r 3 1 ; Æ r 3 1 ) , with d r 3 1 = f a g , v r 3 1 : f 1 ; 2 ; 3 ; 4 g [ f her e; out g ! M ( A ) given as v r 3 1 (1) = v r 3 1 (2) = v r 3 1 (3) = v r 3 1 (4) = v r 3 1 ( out ) = ; ; v r 3 1 ( her e ) = f ab 0 g , and, also, Æ r 3 1 =  Æ . – r 3 2 = ( d r 3 2 ; v r 3 2 ; Æ r 3 2 ) , with d r 3 2 = f a g , v r 3 2 : f 1 ; 2 ; 3 ; 4 g [ f her e; out g ! M ( A ) given as v r 3 2 (1) = v r 3 2 (2) = v r 3 2 (3) = v r 3 2 (4) = v r 3 2 ( out ) = ; ; v r 3 2 ( her e ) = f b 0 g , and, also, Æ r 3 2 = + Æ . – r 3 3 = ( d r 3 3 ; v r 3 3 ; Æ r 3 3 ) , with d r 3 3 = f f g , v r 3 3 : f 1 ; 2 ; 3 ; 4 g [ f her e; out g ! M ( A ) given as v r 3 3 (1) = v r 3 3 (2) = v r 3 3 (3) = v r 3 3 (4) = v r 3 3 ( out ) = ; ; v r 3 3 ( her e ) = f f f g , and, also, Æ r 3 3 =  Æ .   is the application with domain in f 1 ; 2 ; 3 ; 4 g defined as:  (1) =  (3) =  (4) = ; and  (2) = f ( r 3 2 ; r 4 2 ) g . (d) The output membrane is i 0 = 4 . 4. Characterizing successful configurations of  Let  be a P system designed to generate a set B of natural numbers. To establish the verification of  in relation to the set B , a predicate over configurations (that is, over C omp ()  N ), being, in some way, an invariant of the whole process of generation of the P system  , is searched. That is, this predicate will be true for every computation, C , of  and every natural number. Also, the truth of the predicate over all the configurations of  must extract important information to establish the soundness and completeness of  related to the generation of the set B . The process of verification of a P system,  , is based on the analysis of the content of every membrane in every computation that can be obtained in  . Given a computation, C , of  , we will denote C 0 )  C 1 )  ::: )  C k )  ::: . That is, C k represents the configuration obtained after the execution of k steps in the computation C . In a natural way, a partial function, STEP : C omp ()  N  V (  0 )  ! M ( A ) , can be defined to assign to every computation C , of  , every natural number k and every membrane i of the P system, the content of the membrane i after the execution of k steps in the computation C . If, after the execution of the k -th step, the membrane i is dissolved, then STEP ( C ; k ; i ) is not defined, in this case, we will denote STEP ( C ; k ; i ) " . In other case, we will denote STEP ( C ; k ; i ) # . In general, we will denote STEP ( C ; k ; i ) = C k ( i ) . We denote jC j the length of the computation C that, eventually, can be infinite. 6M.J. P´erez-Jim´enez, F. Sancho-Caparrini /Verifying a P system generating squares Definition 4.1. For every membrane, i , and every computation C of  , we define Æ ( C ; i ) = min f m : C m ( i ) "g Having in mind that no membrane is dissolved in the initial configuration of a every P system  , we have that Æ ( C ; i )  1 , for every C 2 C omp () and every membrane i of  . Given a P system  and a membrane i of  , we can define in a natural way a partial function D i : C omp ()  ! N  f 0 g , as follows: D i ( C ) = Æ ( C ; i ) . That is, D i assign to every computation C of  a natural number representing the instant where the membrane i of  is dissolved (if any). To establish thatthe considered P system  generates the set f n 2 : n  1 g , wewill try to characterize the successful computations of  . For that, first we will give a predicate over the configurations of  to be an invariant along the execution of the P system  . Let us consider the formula  ( C ; n )  ( n < Æ ( C ; 3) ! C n = (  0 ; ( ; ; ; ; ab 0 n f 2 n ; ; ))) ^ ( n = Æ ( C ; 3) ! C success. ^ O ( C ) = n 2 ) To make easier the proofs, and following section 2, the applicability vector will be expressed with a finite number of components (so many as rules the membrane has). We will denote by 0 the vector with all null components, no attending the size of it. If C = ( ; M ) is a cell, where V (  ) = f a 1 ;::: ;a n g  N with a 1 <  < a n , we will note M = ( M ( a 1 ) ;::: ;M ( a n )) . For simplicity of notation, we will represent the multisets by means of the associated word, and ; will be the empty multiset. First, we are going to determine every configuration of the P system before membrane 3 is dissolved. Proposition 4.1. For revery computation C of  we have: 8 n ( n < Æ ( C ; 3) ! C n = (  0 ; ( ; ; ; ; ab 0 n f 2 n ; ; ))) Proof: Let C be a computation of  . Let us prove the result by induction on n . For the base case, n = 0 , it is enough to consider that Æ ( C ; 3)  1 and C 0 = (  0 ; ( ; ; ; ; af ; ; )) . Let n 2 N such that ( n < Æ ( C ; 3) ! C n = (  0 ; ( ; ; ; ; ab 0 n f 2 n ; ; )) . If n + 1 < Æ ( C ; 3) then n < Æ ( C ; 3) and, hence, C n = (  0 ; ( ; ; ; ; ab 0 n f 2 n ; ; )) . As C n +1 (3) # , we deduce that the configuration C n +1 is obtained from C n applying the matrix ~p = ( 0 ; 0 ; (1 ; 0 ; 2 n ) ; 0 ) (applicability matrix over C n ), since no dissolution is applied over membrane 3. The, we have that C n +1 = ~p ( C n ) = (  0 ; ( ; ; ; ; ab 0 ( n +1) f 2 n +1 ; ; )) . ut Next, we will proof that a critical point of the computations of the P system  is in the instant when the membrane 3 is dissolved. That is, we will justify that knowing when membrane 3 is dissolved is important to characterize the successful computations of  . Proposition 4.2. For every computation C of the P system  such that n = Æ ( C ; 3) < 1 , we have: 1. C n = (  0 ; ( ; ; b 0 n f 2 n ; ; )) , where  0 = (1 ; ((1 ; 2) ; (2 ; 1 ; 4) ; (4 ; 2)) ) . 2. For every k such that 0  k  n  1 , we have that C n +1+ k = (  0 ; ( ; ; b n f 2 n  k  1 ;  k n )) , where  0 is as above. 3. C 2 n +1 = (  00 ; ( ab n ;  n 2 )) , where  00 = (1 ; ((1 ; 4) ; (4 ; 1))) . M.J. P´erez-Jim´enez, F. Sancho-Caparrini /Verifying a P system generating squares 7 4. The computation C is successful, its length is jC j = 2 n + 1 , and, also, the numerical output of this computation is O ( C ) = n 2 . Proof: 1. If n = Æ ( C ; 3) < 1 then 0  n 1 < Æ ( C ; 3) . From proposition 4.1, we deduce that C n 1 = (  0 ; ( ; ; ; ; ab 0 ( n  1) f 2 n  1 ; ; )) . Having in mind that Æ ( C ; 3) = n , we obtain that the configuration C n is obtained from C n  1 executing the applicability matrix ~p = ( 0 ; 0 ; (0 ; 1 ; 2 n  1 ) ; 0 ) over C n  1 . Hence, C n = ~p ( C n  1 )=(  0 ; ( ; ; b 0 n f 2 n ; ; )) , where  0 = (1 ; ((1 ; 2) ; (2 ; 1 ; 4) ; (4 ; 2)) ) . 2. Let us prove by induction on k . For the base case, k = 0 , let us observe that from (1) we obtain that C n = (  0 ; ( ; ; b 0 n f 2 n ; ; )) . In this situation, since n  1 , it is possible to apply the rule r 2 3 to the membrane 2 and then, by the strong sense in which the priority is interpreted, the rule r 2 4 can not be applied to C n (this rule would dissolve the membrane 2). Hence, the only matrix applicability over C n will be ~p = ( 0 ; ( n; 0 ; 2 n  1 ; 0) ; 0 ) . In consequence, C n +1 = ~p ( C n )=(  0 ; ( ; ; b n f 2 n  1 ; ; )) . Let k be such that 0  k < n  1 , and let us suppose that C n +1+ k = (  0 ; ( ; ; b n f 2 n  k  1 ;  k n )) . Since n  k  1 > 0 , we deduce that it is possible to apply the rule r 2 3 to membrane 2 and then, the only applicability matrix over C n +1+ k is ~p = ( 0 ; (0 ; n; 2 n  k  2 ; 0) ; 0 ) . Hence, we have that C n +1+ k +1 = (  0 ; ( ; ; b n f 2 n  k  2 ; ( k +1) n )) 3. By applying (2) to the case k = n  1 , we obtain that C 2 n = (  0 ; ( ; ; b n f ;  ( n 1) n )) . Then, the only applicability matrix over C 2 n is ~p = ( 0 ; (0 ; n; 0 ; 1) ; 0 ) . Hence, we have that the configuration C 2 n +1 = (  00 ; ( ab n ;  n 2 )) , where  00 = (1 ; ((1 ; 4) ; (4 ; 1))) . 4. From (3) we deduce that C 2 n +1 = (  00 ; ( ab n ;  n 2 )) . Having in mind that V (  00 ) = f 1 ; 4 g and R 1 = R 4 = ; we deduce that M Ap ( C 2 n +1 ) = f ( 0 ; 0 ) g . Then the configuration C 2 n +1 is a halting configuration. Also, since 4 2 V (  00 ) and 4 is a leaf of  00 results that the configuration C 2 n +1 is successful. Hence, the computation C is successful, its length is 2 n + 1 , and its numerical output is O ( C ) = jC 2 n +1 (4) j = n 2 . ut As a first consequence from this proposition, let us see that after the instant the membrane 3 is dissolved, the P system evolves in a “deterministic” way. Corollary 4.1. For every n  1 and every C ; C 0 2 C omp () such that n = Æ ( C ; 3) = Æ ( C 0 ; 3) we have that 8 k ( n  k  2 n + 1 ! C k = C 0 k ) . Proof: The case k = n follows from (1) in above proposition, the case n < k  2 n follows from (2), and the case k = 2 n + 1 follows from (3). ut Next, let us see that if two computations have the same instant of dissolution to membrane 3, then these computations are equal. 8M.J. P´erez-Jim´enez, F. Sancho-Caparrini /Verifying a P system generating squares Corollary 4.2. For every n  1 and every C ; C 0 2 C omp () such that n = Æ ( C ; 3) = Æ ( C 0 ; 3) we have that C = C 0 . Proof: Let n  1 and C ; C 0 2 C omp () such that n = Æ ( C ; 3) = Æ ( C 0 ; 3) . By applying (4) in proposition 4.2, and above corollary, it’s enough to prove that 8 k (0  k  n  1 ! C k = C 0 k ) . But, this last relation follows directly from proposition 4.1. ut Corollary 4.3. There exists, at most, a computation of  not to be successful. Proof: Let C be a computation of  not to be successful. From proposition 4.2 we deduce that 8 k ( k < Æ ( C ; 3)) . Hence, from proposition 4.1 results that C k = (  0 ; ( ; ; ; ; ab 0 k f 2 k ; ; ))) . Then, C is unique. ut Next, let us see that the formula  ( C ; n ) is true for every configuration C n of the P system  . Corollary 4.4. The formula  ( C ; n ) is an invariant of the P system  . That is, 8C 2 C omp () 8 n 2 N (  ( C ; n )) . Proof: It follows directly from proposition 4.1 and (4) in proposition 4.2. ut Next, we are going to characterize the successful computations of  through the instant the membrane 3 is dissolved. Corollary 4.5. Let C be a computation of  . The following are equivalents: (a) C is a successful computation. (b) Æ ( C ; 3) < 1 . (c) Æ ( C ; 3) < 1 and jC j = 2  Æ ( C ; 3) + 1 . Proof: Let C be a successful computation. Let k = jC j . Then 1  k < 1 . Let us see that Æ ( C ; 3)  k . In other case, from proposition 1 we have that C k = (  0 ; ( ; ; ; ; ab 0 k f 2 k ; ; )) . Which contradicts k = jC j , since from the existence of no null applicability matrix over C k (for example, ~p = ( 0 ; 0 ; (1 ; 0 ; 2 k ) ; 0 ) ) we would have that C k is not a halting configuration. If Æ ( C ; 3) < 1 then, from (4) in proposition 4.2, results that jC j = 2 n + 1 . Finally, (  ) ) ( a ) results directly from (4) in proposition 4.2. ut M.J. P´erez-Jim´enez, F. Sancho-Caparrini /Verifying a P system generating squares 9 5. Soundness and Completeness of the P system  To establish that the set of natural numbers generated by  is N () = f n 2 : n  1 g we must to prove two results:  The numerical output of any successful computation of the P system  encodes the square of a natural number greater or equal to 1 (soundness of the P system).  For every n  1 there exists, at least, a successful computation, C ,of the P system  with numerical output O ( C ) = n 2 (completeness of the P system). Theorem 5.1. ( Soundness ) If C is a successful computation of the P system  , then there exists n  1 such that the output of C is O ( C ) = n 2 . Proof: Let C be a successful computation of  . If n = Æ ( C ; 3) then, from corollary 4.2, results that 1  n < 1 . Since the formula  ( C ; n ) is true and n = Æ ( C ; 3) , we deduce that the computation C is successful and, also, O ( C ) = n 2 . ut To establish the completeness of  to generate the set f n 2 : n  1 g , we consider the formula ' ( n )  9 C 2 C omp () ( n = Æ ( C ; 3)) . Let us see that this formula is true for every natural number greater or equal to 1. Proposition 5.1. For every natural number n  1 there exists a unique computation, C , of  such that Æ ( C ; 3) = n . Proof: Let us prove the existence by induction on n . For the base case, n = 1 , the configuration C 1 , obtained from the initial configuration, C 0 , by applying the matrix ~p = ( 0 ; 0 ; (0 ; 1 ; 1) ; 0 ) (applicability matrix over C 0 ), is considered. Since r 3 2  a ! b 0 Æ , we obtain that Æ ( C ; 3) = 1 . Let n  1 and let us suppose the result is true for n . Let C be a computation of  such that Æ ( C ; 3) = n . From proposition 4.1, we deduce that C n  1 = (  0 ; ( ; ; ; ; ab 0 ( n  1) f 2 n  1 ; ; ))) . The set of applicability matrices over C n  1 is M Ap ( C n  1 ) = f ~p 1 ; ~p 2 g , where ~p 1 = ( 0 ; 0 ; (0 ; 1 ; 2 n  1 ) ; 0 ) , ~p 2 = ( 0 ; 0 ; (1 ; 0 ; 2 n  1 ) ; 0 ) Let C 0 n = ~p 2 ( C n  1 ) . Then C 0 n = (  0 ; ( ; ; ; ; ab 0 n f 2 n ; ; )) . Let C 0 n +1 = ~p 3 ( C 0 n ) , where ~p 3 = ( 0 ; 0 ; (0 ; 1 ; 2 n ) ; 0 ) , in this step membrane 3 is dissolved. Then C 0 n +1 = (  0 ; ( ; ; b 0 ( n +1) f 2 n +1 ; ; )) , where the membrane structure is  0 = (1 ; ((1 ; 2) ; (2 ; 1 ; 4) ; (4 ; 2))) . Hence, the computation C 0  C 0 )  C 1 )  ::: )  C n  1 )  C 0 n )  C 0 n +1 )  ::: , verifies that Æ ( C 0 ; 3) = n + 1 . Given n  1 , the uniqueness of the computation C verifying Æ ( C ; 3) = n , follows directly from corollary 4.2. ut Proposition 5.2. There exists an unique computation, C , of  not to be successful.