Generating, computing and recognizing with virus machines

Theoretical Computer Science 972 (2023) 114077 Contents lists available at ScienceDirect Theoretical Computer Science journal homepage: www.elsevier.com/locate/tcs Generating, computing and recognizing with virus machines✩ Antonio Ramírez-de-Arellanoa,b, David Orellana-Martína,b,∗, Mario J. Pérez-Jiméneza,b aResearch Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain bSCORE Laboratory, I3US, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain a r t i c l e i n f o a b s t r a c t Article history: Received 3 February 2023 Received in revised form 11 July 2023 Accepted 14 July 2023 Available online 20 July 2023 Keywords: Natural computing Virus machines Functions computing Finite sets Natural computing is a research area of computer science where different models of computation arise from the inspiration of real-life natural processes. In particular, virus machines are devices inspired by the transmission of viruses between different hosts, and how they replicate in the organism. This paradigm provides devices that can be seen as a network of hosts where the communication between them is controlled by a set of instructions that lead to the transmission of viruses. Virus machines can be seen as generating devices, computing devices and recognizing devices, depending on the possible input and the output of the systems. In this work, we present some machines generating basic sets, computing basic functions and we present recognizer virus machines, capable of solving decision problems in order to create a new complexity theory paradigm with virus machines. ©2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/). 1. Introduction In the area of Natural Computing, several different computing paradigms have arised inspired by some physical/biological real-life processes. This is the case in DNA computing [1], membrane computing [2], artificial neural networks [3]and cellular automata [4], among others. A computing paradigm is a framework where different models of computation with common characteristics coexist. From the basic model [5]to attention networks [6], several types have been defined in the framework of neural networks [7–13], as new requisites are imposed by new problems. They have been demonstrated to be very good models in a wide spectrum of applications [14–17]. In the framework of membrane computing, three main variants were defined depending of their structure: cell-like membrane systems [2], tissue-like membrane systems [18]and neural-like membrane systems [19], although several other classes of P systems have been defined [20–26]. These models have been applied to very different fields [27–31]. In 2015, the paper [32]presented a new model of computation inspired by the way viruses spread between hosts and replicate their genetic code by “tricking” the host entities. Then, some papers related with the universality of these devices have been published [33–35]. Lately, the area has been revisited and some new results have been obtained [36]. In this work, we focus on the design and formal verification of virus machines solving “simple” problems, being easy ✩This article belongs to Section C: Theory of natural computing, Edited by Lila Kari. *Corresponding author at: Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain. E-mail addresses: aramirezdear[email protected] (A. Ramírez-de-Arellano), dor[email protected] (D. Orellana-Martín), [email protected] (M.J. Pérez-Jiménez). https://doi.org/10.1016/j.tcs.2023.114077 0304-3975/©2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/). A. Ramírez-de-Arellano, D. Orellana-Martín and M.J. Pérez-Jiménez Theoretical Computer Science 972 (2023) 114077 to prove and understand the corresponding solutions. This paper is an extension to the paper “Generating, computing and recognizing with virus machines” presented in the 23rd Conference on Membrane Computing located in Trieste, Italy [37]. In the present work, new machines generating and recognizing finite sets are introduced. In particular, the machines presented in Section 3.3 that generate finite sets and the machines presented in Section 5.3 that recognize finite sets. The work is organized as follows: In Section 2, the definition of virus machines is given, and both the syntax and semantics of them are detailed. Section 3is devoted to the design and verification of four virus machines in generating mode. In the next section, some virus machines computing different functions are introduced, giving an explicit verification of their behavior. In Section 5, recognizer virus machines are introduced in addition to a computational complexity class with virus machines and three virus machines solving decision problems are explained. The paper finishes with some conclusions and open research lines in the area. 2. Virus machines Virus machines were introduced in [32]as universal devices capable of simulating register machines if no restrictions are imposed, and simpler languages can be recognized if there are restrictions in the number of hosts, instructions or viruses present in the machines. Now we recall the definition of a virus machine. Definition 1. A virus machine of degree (p, q), p, q ≥1is a tuple =(,H,I,DH,DI,GC,n1,...,np,i1,hout), where: 1.  ={v}is the singleton alphabet; 2. H={h1, ..., hp}and I={i1, ..., iq}are ordered sets such that v /∈H∪I, H∩I=∅ and hout ∈Hor hout =h0; 3. DH=(H∪{hout}, EH, wH)is a weighted directed graph, where EH⊆H×(H∪{hout}), (h, h) /∈EHfor each h ∈H, out −degree(hout) =0 and wHis a mapping from EHonto N\{0}; 4. DI=(I, EI, wI)is a weighted directed graph, where EI⊆I×I, wIis a mapping from EIonto N\{0}and the outdegree of each node is less than or equal to 2; 5. GC=(VC, EC)is an undirected bipartite graph, with VC=I∪EHbeing {I, EH}the partition associated with it: every edge connects an element from Iwith, at most, one arc from EH; 6. nj∈N(1 ≤j ≤p). A virus machine (VM, for short) =(,H,I,DH,DI,GC,n1,...,np,i1,hout) of degree (p, q), can be viewed as an ordered set of phosts labelled by elements from H, where each host hjinitially contains njviruses, and an ordered set of q control instruction units labelled by elements from I. hout represents the output region, being a host if hout ∈H, and the environment of the machine if hout =h0. Arcs from the directed graph DHrepresent transmission channels through which viruses can transmit from one host hs(different from hout) to another different host hsor to the environment. The environment plays a passive role in virus machines, in the sense that it can only receive viruses from the device, but cannot take them back to it. Arcs from the directed graph DIrepresent instruction transfer paths. Finally, the undirected bipartite graph GCrepresents the instruction-channel network by which an edge (ij, (hs, hs)) indicates a control relationship between the instruction ijand the channel (hs, hs). Graphically, avirus machine of degree (4, 6)can be depicted as a heterogeneous network consisting of three graphs, as illustrated in Fig. 1. Each host is represented as a rectangle and each instruction is represented by a circle. Arrows between hosts represent transmission channels, arrows between instructions represent instruction transfer paths and edges between instructions and channels represent instruction-channel connections. The weights of the edges are represented as positive numbers besides the edge (if the weight is 1, then it is not represented). In the following paragraphs, the semantics of a virus machine will be described. First, we define the instantaneous description or a configuration Ctat an instant tof a virus machine by a tuple (a1, ..., ap, u, a0), where a0, a1, ..., ap∈Nand u ∈I∪{#}, where # /∈H∪{h0} ∪Iis an object that characterizes a halting configuration. The meaning of Ctis the following: at an instant t, each host hjcontains exactly ajviruses, the environment contains exactly a0viruses and, if u ∈I, then the instruction uwill be activated at step t+1, otherwise, then no instruction will be activated and the machine will halt. The initial configuration of a virus machine  =(, H, I, DH, DI, GC, n1, ..., np, i1, hout)is C0=(n1, ..., np, i1, 0). A configuration Ctyields configuration Ct+1in one transition step or computation step if we can pass from Ctto Ct+1(and we denote it by Ct⇒Ct+1) in the following form. 1. First, given that Ctis a non-halting configuration, we have that u ∈I. Then, the control instruction unit uis activated. 2. If uis attached to a channel (hs, hs), then the channel will be opened and: •If as≥1then only one virus is consumed from host hsand ws,scopies of vare produced in the region hs. 2 A. Ramírez-de-Arellano, D. Orellana-Martín and M.J. Pérez-Jiménez Theoretical Computer Science 972 (2023) 114077 Fig. 1. Virus machine of order (4,6). •If as=0then no viruses are consumed from host hsand no viruses are produced in the region hs. 3. If uis not attached to any channel then there is no transmission of viruses. 4. The next instruction to be executed is obtained as follows: •If out −degree(u) =2then there are two different instructions uand u such that (u, u), (u, u) ∈EI(with weights wu,uand wu,u , respectively). –If the instruction uis attached to a channel (hs, hs): ∗If as≥1then the next instruction corresponds to the highest weight path (max({wu,u, wu,u })). ∗If as=0then the next instruction corresponds to the lowest weight path (min({wu,u, wu,u })). ∗In either case, if wu,u=wu,u , the next instruction is selected in a non-deterministic way. –If instruction uis not attached to a channel, then the next instruction is selected in a non-deterministic way. •If out −degree(u) =1then the system behaves deterministically and uis the next instruction that verifies (u, u) ∈ EI. •If out −degree(u) =0then u =# and Ct+1is a halting configuration. A computation C=(C0, C1, ...) of a virus machine is a (possibly infinite) sequence of configurations such that C0is the initial configuration of and for each t∈N, Ct⇒Ct+1. A computation C=(C0, C1, ..., Ck)is called a halting computation if there exists a ksuch that Ckis a halting configuration; that is, u =#. An invariant is a formula φthat holds through all the computation of a virus machine. Let M=(, H, I, DH, DI, GC, n1, ..., np, i1, hout)be a virus machine of degree (p, q). The invariant φ≡Ct=(a1,t, ..., ap,t, ut, a0,t)holds if: (a) at configuration Ctof the virus machine t, the current instruction is ut; (b) the contents of the host i ∈{1, ..., p}at configuration Ctis ai,t; and (c) the contents of the environment at configuration Ctis a0,t. This formula can contain parameters that can lead to useful formulas for different configurations. For instance, the invariant φ(k) =Ck=(1, 0, i1, k), for 0 ≤k ≤9, indicates that the environment must contain exactly kviruses in the configuration Ckduring the first 10 configurations. This type of formula is useful to prove the correctness of devices such as virus machines. In this work, virus machines are used to generate sets of numbers, to compute functions over natural numbers and to solve decision problems. Thus, different definitions must be introduced to know what is to generate sets, to compute functions and to solve (decision) problems with virus machines. Definition 2. Let Fbe a (finite or infinite) set of natural numbers, and let |F|be the cardinal of F(i.e. the number of elements of F). We say that Fis generated by a virus machine if the following holds: •If Fis a finite set, then the virus machine has exactly |F|computations. Each one of the computations generate exactly one element from F, and each element of Fis generated by exactly one computation; that is, an element k ∈F is generated by means of a computation of if and only if there exists a computation of such that there exists k viruses in the region hout at the last step of the computation. •If Fis an infinite set, then the virus machine has infinite computations, and one of them is infinite. Each one of the finite computations generate exactly one element from F, and each element of Fis generated by exactly one computation; that is, an element k ∈Fis generated by means of a computation of if and only if there exists a 3 A. Ramírez-de-Arellano, D. Orellana-Martín and M.J. Pérez-Jiménez Theoretical Computer Science 972 (2023) 114077 computation of such that there exists kviruses in the region hout at the last step of the computation, and there exists a computation of that never halts. Definition 3. Let f:Nk→Nbe a function. We say that the function fis computable by a virus machine with kinput hosts if the following conditions are verified: •For each instance (x1, ..., xk) ∈Nk, the virus machine will have kinput hosts hr1, ..., hrk∈Hr, and in the initial configuration, the host hriwill contain exactly nri+xiviruses. •For each instance (x1, ..., xk) ∈Nk, the virus machine will have the following behavior: –If f(x1, ..., xk) =y, then the virus machine will halt and have exactly yviruses in the region hout in the last step of the computation. –If f(x1, ..., xk)is not defined, then the virus machine will not halt. Definition 4. Let X=(IX, θX)be a decision problem, where IXis a language over a finite alphabet (instances) and θXis a total boolean function over IX(predicate). We say that the decision problem is solvable in polynomial time by a family  ={(n) | n ∈N}of recognizer virus machines if the following conditions are verified: •The family is polynomial uniform by Turing Machines. •Exists a pair (cod, s)of functions over IX(computed in polynomial time) such that: –For each instance u ∈IX, s(u)is a natural number and cod(u)is a valid input of the recognizer virus machine (s(u)). –The family is polynomial bounded with respect to (X, cod, s), i.e. ∃ppolynomial such that ∀u ∈IX, (s(u)) +cod(u) halts in p(s(u)) steps. –The family is sound with respect to (X, cod, s), ∀u ∈IX. That is, if there exists an accepting computation of (s(u)) + cod(u), then θX(u) =1. –The family is complete with respect to (X, cod, s), ∀u ∈IX. That is, if θX=1, then every computation of (s(u)) + cod(u)is an accepting computation. Definition 5. We say that a decision problem X=(IX, θX)is solvable in polynomial time by a family  ={(n) | n ∈N}of virus machines with input, in a deterministic and uniform way (we denote it by X∈PVM), if there exists k ∈Nsuch that Xis solvable by the family in time bounded by a polynomial, in a deterministic and uniform way. 3. Generating virus machines In [34], the universality of virus machines is proved by showing their capacity to generate Diophantine sets. By using the non-deterministic nature of these devices, each computation is able to generate a different number, obtaining in this sense a device capable of generating an infinite set. In this section, we show two simple cases of generating machines (following the Definition 2) with some invariants that show the correctness of the corresponding virus machines and generating finite sets is also studied. Let us recall some notation: For each p, q, n ≥1, we denote by NVM(p, q, n)[34]the family of all subsets of Ngenerated by virus machines with at most phosts, qinstructions and all hosts having at most nat any instant of each computation. If one of the parameters p, q, nis not bounded, then it is replaced with ∗. 3.1. Generating even numbers Let  =(, H, I, DH, DI, GC, n1, n2, i1, hout), where: 1.  ={v}; 2. H={h1, h2}; 3. I={i1, i2, i3, i4}; 4. DH={H∪{hout}, {(h1, h2), (h2, h1), (h2, hout)}, wH}, where wH((h1, h2)) =1, wH((h2, h1)) =wH((h2, hout)) =2; 5. DI={I, {(i1, i2), (i1, i3), (i2, i1), (i2, i2), (i3, i3), (i3, i4)}, wI}, where wI((i1, i2)) =wI((i1, i3)) =wI((i2, i1)) = wI((i3, i4)) =1, wI((i2, i2)) =wI((i3, i3)) =2; 6. GC=(I∪EH, {(i1, (h2, h1)), (i2, (h1, h2)), (i3, (h2, hout))}); 7. n1=0, n2=1; and 8. hout =h0. A visual representation of this virus machine can be found in Fig. 2. Let us prove that for each n ∈N, there exists a computation of such that producing 2nviruses in the environment in the halting configuration, and there exists a nonhalting computation. Let 2nbe the number generated in the computation C=(C0, C1, ...) The following invariants hold in this machine: 4 A. Ramírez-de-Arellano, D. Orellana-Martín and M.J. Pérez-Jiménez Theoretical Computer Science 972 (2023) 114077 Fig. 2. Virus machine generating the set {2n:n∈N}. φ(k)≡C4k=(0,n+1,i1,0), for 0 ≤k≤n φ(k)≡C4k+1=(2,n,i2,0), for 0 ≤k≤n When the non-deterministic step from instruction i1goes to i3instead of i2, then the machine starts sending viruses to the environment, and it will take exactly nsteps, then instruction i4will be selected and therefore the system will halt in the following step, thus the following invariants hold: φ ≡C4n+1=(2,n,i3,0) φ ≡C4n+n+2=(2,0,i4,2n) φ(IV)≡C4n+n+3=(2,0,#,2n) From i1, anon-deterministic step selects the next instruction from {i2, i3}. It is easy to see that there exists an infinite computation taking into account the following configurations: C0=(0,1,i1,0) C1=(2,0,i2,0) C2=(1,1,i2,0) C3=(0,2,i2,0) C4=(0,2,i1,0) ... C8=(0,3,i1,0) ... When making the non-deterministic decision, the instruction selected in the step 4k +1can be always i2, thus making the machine non-halting. 3.2. Generating powers of two Let  =(, H, I, DH, DI, GC, n1, n2, i1, hout), where: 1.  ={v}; 2. H={h1, h2}; 3. I={i1, i2, i3, i4, i5, i6, i7}; 5 A. Ramírez-de-Arellano, D. Orellana-Martín and M.J. Pérez-Jiménez Theoretical Computer Science 972 (2023) 114077 Fig. 3. Virus machine generating the set {2n:n∈N}. 4. DH={H∪{hout}, {(h1, h2), (h2, h1), (h1, hout), (h2, hout)}, wH}, where wH((h1, h2)) =wH((h2, h1)) =2, wH((h1, hout)) = wH((h2, hout)) =1; 5. DI={I, {(i1, i2), (i1, i5), (i2, i2), (i2, i3), (i3, i4), (i3, i6), (i4, i4), (i4, i1), (i5, i5), (i5, i7), (i6, i6), (i6, i7)}, wI}, where wI((i1, i2)) =wI((i1, i5)) =wI((i2, i3)) =wI((i3, i4)) =wI((i3, i6)) =wI((i4, i1)) =wI((i5, i7)) =wI((i6, i7)) =1, wI((i2, i2)) =wI((i4, i4)) =wI((i5, i5)) =wI((i6, i6)) =2; 6. GC=(I∪EH, {(i2, (h1, h2)), (i4, (h2, h1)), (i5, (h1, hout)), (i6, (h2, hout))}); 7. n1=1, n2=0; and 8. hout =h0. A visual representation of this virus machine can be found in Fig. 3. Let us prove that for each n ∈N, there exists a computation of such that it produces 2nviruses in the environment in the halting configuration, and there exists a nonhalting computation. Let 2nbe the number generated in the computation C=(C0, C1, ...) Let αk=k i=02iThe following invariants hold in this machine: φ≡Cαk+k=(2k,0,i1,0), for 0 ≤k≤n,keven φ≡Cαk+k=(2k,0,i3,0), for 0 ≤k≤n,kodd When the non-deterministic step from instruction i1(respectively, i3) goes to i5(resp., i6) instead of i2(respectively, i4), then the machine starts sending viruses to the environment, and it will take exactly 2n+1steps, then instruction i7will be selected and therefore the system will halt in the following step, thus the following invariants hold: φ ≡C2n+n+1=(2n,0,i5,0),neven φ ≡C2n+n+1=(0,2n,i6,0),nodd φ(IV)≡C2·2n+n+2=(0,0,i7,2n) φ(V)≡C2·2n+n+3=(0,0,#,2n) From i1(respectively, i3), anon-deterministic step selects the next instruction from {i2, i5}(respectively, {i4, i6}). It is easy to see that there exists an infinite computation taking into account the following configurations: 6 A. Ramírez-de-Arellano, D. Orellana-Martín and M.J. Pérez-Jiménez Theoretical Computer Science 972 (2023) 114077 Fig. 4. Virus machine generating the finite set F. C0=(1,0,i1,0)C6=(4,0,i4,0) C1=(1,0,i2,0)C7=(4,0,i1,0) C2=(0,2,i2,0). . . C3=(0,2,i3,0)C13 =(0,8,i3,0) C4=(0,2,i4,0). . . C5=(2,1,i4,0)C23 =(16,0,i1,0) When making the non-deterministic decisions, the instructions i5and i6will never be selected in such a computation, thus making the machine non-halting. 3.3. Generating finite sets In this subsection, two different ways of generating the finite sets are studied. Lemma 1 (Host). Let F={m1, ..., mk}a ordered (from lower to higher) finite set of natural numbers greater than zero. Then Fcan be generated by a virus machine of 1host, mk+1instructions and mkviruses at each host at most. Proof. Let  =(, H, I, DH, DI, GC, n1, i1, hout), where: 1.  ={v}; 2. H={h1}; 3. I={i1, ..., imk+1}; 4. DH=(H∪{hout}, {(h1, hout)}, wH), where wH((h1, hout)) =1; 5. DI=(I, EI={(ia, ia+1) | ia∈I\imk+1} ∪{(ib, imk+1) | b ∈F}, wI), where wI((id, ie)) =1 ∀(id, ie) ∈EI; 6. GC=(I∪EH, {(if, (h1, hout))}) ∀if∈I\{imk+1}; 7. n1=mk; and 8. hout =h0. A visual representation of this virus machine can be found in Fig. 4. Let us prove that for each mj∈F, there exists a computation of such that it produces mjviruses in the environment in the halting configuration. Let mjthe number generated in the computation C=(C0, C1, ...), the following invariant holds in this machine: φ(x)≡Cx=(mk−x,i1+x,x), for 0 ≤x≤mj−1 From this, φ(mj)is true and instruction imjis reached; thus the non-deterministic step selects imk+1as the next instruction (if mj=mk, the decision is deterministic) and therefore the system will halt in the following step: Cmj+2=(mk−mj,#,mj) It is interesting to point out that, since all the connections from ij(1 ≤j ≤mk) to imk+1fulfil the restriction j ∈F, the only elements that can be generated are the elements from F. If we think of an element xgenerated from the virus machine that does not belong to F, we must think that there must exist a connection from ixto imk+1, and this path will only exist if x ∈F, that contradicts the premise of xnot belonging to F. 7 A. Ramírez-de-Arellano, D. Orellana-Martín and M.J. Pérez-Jiménez Theoretical Computer Science 972 (2023) 114077 Fig. 5. Virus machine generating the finite set F. Lemma 2 (Viruses). Let F={m1, ..., mk}an ordered (from lower to higher) finite set of k >1natural numbers greater than zero. Then Fcan be generated by a virus machine of k hosts, 2k instructions and 1virus at each host at most. Proof. Let  =(, H, I, DH, DI, GC, n1, n2, ..., nk, i1, hout), where: 1.  ={v}; 2. H={h1, h2, ..., hk}; 3. I={i1, ..., i2k}; 4. DH=(H∪{hout}, {(hl, hout) | hl∈H}, wH), where wH((hl, hout)) =nlfor 1 ≤l ≤k; 5. DI=(I, EI, wI), where EI={(i2a, i2k) | a ∈{1, ..., k −1}} ∪{(i2k−1, i2k), (i2(k−1)−1, i2k−2), (i2(k−1)−1, i2k−1)} ∪ {(i2a+1, i2a+2), (i2a+1, i2a+3) | a ∈{0, ..., k −2}}, wI((ij, ij)) =1 ∀(ij, ij) ∈EI; 6. GC=(I∪EH, {(i2k−1, (hk, hout))} ∪{(i2f, (hf, hout)) | f∈{1 ..., k −1}}); 7. n1=n2=···=nk=1; and 8. hout =h0. A visual representation of this virus machine can be found in Fig. 5. Let us prove that for each mj∈F, there exists a computation of such that it produces mjviruses in the environment in the halting configuration. Let mj= mkthe number generated in the computation C=(C0, C1, ...), the following invariant holds in this machine: φ(x)≡Cx=(1,1,...,1,i2x+1,0), for 0 ≤x≤j−1. From this, φ(j −1)is true and from instruction i2j−1a non-deterministic decision is made and goes to i2jwhich is attached to the channel (hj, hout)and i2kwill be activated in the next step, finally, the system will halt in following step: C2j+1=(1,1,...,1,0  host j ,1,...,1,#,mj). Let us suppose now that mkis generated, then the following invariant holds: φ(x)≡Cx=(1,1,...,1,i2x+1,0), for 0 ≤x≤k−2. From this, φ(k −2)is true and form instruction i2k−3a non-deterministic decision is made and goes to i2k−1which is attached to the channel going from, host h :mkto the environment. After that, i2kwill be activated so the system will halt in the following step: C2j+1=(1,1,...,1,0,#,mk).  8 A. Ramírez-de-Arellano, D. Orellana-Martín and M.J. Pérez-Jiménez Theoretical Computer Science 972 (2023) 114077 Fig. 6. Virus machine computing f(x)=0. Fig. 7. Virus machine computing f(x)such that dom(f(x)) =∅. Theorem 1. NFIN⊆NVM(1, ∗, ∗)and NFIN⊆NVM(∗, ∗, 1). 4. Computing virus machines From now on, since the number of elements present in the virus machines can grow and the description can be tedious to read, it is easy to depict them with graphics where the initial configuration is described (only for the smaller devices). Let us recall that i1is the initial instruction, and hout =h0. We follow the Definition 3to know what does it mean to compute a function by means of a virus machine. Since we are using virus machines as computing devices, we must have input for the machine. Let us recall, from [36], that a virus machine with input, of degree (p, q, r), p, q, r≥1is a tuple  =(, H, Hr, I, DH, DI, GC, n1, ..., np, i1, hout), where: •(, H, I, DH, DI, GC, n1, ..., np, i1, hout)is a virus machine of degree (p, q); and •Hr={hj1, ..., hjr} ⊆His the ordered set of rinput hosts and hout /∈Hr. The initial configuration of a virus machine with input (a1, ..., ar) ∈Nris given by (n1, ..., nj1+a1, ..., njr+ar, ..., np). We denote a virus machine with input (a1, ..., ar)by  +(a1, ..., ar). If there is a single input, it can be denoted by  +a1. In the graphical description, input hosts will be marked with a double border in the corresponding host. If more than one host is an input host, then their order with respect to the input tuple is the alphanumerical order. 4.1. Zero function A visual representation of this virus machine can be found in Fig. 6. It is easy to see that this machine always halts and does not send any virus to the environment. The computation would go from C0=(n, i1, 0)to C1=(n, #, 0), a halting configuration, no matter which is the input that is given to the virus machine. 4.2. Empty function A visual representation of this virus machine can be found in Fig. 7. It is easy to see that this machine never halts. The computation would go from C0=(n, i1, 0)to C1=(n, i2, 0), and then back to C2=(n, i1, 0), which is equivalent to C0. Thus the computation never halts. 9