Generating Diophantine Sets by Virus Machines

Generating Diophantine Sets by Virus Machines ´Alvaro Romero-Jim´enez, Luis Valencia-Cabrera, and Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence, University of Seville, Avda. Reina Mercedes s/n, 41012 Seville, Spain {romero.alvaro,lvalencia,marper}@us.es Abstract. Virus Machines are a computational paradigm inspired by the manner in which viruses replicate and transmit from one host cell to another. This paradigm provides non-deterministic sequential devices. Non-restricted virus machines are unbounded virus machines, in the sense that no restriction on the number of hosts, the number of instructions and the number of viruses contained in any host along any computation is placed on them. The computational completeness of these machines has been obtained by simulating register machines. In this paper, virus machines as set generating devices are considered. Then, the universality of non-restricted virus machines is proved by showing that they can compute all diophantine sets, which the MRDP theorem proves that coincide with the recursively enumerable sets. Keywords: Virus machines ·Computational completeness ·Diophantine sets ·MRDP theorem 1 Introduction A new computational paradigm inspired by the replications and transmissions of viruses was introduced in [1]. The computational devices in this paradigm are called Virus Machines and they consist of several processing units, called hosts, connected to each other by transmission channels. A host can be viewed as a group of cells (being part of a colony, organism, system, organ or tissue). Each cell in the group will contain at most one virus, but we will not take into account the number of cells in the group, we will only focus on the number of viruses that are present in some of the cells of that group (not every cell in the group does necessarily hold a virus). Only one type of viruses is considered. Channels allow viruses to be transmitted from one host to another or to the environment of the system. Each channel has a natural number (the weight of the channel) associated with it, indicating the number of copies of the virus that will be generated and transmitted from an original one (i.e., one virus may replicate, generating a number of copies to be transmitted to the target host group of cells). Each transmission channel is closed by default and it can be opened by a control instruction unit. Specifically, there is an instruction-channel control network that allows opening a channel by means of an activated instruction. In that moment, the opened channel allows a virus (only one virus) to replicate and transmit through it. Instructions are activated individually according to a protocol given by an instruction transfer network, so that only one instruction is enabled in each computation step. That is, an instruction activation signal is transferred to the network to activate instructions in sequence. In this work, new virus machines as set generating devices are introduced. The universality of non-restricted virus machines working in this mode is proved by showing that they can generate all diophantine sets. The celebrated MRDP theorem assures that these sets are exactly the same as the recursively enumerable sets [4]. This paper is structured as follows. First, the computing model of virus machines is formally defined. Then, in Sect. 3the computational completeness of non-restricted virus machines is stated. Finally, in Sect. 4the main conclusions of this work are summarized and some suggestions for possible lines of future research are outlined. 2 Virus Machines In what follows we formally define the syntax of the Virus Machines (see [1]for more details). An undirected graph Gis a pair (V,E), where Vis a finite set and Eis a subset of {x, y}|x∈V,y ∈V,x =y. The set Vis called the vertex set of G, and its elements are called vertices. The set Eis called the edge set of G, and its elements are called edges.Ife={x, y}∈Eis an edge of G, then we say that edge eis incident on vertices xand y. In an undirected graph, the degree of a vertex xis the number of edges incident on it. A bipartite graph Gis an undirected graph (V,E)inwhichVcan be partitioned into two sets V1,V 2such that {u, v}∈Eimplies either u∈V1and v∈V2or u∈V2and v∈V1;thatis, all edges are arranged between the two sets V1and V2(see [2] for details). Adirected graph Gis a pair (V,E), where Vis a finite set and Eis a subset of V×V. The set Vis called the vertex set of G, and its elements are called vertices. The set Eis called the arc set of G, and its elements are called arcs. In a directed graph, the out-degree of a vertex is the number of arcs leaving it, and the in-degree of a vertex is the number of arcs entering it. Definition 1. AVirus Machine Πof degree (p, q),withp≥1,q ≥1, is a tuple (Γ,H,I,DH,D I,G C,n 1,...,n p,i 1,h out),where: –Γ={v}is the singleton alphabet; –H={h1,...,h p}and I={i1,...,i q}are ordered sets such that v/∈H∪I and H∩I=∅; –DH=(H∪{hout},E H,w H)is a weighted directed graph, verifying that EH⊆ H×(H∪{hout}),(h, h)/∈EHfor each h∈H,out-degree(hout)=0,andwH is a mapping from EHto Z>0; –DI=(I,EI,w I)is a weighted directed graph, where EI⊆I×I,wIis a mapping from EIto Z>0and, for each vertex ij∈I, the out-degree of ijis less than or equal to 2; –GC=(VC,E C)is an undirected bipartite graph, where VC=I∪EH,being {I,EH}the partition associated with it (i.e., all edges go between the two sets Iand EH). In addition, for each vertex ij∈I, the degree of ijin GCis less than or equal to 1; –nj∈N(1≤j≤p)andi1∈I; –hout /∈I∪{v}and hout is denoted by h0in the case that hout /∈H. A Virus Machine Π=(Γ,H,I,DH,D I,G C,n 1,...,n p,i 1,h out) of degree (p, q) can be viewed as an ordered set of phosts labelled with h1,...,h p(where each host hj,1≤j≤p, initially contains exactly njviruses –copies of the symbol v–), and an ordered set of qcontrol instruction units labelled with i1,...,i q. The symbol hout represents the output region of the system (we use the term region to refer to host hout in the case that hout ∈Hand to refer to the environment in the case that hout =h0). Arcs (hs,h s)fromDHrepresent transmission channels through which viruses can travel from host hsto hs. Each channel is closed by default, and so it remains until it is opened by a control instruction (which is attached to the channel by means of an edge in graph GC) when that instruction is activated. Furthermore, each channel (hs,h s) is assigned with a positive integer weight, denoted by ws,s, which indicates the number of viruses that will be transmitted/replicated to the receiving host of the channel. Arcs (ij,i j)fromDIrepresent instruction transfer paths, and they have a weight, denoted by wj,j, associated with it. Finally, the undirected bipartite graph GCrepresents the instruction-channel network by which an edge {ij,(hs,h s)}indicates a control relationship between instruction ijand channel (hs,h s): when instruction ijis activated, the channel (hs,h s) is opened. Aconfiguration Ctof a virus machine at an instant tis described by a tuple (a1,t,...,a p,t,u t,e t), where a1,t,...,a p,t and etare non-negative integers and ut∈I∪{#}, with # /∈H∪{h0}∪I. The meaning is the following: at instant t the host hsof the system contains exactly as,t viruses, the output region hout contains exactly etviruses and, if ut∈I, then the control instruction unit utwill be activated at step t+ 1. Otherwise, if ut= #, then no further instruction will be activated. The initial configuration of the system is C0=(n1,...,n p,i 1,0). A configuration Ct=(a1,t,...,a p,t,u t,e t)isahalting configuration if and only if utis the object #. A non-halting configuration Ct=(a1,t,...,a p,t,u t,e t) yields configuration Ct+1 =(a1,t+1,...,a p,t+1,u t+1,e t+1)inonetransition step, denoted by Ct⇒ΠCt+1, if we can pass from Ctto Ct+1 as follows: 1. First, given that Ctis a non-halting configuration, we have ut∈I.Sothe control instruction unit utis activated. 2. Let us assume that instruction utis attached to channel (hs,h s). Then this channel will be opened and: –Ifas,t ≥1, then a virus (only one virus) is consumed from host hsand ws,s copies of vare produced in host hs(if s=out) or in the output region hout. –Ifas,t = 0, then there is no transmission of virus. 3. Let us assume that instruction utis not attached to any channel (hs,h s). Then there is no transmission of virus. 4. Object ut+1 ∈I∪{#}is obtained as follows: – Let us suppose that out-degree(ut) = 2, that is, there are two different instructions utand ut such that (ut,u t)∈EIand (ut,u t )∈EI. •If instruction utis attached to a channel (hs,h s)andas,t ≥1 then ut+1 is the instruction corresponding to the highest weight path. •If instruction utis attached to a channel (hs,h s)andas,t = 0 then ut+1 is the instruction corresponding to the lowest weight path. •If both weights are equal or if instruction utis not attached to a channel, then the next instruction ut+1 is either utor ut , selected in a nondeterministic way. – If out-degree(ut) = 1 then the system behaves deterministically and ut+1 is the instruction that verifies (ut,u t+1)∈EI. – If out-degree(ut) = 0 then ut+1 is object # and configuration Ct+1 is a halting configuration. Acomputation of a virus machine Πis a (finite or infinite) sequence of configurations such that: (a) the first element is the initial configuration C0of the system; (b) for each n≥1, the n-th element of the sequence is obtained from the previous element in one transition step; and (c) if the sequence is finite (called halting computation) then the last element is a halting configuration. All the computations start from the initial configuration and proceed as stated above; only halting computations give a result, which is encoded in the contents of the output region for the halting configuration. In this paper we consider virus machines working in the generating mode. That is, we think of the result of a computation of a virus machine Πas the total number nof viruses sent to the output region during the computation. We say that A⊆Nis the set generated by Πif it is verified that n∈Aif and only if there exists a halting computation of Πthat outputs n. 3 The Universality of Non-Restricted Virus Machines Anon-restricted Virus Machine is a virus machine for which there is no restriction on the number of hosts, the number of instructions and the number of viruses contained in any host along any computation. For each p, q, n ≥1, we denote by NVM(p, q, n) the family of all subsets of Ngenerated by virus machines with at most phosts, qinstructions, and all hosts having at most nviruses at any instant of each computation. If one of the parameters p, q, n is not bounded, then it is replaced with ∗. In particular, NVM(∗,∗,∗) denotes the family of all subsets of natural numbers generated by non-restricted virus machines. 3.1 Generating Diophantine Sets by Virus Machines In this section, the computational completeness of non-restricted virus machines working in the generating mode is established. Specifically, we prove that they can generate all diophantine sets of natural numbers. Indeed, we will design nonrestricted virus machines that, given a polynomial P(x, y1,...,y k) with integer coefficients: 1. Generate, in a non-deterministic manner, any tuple (x, y1,...,y k) of natural numbers. 2. Compute the value of Pover the tuple (x, y1,...,y k). 3. If the computed value is zero, then halt and output x. 4. If the computed value is non-zero, then do not halt. 3.2 Modules In order to ease the design of the virus machines generating any diophantine set, the construction of such virus machines will be made in a modular manner. Amodule can be seen as a virus machine without output host, with the initial instruction marked as the in instruction and with at least one instruction marked as an out instruction. The out instructions must have out-degree less than two, so that they can still be connected to another instruction. In this way, a module m1can be plugged in before another module m2or virus machine instruction i by simply connecting the out instructions of m1with the in instruction of m2 or with the instruction i. The layout of a module must be carefully done to avoid conflicts with other modules and to allow the module to be executed any number of times. To achieve the first condition, we will consider that all the hosts (with the only exception of the parameters of the module) and instructions of a module are individualized for that module, being distinct from the ones of any other module or virus machine. There are several ways to meet the second condition: for example, we can ensure that, after the execution of the module, all its hosts except its parameters contain the same number of viruses as before the execution. In this paper we consider two types of modules: action modules and predicate modules. For the action modules we require all of its out instructions to be connected to the in instruction of the following module, or to the following instruction of the virus machine. For the predicate modules we consider its out instructions to be divided in two subsets: the out instructions representing a yes answer and the out instructions representing a no answer of the predicate. For each of these subsets, all of its instructions have to be connected to the same module in instruction or virus machine instruction. The library of modules used in this paper consists of the following modules (we name the action modules as verbs and the predicate modules as questions): –EMPTY(h): action module that sets to zero the number of viruses in host h. To implement this module we only need to introduce an internal host h, initially with zero viruses, and associate with the channel from hto han action that transfers all the viruses from h. Note that host hmay end with a nonzero number of viruses, but this does not prevent the module to be reused, because hplays a passive role. –ADD(h1,h2): action module that adds to host h2the number of viruses in host h1, without modifying the number of viruses in h1. This module is implemented as follows: This way, the module starts by transferring one by one all the viruses from h1to h, duplicating them along the way. Then it sends, again and again, one virus from hto h2and another one from hto h1, until there are no more viruses left. It is clear then that when the module ends, the host h1retains its initial number of viruses, the host his empty (thus allowing the module to be reused), and the host h2has a number of viruses equal to the sum of the initial number of viruses in h1and h2. –COPY(h1,h2): action module that sets the number of viruses in h2the same as in h1, without modifying the number of viruses in h1. This module is implemented by the following concatenation of modules: in →EMPTY(h2)→ADD(h1,h 2)→out That is, we first get rid of all the viruses from h2, and then add the viruses from h1,soh2ends with the same number of viruses as h1. Also observe that the module ADD(h1,h2) does not modify the number of viruses in h1, what will be important later. –SET(h,n): action module that sets to nthe number of viruses in host h. This module is implemented simply by introducing an internal host hwith initial number of viruses nand using the module COPY(h,h). –AREEQUAL?(h1,h2): predicate module that checks if the number of viruses in hosts h1and h2coincides. This module is implemented as follows, where h 1,h 2and hare new internal hosts: We first copy the contents of h1and h2into the internal hosts h 1and h 2, so that they do not get modified. Then, in turns, we send one virus from h 1 to hand then another one from h 2to h. If the latter can not be done, this is because the contents of h1were greater than the contents of h2and the answer is no. If the former can not be done, we must try once more to send a virus from h 2to hto determine if the contents were or not equal. Notice that the contents of h 1,h 2and hget modified, but this does not prevent the module to be reused, because the first two get initialized by the first two COPY modules and the latter plays a passive role. –MULTIPLY(h1,h2): action module that multiplies the number of viruses in host h2by the number of viruses in host h1, without modifying the number of viruses in h1. This module is implemented in two stages: 1. An initialization stage, where the contents of an internal host h 1,which will be used as a counter, is set to zero. Also the number of viruses in h2is saved in an internal host h 2. This is because host h2needs to be emptied, so that it can be used as the accumulator in a standard implementation of the multiplication. in →EMPTY(h 1)→COPY(h2,h  2)→EMPTY(h2)→ 2. The second stage iteratively adds the contents of h 2to h2, until the counter h 1reaches the number of viruses in h1. The counter is incremented in each step by adding to it the contents of an internal host hone that has only one virus within. →AREEQUAL?(h1,h  1)no →ADD(h 2,h 2)→ADD(hone,h  1)→back to stage 2 ↓yes out It is clear that when the module ends, the host h1retains its initial number of viruses and the host h2has a number of viruses equal to the product of the initial number of viruses in h1and h2. The internal host hone is never modified and both internal hosts h 1and h 2are initialized in stage 1, what allows the module to be reused. –RAISE(h1,h2): action module that raises the number of viruses in host h2to the power of the number of viruses in host h1, without modifying the number of viruses in h1. This module is implemented in two stages: 1. An initialization stage, where the contents of an internal host h 1,which will be used as a counter, is set to zero. Also the number of viruses in h2 is saved in an internal host h 2. This is because the contents of host h2 needs to be set to one virus, so that it can be used as the accumulator in a standard implementation of the exponentiation. in →EMPTY(h 1)→COPY(h2,h  2)→SET(h2,1) → 2. The second stage iteratively multiplies the contents of h2by the contents of h 2, until the counter h 1reaches the number of viruses in h1. The counter is incremented in each step by adding to it the contents of an internal host hone that has only one virus within. →AREEQUAL?(h1,h  1)no →MULTIPLY(h 2,h 2)→ADD(hone,h  1)→back to stage 2 ↓yes out It is clear that when the module ends, the host h1retains its initial number of viruses and the host h2has a number of viruses equal to the initial number of viruses in h2raised to the initial number of viruses in h1. The internal host hone is never modified and both internal hosts h 1and h 2are initialized in stage 1, what allows the module to be reused. –EXPT(h,n): action module that raises the number of viruses in hto the power of n. This module is implemented simply by introducing an internal host hwith initial number of viruses nand using the module RAISE(h,h). 3.3 Generation of a Diophantine Set In what follows we show how to design, given a polynomial P(x, y1,...y k) with integer coefficients, a virus machine ΠPthat generates the diophantine set characterized by that polynomial. – The hosts are H={hx,h  x,h y1,h  y1,...,h yk,h  yk,h +,h −,h one,h out}∪ {hc|c>0 and there exists α, β1,...,β k∈Nsuch that cx αyβ1 1···yβk kor −cx αyβ1 1···yβk kis a monomial of P} together with the internal hosts of the modules. – The initial contents of hone is 1, and of hcis c. The initial contents of the rest of hosts is 0, except for the internal hosts of the modules, which have their specific initial contents. – The output host is hout. – The instructions are I={increment x, increment y1,...,increment yk, halt,infinite loop} together with the individualized instructions of the modules. – The initial instruction is increment x. – The functioning of the virus machine is given by the following sequence of concatenated instructions and modules, which determines the graphs DH,D I and GC: 1. First a value for xis generated, in a non-deterministic manner. The instruction transfer paths labelled by yes and no are set to have the same weight (for example, weight 1) so, according to the semantics of the model, it is non-deterministically chosen to add or not the contents of hone, one virus, to hx. In the former case, the machine comes back to instruction increment x to make the choice again. In the latter case, it has finished generating a value for x. 2. Analogously, a value for each of y1to ykis generated in a non-deterministic manner.