Parallel virus machines

-

Natural Computing is a research field where diferent 2 computing paradigms arise from the inspiration of processes occurring in Nature. DNA computing [ 1 ], Mem- h3 h4 brane computing [ 2 ], artificial neural networks [ 3 ], and 2 evolutionary computing [ 4 ], among others, are widely studied while looking for alternative methods for solv- h1 h2 ing real-life problems that demand a large amount of resources in more eficient ways.

In 2015, virus machines were introduced as a model of computation inspired by the way viruses spread between 2 2 2 hosts and replicate their genetic code by “tricking” the 2 host entities. i2 i4 i6 graAphbiacsailclyvidreupsicmteadchaisneinofFdige.gr1e,e is(a,)tu,p,le Π ≥ = 1, i1 i3 i5 (Γ , , , , , , 1, . . . , , 1, ℎ) where Γ = Figure 1: Basic virus machine {} is the working alphabet, whose unique element is called a virus, = {ℎ1, . . . , ℎ} is the set of labels of the hosts, that will contain the viruses, = {1, . . . , } is the set of labels of the instructions, that will control the computational problems. The basic model is, by definifunctioning of the system, is the graph of the hosts, tion, a sequential model of computation. Thus, it is easy connecting them through channels, that will be opened to see that from the computational complexity point of by the instructions and will let viruses pass from one host view, these devices will only be able to solve from the to other one, is the graph of the instructions, that will complexity class P. control the flow of the computation, connects the in- Several bio-inspired models of computation have instructions with the channels they will open, 1, . . . , cluded diferent features to increase their computational are the initial number of viruses in each host, 1 is the eficiency, taking inspiration from some elements present in real-life processes. The most basic variant changes the initial instruction and ℎ ∈ ∪ {ℎ0} is the output region, that can be either a host or the environment. If initial instruction 1 of the tuple by a set of initial ina virus passes through an open channel, then the next structions 0, that will be executed at the same time. In instruction will be the one connected to the current in- this generalization, when two instructions open the same struction by the edge with the higher weight; otherwise, channel, both take the same decision concerning which the selected instruction will be connected by the edge path to take for selecting the next instruction. Since only with the lower weight. If no instructions are connected one instruction can be selected from another instruction, to the current instruction, the following instruction is the number of active instructions will decrease throughdenoted by # and the computation halts. out the computation. The computation halts when the

In previous works, it has been demonstrated that this set of current active instructions is the empty set. model of computation is computationally complete; that Another interesting approach is to let instructions conis, its power is equivalent to the power of a Turing ma- trol more than one channel; that is, in the graph , one chine. Apart from that, it has been demonstrated to be a instruction can be connected to more than one channel. good model of computation for solving diferent types of Diferent possibilities arise from this variant. Let us suppose that the instruction is connected to channels.

When should select the edge with the higher weight? When at least one virus goes through one channel? When all the channels transport a virus? When the majority ITAT’23: Information technologies – Applications and Theory, September 22–26, 2023, Vysoké Tatry, Slovakia " [e-mail] (D. Orellana-Martín) 0000-0002-2892-6775 (D. Orellana-Martín)

© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License of channels have moved a virus? The diferent choices CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) will lead to diferent models that work in a very diferent way.

Even when these variants are not able to solve NPcomplete problems eficiently, these new ingredients are really interesting for some applications, improving the running time for previously designed solutions. When a real-life cell replicates its ADN, without realizing it, it replicates also the genetic code of the virus. This behavior can be abstracted as a division of the host entity, duplicating its entire genetic code (the connections and internal elements). Potentially, this type of instruction could lead to presumably eficient virus machines, as it happens in the framework of membrane computing [ 5 ].

Acknowledgments The research described in this work is supported by the Zhejiang Lab BioBit Program (Grant No. 2022BCF05).

References

[1] Gh . Păun, G. Rozenberg , A. Salomaa , DNA Computing, Springer Berlin Heidelberg, 1998 .

[2] Gh . Păun, G. Rozenberg , A. Salomaa , The Oxford Handbook of Membrane Computing , Oxford University Press, Inc., USA, 2010 .

[3] S. S. Haykin , Neural networks and learning machines , third ed., Pearson Education , Upper Saddle River, NJ, 2009 .

[4] A. Eiben , J. Smith , Introduction to Evolutionary Computing, Springer Berlin Heidelberg, 2015 .

[5] G. Păun , Computing with membranes: Attacking np-complete problems , in: I. Antoniou , C. S. Calude , M. J. Dinneen (Eds.), Unconventional Models of Computation, UMC'2K , Springer London, London, 2001 , pp. 94 - 115 .