Virus machines: an unconventional computing paradigm

Universidad de Sevilla Dpto. de Ciencias de la Computaci´on e Inteligencia Artificial Virus Machines: An Unconventional Computing Paradigm Memoria presentada por Antonio Ram´ırez de Arellano Marrero para optar al grado de Doctor por la Universidad de Sevilla Antonio Ram´ırez de Arellano Marrero VºBºpor el director de la tesis Dr. D. David Orellana Mart´ın Sevilla, 9 de abril de 2024 Acknowledgements A lo largo de mi carrera como matem´atico, siempre me ha apasionado buscar invariantes, bien sean geom´etricos, algebraicos, topol´ogicos, computacionales, etc. sin percatarme que el invariante m´as importante siempre ha estado delante m´ıa: mi familia y amigos. Gracias de coraz´on a todas las personas que han estado en este precioso, y a la vez arduo, camino de la tesis, sois parte tambi´en de cada idea plasmada y cada letra escrita en esta memoria. Gracias, Mario, por acogerme en este maravilloso grupo, por demostrarme cada d´ıa que la ciencia requiere especialmente trabajo, trabajo, y m´as trabajo. A´un me sigo sorprendiendo de la vitalidad y la ilusi´on que te hace esto como si fuese el primer d´ıa. Gracias, David, por sacarme una sonrisa todo el rato y por ayudarme en todo (disculpa al resto del grupo la doble dosis de chistes malos). El poder hablar con los dos de ciencia es algo maravilloso, ¡y que nunca se acabe! Gracias al resto del grupo, por los buenos ratos y caf´es con Agust´ın, por esas bonitas charlas (no s´olo de beticismo) con Luis, dos jefes que tiran contigo y no de ti, y al resto del grupo ´ Alvaro, Carmen, Miguel ´ Angel y Jos´e Antonio, por todos esos buenos ratos vividos y que est´an por vivir. Gracias tambi´en a todos los compa˜neros del departamento de computaci´on, en especial a Chesko, el mejor compi de despacho, a To˜ni, por acoger desde el d´ıa uno a ese pobre chaval perdido con las clases, a Maricarmen y a Jos´e Luis, por salvarme de todos los l´ıos y hacer mi vida m´as f´acil all´ı. Muchas gracias a toda mi familia, a mis padres, por ense˜narme el precioso mundo de la ciencia, por cuidarme y quererme, a las Rosas de mi vida, a mi hermana, estoy orgullos´ısimo de ti; y a mi abuela por ser mi segunda madre y la mejor compa˜nera de piso, por haber sido la culpable de “los mejores a˜nos de mi vida”. A mi abuelo, por ense˜narme todo el trabajo, esfuerzo, y demostrarme con hechos que nunca es tarde para nada. A toda mi familia de Puerto Rico, por hacer que el amor y calor que me llega desde all´ı sin importar la distancia. Esto tambi´en es parte de mis amigos, a Ana, por ser “la que m´as me ha tenido que aguantar”, a ´ Angela, a Facu, a Paula por todas las fiestas y por estar ah´ı en las buenas y en las malas. A los que est´an m´as lejos, gracias a Arturo, por ense˜narme la fuerza y madurez para enfrentar incluso las peores batallas; a Ale, por m´as que mi primo, ser un gran amigo, la valent´ıa de irte s´olo a un nuevo pa´ıs; a Adolfo y Migue, se os echa de menos por aqu´ı abajo. Por ´ultimo, pero no menos importante, gracias a Isa, por la suerte de poder compartir contigo todo, por apoyarme, por ense˜narme la fuerza, la valent´ıa, y la intensidad con la que afrontas la vida. Esta tesis tambi´en es tuya, amor, te quiero. Contents I State of the Art 19 1 Preliminaries 21 1.1 Notation............................... 21 1.2 Computability Theory . . . . . . . . . . . . . . . . . . . . . . . 28 1.3 Computational Complexity Theory . . . . . . . . . . . . . . . . 33 1.4 Natural Computing . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.5 Cryptography............................ 45 2 Biology of Viruses 51 2.1 ≪Viruses, are viruses≫....................... 51 2.2 Generalfeatures........................... 53 2.3 Life cycle of viruses . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.4 Viral transmission . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.5 Computerviruses.......................... 59 II Basic Virus Machines 61 3 Virus Machines 63 3.1 Introduction............................. 63 3.2 Definition .............................. 64 3.3 Universality............................. 78 3.4 Bounded virus machines . . . . . . . . . . . . . . . . . . . . . . 96 4 Computing Mode 101 4.1 Formal Verification . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.2 Basic Arithmetic Operations . . . . . . . . . . . . . . . . . . . . 102 4.3 Small Universal Virus Machine . . . . . . . . . . . . . . . . . . 109 5 4.4 Pairing Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.5 Attacking Cryptosystems . . . . . . . . . . . . . . . . . . . . . . 115 5 Generating and Accepting Mode 125 5.1 Generating Virus Machines . . . . . . . . . . . . . . . . . . . . . 125 5.2 Recognizing Virus Machines . . . . . . . . . . . . . . . . . . . . 135 6 Uniform Solutions to SAT and Subsetsum 143 6.1 Uniform Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . 143 6.2 SAT .................................144 6.3 Subsetsum..............................153 III Extensions of Virus Machines 159 7 Parallelism in Virus Machines 161 7.1 Parallelism in the set of instructions . . . . . . . . . . . . . . . . 161 7.2 Clarifications and ambiguities . . . . . . . . . . . . . . . . . . . 164 7.3 Parallelism in the set of channels . . . . . . . . . . . . . . . . . 179 8 Virus Machines with Host Excitation 187 8.1 Spiking Neural P Systems . . . . . . . . . . . . . . . . . . . . . 188 8.2 Virus Machines with Host Excitation . . . . . . . . . . . . . . . 190 8.3 Computational Completeness . . . . . . . . . . . . . . . . . . . 193 8.4 Generating natural number sets . . . . . . . . . . . . . . . . . . 197 8.5 Computing Boolean Functions . . . . . . . . . . . . . . . . . . . 204 8.6 Border detection using virus machines . . . . . . . . . . . . . . 207 9 Nonlinear Parallel Virus Machines 213 9.1 Nonlinear Parallel Virus Machines . . . . . . . . . . . . . . . . . 214 9.2 Universality.............................219 9.3 Small Universal Computing Device . . . . . . . . . . . . . . . . 223 IV Conclusions 227 10 Conclusions and Future Works 229 10.1Conclusions .............................229 10.2FutureWorks ............................231 Appendix 233 A Formal verification of chapter 4 235 A.1 Least Prime Divisor . . . . . . . . . . . . . . . . . . . . . . . . . 235 A.2 Discrete Logarithm . . . . . . . . . . . . . . . . . . . . . . . . . 242 Bibliography 255 List of Figures 1.1 A chain of degree (20,4,5), and stickers associated to it. . . . . 38 1.2 Two 2-dimensional cellular automata neighbourhoods. . . . . . . 39 1.3 Nonlinear model of a neuron. . . . . . . . . . . . . . . . . . . . 41 1.4 General scheme of evolutionary computation. . . . . . . . . . . . 42 1.5 Visual example of a P system generating square numbers. . . . . 44 2.1 General Viral structure of a enveloped virus (left) and naked virus (right), illustration inspired in [64], and created with BioRender. com. ................................. 54 2.2 Image inspired in [31] and created with BioRender.com. . . . . 55 2.3 Life cycle of a DNA virus, created with BioRender.com. . . . . 56 2.4 Lytic and Lysogenic cycle. Ilustration inspired in [107], and created with BioRender.com. ................... 58 3.1 Example of a VM of degree (4,6).................. 68 3.2 VM Πempty +x1computing the empty function. . . . . . . . . . 70 3.3 VM Πmin + (x1, x2) computing the min function. . . . . . . . . 71 3.4 VM Πempty′generating the empty set. . . . . . . . . . . . . . . . 73 3.5 VM Πodd generating the set {1+2·n|n∈N}. ......... 74 3.6 VM Πequal + (x1, x2). ........................ 76 3.7 VM ΠADD simulating the instruction l1: (ADD(r), l2, l3). . . . . 80 3.8 VM ΠSUB simulating the instruction l1: (SUB(r), l2, l3). . . . . 81 3.9 VM ΠOUT PUT simulating the output of the system.. . . . . . . . 82 3.10 A VM generating an arithmetical progression. . . . . . . . . . . 98 3.11 Idea of extension for arithmetic progression. . . . . . . . . . . . 98 3.12 Idea of the union construction. . . . . . . . . . . . . . . . . . . . 99 4.1 Virus Machine Πadd + (a, b). ....................103 4.2 Virus Machine Πsub + (a, b). ....................105 4.3 Virus Machine Πmul + (a, b).....................106 9 16 13(1):21831, 2023. (doi:10.1038/s41598-023-49297-6). [JCR IF 2022: 4.6 (Q2 - 22/73 - Multidisciplinary Sciences)] 4. A. Ram´ırez-de-Arellano, D. Orellana-Mart´ın, and M. J. P´erez-Jim´enez. Bridges Between Spiking Neural Membrane Systems and Virus Machines. International Journal of Neural Systems, 2024. (doi:10.1142/S0129065724500345). [JCR IF 2022: 8.0 (Q1 - 25/145 - Computer Science, Artificial Intelligence)] Papers Presented in International Conferences 1. A. Ram´ırez-de-Arellano, D. Orellana-Mart´ın, and M. J. P´erez-Jim´enez. Basic arithmetic calculations through virus-based machines. In J. M. Ferr´andez Vicente, J. R. ´ Alvarez-S´anchez, F. de la Paz L´opez, and H. Adeli, editors, Bioinspired Systems and Applications: from Robotics to Ambient Intelligence, pages 403–412, Cham, 2022. Springer International Publishing. 2. A. Ram´ırez-de-Arellano, D. Orellana-Mart´ın, and M. J. P´erez-Jim´enez. Generating, computing and recognizing with virus machines. 23rd Conference on Membrane Computing, September 6-9, 2022. Trieste, Italy. (Best Paper Award) 3. A. Ram´ırez-de-Arellano, D. Orellana-Mart´ın, and M. J. P´erez-Jim´enez. Parallel Virus Machines. The 12th Asian Conference on Membrane Computing (ACMC 2023) and The Workshop on Affective Computing (AC2023), September 24-27, 2023, Chengdu, China, 1-15. Other publications Throughout the author’s research career, he has made contributions in other areas close to those developed in this report, which are listed below. Articles in journals indexed in JCR 1. A. Carriazo-Rubio, L. M. Fern´andez-Fern´andez and A. Ram´ırez-de-Are- llano. A Discrete Representation of the Second Fundamental Form. Mathematics, 10(13):2279, 2022. (doi:10.3390/math10132279). [JCR IF 2022: 2.4 (Q1 - 23/329 - Mathematics)] 17 2. X. Ronghao, X. Xiong, H. Peng, J. Wang, A. Ram´ırez-de-Arellano and Q. Yang. Feature fusion method based on spiking neural convolutional network for edge detection. Pattern Recognition, 147:110112, 2024. (doi:10.1016/j.patcog.2023.110112). [JCR IF 2022: 8.0 (Q1 - 25/145 - Computer Science, Artificial Intelligence)] 3. D. Orellana-Mart´ın, A. Ram´ırez-de-Arellano, J.A. Andreu-Guzm´an, A. Romero-Jim´enez and M. J. P´erez-Jim´enez. A protocol for solutions to DP-complete problems through tissue membrane systems. Mathematics, 11(13):2797, 2023. (doi:10.3390/math11132797). [JCR IF 2022: 2.4 (Q1 - 23/329 - Mathematics)] 4. B. Xhinzhu, H. Yanping, H. Peng, J. Wang, Q. Yang, D. Orellana-Mart´ın, A. Ram´ırez-de-Arellano and M. J. P´erez-Jim´enez. Sequence recommendation using multi-level self-attention network with gated spiking neural P systems. Information Sciences, 656:119916, 2024. (doi:10.1016/j.ins.2023.119916). [JCR IF 2022: 8.1 (Q1 - 25/145 - Computer Science, Information Systems)] 5. C. Zhou, L. Ye, H. Peng, Z. Liu, J. Wang, and A. Ram´ırez-De-Arellano. A Parallel Convolutional Network Based on Spiking Neural Systems. International Journal of Neural Systems, 34(05):2450022, 2024. (doi:10.1142/S0129065724500229). [JCR IF 2022: 8.0 (Q1 - 25/145 - Computer Science, Artificial Intelligence)] 6. J. Fu, H. Peng, B. Li, Z. Liu, R. Lugu, J. Wang, and A. Ram´ırez-De- Arellano. Multitask Adversarial Networks Based on Extensive Nonlinear Spiking Neuron Models. International Journal of Neural Systems, 2024. (doi:10.1142/S0129065724500321). [JCR IF 2022: 8.0 (Q1 - 25/145 - Computer Science, Artificial Intelligence)] 7. D. Orellana-Mart´ın, A. Ram´ırez-de-Arellano and M. J. P´erez-Jim´enez. Simulating and validating virus machines. PREPRINT Natural Computing, 2023. (doi:10.21203/rs.3.rs-2714903/v1). Papers Presented in International Conferences 1. A. Ram´ırez-de-Arellano, J. A. Rodr´guez-Gallego D. Orellana-Mart´ın, and S. Ivanov. Stochastic Virus Machines. Proceedings of the Nineteenth Brainstorming Week on Membrane Computing, January 24-27, 2023, Seville, Spain, 79-90. 18 2. A. Alhazov, R. Freund, S. Ivanov, A. Ram´ırez-de-Arellano, D. Orellana- Mart´ın, J. A. Rodr´ıguez-Gallego. P Systems with Reactive Membranes. Proceedings of the Nineteenth Brainstorming Week on Membrane Computing, January 24-27, 2023, Seville, Spain, 9-20. 3. A. Alhazov, R. Freund, S. Ivanov, A. Ram´ırez-de-Arellano, D. Orellana- Mart´ın, J. A. Rodr´ıguez-Gallego. P Systems with Reactive Membranes. Proceedings of the 24th International Conference on Membrane Computing (CMC2023) August 28-31, Opava, Czech Republic, 27-42. 4. J.A. Andreu-Guzm´an, L. Valencia-Cabrera, D. Orellana-Mart´ın, and A. Ram´ırez-de-Arellano. Exploring OGAPS with Communication Rules: A Comparative Study on TSP and GCP. The 12th Asian Conference on Membrane Computing (ACMC 2023) and The Workshop on Affective Computing (AC2023), September 24-27, 2023, Chengdu, China, 1-19. Software development For the experimental validation of the models presented in this thesis, we have developed and worked with a virus machine simulator that can be found on GitHub https://github.com/RGNC/virusmachines/tree/main. For deeper information see [68]. Part I State of the Art 19 1 Preliminaries The work presented in this thesis has been prepared with the intention of being self-contained. For this reason, we considered it convenient to denote a chapter in the description of all those basic concepts and results that are necessary for a better understanding of the text and, moreover, to fix the notations that are going to be used throughout the manuscript. After that, we introduce basic concepts of computability theory and computational complexity theory which allow us to explain the main objectives and results of natural computing. Finally, the chapter concludes with a historical introduction to cryptography, including the two classical public-key cryptosystems that will be attacked in this thesis, i.e., the RSA and DSA cryptosystems. 1.1 Notation 1.1.1 Natural Number Sets The set of natural numbers will be written as N={0,1, . . . }. Let us recall that 0 = ∅; 1 = 0 ∪ {0}; 2 = 1 ∪ {1}and so on. Given two subsets A, B ⊆N, we define: L(A;B) ={x∈N| ∃x0∈A, ∃n∈N,∃m1, . . . , mn∈N,∃x1, . . . , xn∈B (x=x0+m1·x1+· · · +mn·xn)}, 21 Chapter 1. Preliminaries 22 a subset L⊂Nis called a linear set if there exists a natural number c∈N, and a finite subset B⊂Nsuch that L=L({c};B). Asemilinear set of Nis a finite union of linear sets. The family of semilinear sets will be written as SLIN. Theorem 1.1. The family of semilinear sets SLIN of Nis closed with respect to finite union, finite intersection, and complementary. 1.1.2 Languages An alphabet Γ is a non-empty set whose elements are called symbols. A string (or word) over Γ is an ordered finite sequence of elements from Γ; in other words, a function from a natural number n∈Ninto the set Γ. The number nis called the length of the string. The empty string has length 0 and it is denoted by λ, in addition, the alphabet of only one element Γ = {v}, is called the singleton alphabet. We denote by Γ∗the set of all strings over Γ. The set Γ+is the set of all nonempty strings. A language over Γ is a subset of Γ∗. 1.1.3 Graphs For this section, several basic concepts related to graph theory are introduced, which will be used in this work. For more details, we refer to [18, 3]. An undirected graph Gis an ordered pair (V, E), where Vis a finite set whose elements are called vertices or nodes of the graph, and E⊆ {{x, y} | x, y ∈ V}is a finite set whose elements are called edges of the graph. An edge of the graph of the form {v, v}={v}is called a loop of the graph, a graph without loops is called a simple graph. If {u, v}is an edge of the graph, then we say that uand vare adjacent vertices or that they are neighbours, more over, we say that the edge is incident with uand v. An n-partite graph is a graph G= (V, E) in which the vertices can be divided into nnonempty disjoint sets V1, . . . , Vn⊆V, such that no two vertices within the same set are adjacent. In other words, it is a graph in which every edge connects a vertex of one set to a vertex of the another set, and we say that the partition associated with the graph is V=V1∪ · · · ∪ Vn. For the case of n= 2, we say that it is a bipartite graph. Adirected graph Gis an ordered pair (V, E), where Vis a finite set whose elements are called vertices or nodes of the graph, and E⊆ {(x, y)|x, y ∈V}, 1.1. Notation 23 whose elements are called arcs of the graph. Note that an undirected graph G= (V, E) can be viewed as a particular case of a directed graph G′= (V′, E′), where {x, y} ∈ E, if and only if (x, y),(y, x)∈E′. 1.1.4 Propositional Logic In this section, different concepts of propositional logic are reviewed in addition to fixing the notation needed for the work; for a deeper understanding, we refer to [10]. The language of propositional logic consists of an infinite numerable set V P of propositional variables, logic connectives ¬, for negation and ∨, for disjunction; ∧, conjunction; and auxiliary symbols such as parentheses (). The set PForm of the propositional formulas is the least set Γ which contains V P and verifies the following conditions: •If P∈Γ, then ¬P∈Γ; •if P, Q ∈Γ, then (P∨Q)∈Γ. From ¬and ∨, the logic connectives ∧,→,↔can be defined by the usual truth tables. Aliteral is a propositional variable or the negation of a propositional variable. A clause is the disjunction of a finite number of literals. A propositional formula is in conjunctive normal form (CNF) if it is the conjunction of a finite number of clauses; that is, every propositional formula in CNF is the conjunction of disjunctions of literals. Moreover, it can be assumed, without implying any restriction, that every propositional formula in CNF is in simplified form; that is, in every clause of such formula, there cannot be a literal and its negation, nor can there be two repeated literals. Atruth assignment is a function from V P in {0,1}. Every truth assignment can be naturally extended to a function from the PForm into {0,1}. A relevant truth assignment for a formula φis a function from the set of variables of that formula into {0,1}. Thus, if a propositional formula φhas nvariables, then the total number of relevant assignments for φis 2n. We say that a propositional formula, φ, is satisfactible if and only if there exists, at least, one truth assignment, a, such that a(φ) = 1. 1.1.5 Abstract Problems Informally, an abstract problem is a “general question to be answered that usually has several parameters whose values are not specified”[30]. To Solve an Chapter 1. Preliminaries 24 abstract problem is to give a response to the question asked. Thus, an abstract problem consists of a finite or infinite set of specific problems, called instances, which can be get by giving specific values to the parameters associated. Each instance has associated a set of possible solutions and the answer to the general question is related with this set. Now the formal definition of the concepts of search,optimization and decision problems. Definition 1.1.1. A search problem Xis a tuple (ΣX, IX, SX), where: •ΣXis a finite alphabet; •IXis a language over ΣXwhose elements are called instances of X; •SXis a map/function whose domain is IX. For each instance u∈IX,SX(u)is a set whose elements are called the solutions associated with the instance u. Solving a search problem, X, means that for each instance u∈IXfind an element from SX(u) if it is not empty, otherwise return no. Every search problem X= (ΣX, IX, SX) has associated a binary relation QXdefined as: QX={(u, z)|u∈IX∧z∈SX(u)}. In this sense, solving a search problem can be viewed as, given an instance u∈X, find an element z, such that (u, z)∈QX. Definition 1.1.2. An optimization problem Xis a tuple (ΣX, IX, SX, OX) such that: •(ΣX, IX, SX)is a search problem such that, for each u∈IX, we have SX(u)=∅. •OXis a function (called objective function) whose domain is IX, and for each instance u∈IX, and for each possible solution a∈SX(u), associated with u,OX(u, a)is a rational positive number. •For each instance u∈IX, there exists a solution a∈SX(u), such that one of these two cases holds: –∀b(b∈SX(u)⇒OX(u, b)≤OX(u, a)), called maximal solution for the instance u. –∀b(b∈SX(u)⇒OX(u, b)≥OX(u, a)), called minimal solution for the instance u. 1.1. Notation 25 Solving an optimization problem X, means that for each instance u∈IX, return a maximal or a minimal solution. We say that a deterministic Turing machine Msolves an optimization problem Xif given an instance u∈IX, the machine Mwith input u, returns one optimal solution associated with such instance. Definition 1.1.3. A decision problem Xis a search problem (ΣX, IX, SX), such that for each instance u∈IX,SX(u) = {0}or SX(u) = {1}. For the first case we say that the answer of the decision problem is no for the instance u, and for the second case we say that the answer is yes for the instance u. Solving a decision problem, X, means that for each instance u∈IXreturn yes if SX(u) = {1}, and return no otherwise. Any decision problem X= (ΣX, IX, SX) has associated, in a natural way, a language LXdefined as follows: LX={u∈Σ∗ X|SX(u) = {1}}. Analogously, each language Lover an alphabet Γ has associated a decision problem XL= (ΣXL, IXL, SXL) defined as follows: ΣXL= Γ, IXL= Γ∗where SXL(u) = {1}, for each u∈L, and SXL={0}, for each u /∈L. With these definitions, we can conclude that for each decision problem X, we have XLX=Xand for each language Lwe have that LXL=L. We say that a deterministic Turing machine (for short, DTM) Msolves a decision problem Xif the machine Mrecognizes or decides the language LX associated with the problem X; that is, for each string uover ΣX, if u∈LX, then the answer of the machine Mwith input uis yes, otherwise the answer is no. We say a non-deterministic Turing machine (for short, NDTM) solves a decision problem if the machine recognizes LX; that is, if for each string uover ΣXwe have u∈LXif and only if there exists at least one computation of the machine Mwith input usuch that the answer is yes. Moreover, we say that a NDTM M, which solves a decision problem X, works in polynomial time if there exists a polynomial p(n) that verifies the following condition: for each instance uof Xof size n, the machine Maccepts uif and only if, there exists at least a computation of Mwith input uwhose answer is yes and it is done in at most p(n) transition steps. Thus, a NDTM Mwhich solves a decision problem Xand works in time bounded by a polynomial p(n), verifies that for each instance uof size n, if none of the computations from Mwith input u returns yes, in at most, p(n) steps, then the machine Mrejects u. Some of the most studied computational complexity classes are related to decision problems, despite the fact that real-world problems are usually optimization problems. However, in this context, an interesting relationship Chapter 1. Preliminaries 32 his disciple S. Kleene developed the concept of λ-calculus, relating it directly to that of a computable function. For his part, in 1936, A. Turing used for the first time the abstract concept of machine to formalize the notion of algorithm and, therefore, the concept of computable function. By introducing the concept of computability through abstract machines, Turing sought to develop a theoretical system capable of modeling any procedure that could be intuitively interpreted as a computational procedure. Specifically, he tried to design a computational model in its most literal sense: he imagined a human-calculator, a person with paper and pencil, solving a given problem and tried to capture the essence of the process, focusing on the simplest steps into which the task he was performing could be broken down. In this context, the main idea of Turing consisted of considering machines as symbols manipulators instead of number crunchers [61, 43]. 1.2.1 Problem Decidability In a lecture given in 1934 at the Institute for Advanced Study in Princeton, Godel stated that recursive primitive functions verified an important property: for each set of values of their variables, the value of the variable could be computed by a finite process, adding that “the reciprocal seems to be true if the most general type of recursion is considered”. He further added that this result could not be proved because the notion of “finite computation” had not been defined mathematically and therefore the assertion should be understood as a heuristic principle. Everything seems to indicate that A. Church knew these ideas of G¨odel when, on April, 1935, he made public his famous thesis in a brief speech he gave at the meeting of the American Mathematical Society [7], in which it was stated that every effectively computable function had to be recursive. In April 1936, A. Church established the first example of a problem (related to first-order logic) that is mechanically unsolvable (through λ-calculable functions), answering in the negative the third question posed by Hilbert (the Entscheidungsproblem). In May 1936, A. Turing sent a paper to the journal Proceedings of the London Mathematical Society to be submitted to the review process with a view to its subsequent publication. In that paper, Turing provided, first, a proof of the unsolvability of the halting problem. Given a Turing machine, M, and an input data of the machine, u, determine whether M stops over u, through the machines he had introduced. Second, from that result and using a novel reducibility process, he established the undecidability of the first-order 1.3. Computational Complexity Theory 33 logic problem that had previously been analyzed by Church. Thirdly, Turing established the equivalence of his model and that of the λ-computable functions to finally announce the equivalence between the class of functions computable by his machines and the class of recursive functions (a result that he would publish in 1937 [100]). In this way, Turing demonstrated that the three models of computation, introduced formally and independently, were equivalent in the sense that everything that is calculable or solvable in one of these models is also calculable or solvable in any of the other two. In late 1936, Turing formulated a thesis similar to Church’s in terms that every intuitively computable function had to be computable by one of his machines. Bearing in mind that the class of recursive functions and the class of functions computable by Turing’s machines are the same, it follows that Church’s and Turing’s theses are “equivalent”. Perhaps because of this thesis, the three models mentioned above are called universal models or computationally complete models, capturing the intuitive idea of having the “highest possible computational power”. 1.3 Computational Complexity Theory Between 1943 and 1944, the British government developed a project during the Second World War to decipher German messages encrypted by the Enigma machine. This project was led by Alan Turing and resulted in the construction of the first general purpose machines, Colossus Mark I and Mark II, which were electromechanical and fully automatic, made at the beginning of the 40s of the last century. John von Neumann and his disciples, J.P. Eckert and J.W. Mauchly, were inspired by the ideas of Babbage and designed the von Neumann architecture, which enabled the construction of the first programmable electronic machine for general purpose in 1946, the ENIAC (Electronic Numerical Integrator And Computer). As computers were developed, the scientific community began to wonder: What problems can be solved by a real computer? To answer this question, certain instruments are required to quantify the least measure of computational resources that any algorithmic arrangement of a given problem needs. The theoretical calculation of the resources is crucial to obtain a measure of real computability. In the early 1950s, theories were developed to explore the efficient use of the first computers, which had limited processing and memory capabilities. This led to the concept of intrinsic complexity of a problem. At the beginning of Chapter 1. Preliminaries 34 the 1970s, computational complexity theory was established by J. Hartmanis, P.M. Lewis, and R.W. Stearns [47, 97], which classified languages and functions based on the time and space required for their generation or computation. This led to the classification of problems according to the computational resources needed to solve them. From this moment on, the analysis of the time and space needed by an algorithm to be computed by a general-purpose machine became crucial. For this study, several mathematical techniques were used, which also made possible the comparison of several solutions of a given problem; in this way, a new question arises: Given a decidable abstract problem, find best best algorithm that solves it. The idea of the best mechanical solution to an abstract problem is a measure of complexity that quantifies the computational resources needed. A protocol for finding an optimal algorithm, with respect to this measure of complexity, to solve a given abstract problem could be as follows: (1) determine an asymptotic lower bound of the amount of resources (in relation to the measure considered) that any algorithm that solves the problem requires for its execution, and (2) find an algorithm that solves the problem and, furthermore, the amount of resources it uses is exactly the same as the lower bound obtained before. If it is known what the optimal algorithm is for a given abstract problem, then the amount of resources needed to execute it will be the inherent computational complexity of the problem. However, this can be difficult to determine and, in some cases, it is not possible. This is what Manuel Blum demonstrated in 1967 with his Speedup Theorem, which states that for any complexity measure with minimum properties (such as the Blum Axioms [9]), there exists a decidable problem that does not have an optimal algorithm with respect to that measure. Therefore, it is not possible to define the computational complexity of a given problem individually, as there will be an abstract problem that cannot have a complexity associated with it. For this reason, the study of the complexity of abstract problems is done globally, i.e. by studying the computational complexity of a set of problems, which gives rise to complexity classes. The necessary ingredients to define such classes are the following: •Acomputing model which provides the devices where the problems will be solved, •acomputing mode which precise the concept of accepting an input, 1.3. Computational Complexity Theory 35 •acomplexity measure that allows the quantification of the resources used by the devices, •And a family of total computable functions between natural numbers that works as the upper bound of the resources used. The most classical example of this is Turing machines as a computing model, computing mode the deterministic one, the time as a complexity measure and as a bound a fixed family of functions between natural numbers (polynomial, logarithmic, exponential, etc.) which work as upper bound for the amount of resources depending on the instances of the problem. 1.3.1 Tractability and Intractability Computational complexity theory provides tools to measure the degree of difficulty of the mechanical solution of abstract problems, both in absolute terms (inherent complexity of a problem) and in comparative terms with other problems (computational complexity classes). The fundamental objective of this theory is the classification of problems by means of their practical algorithmic solvability, that is, problems that have mechanical solutions that can be executed on real machines for problem instances of sufficiently large size. For this purpose, the concept of efficiency or practical solvability is defined through the concept of polynomial-time computability. This concept was explicitly introduced in the 1960s by A. Cobham [15], and J. Edmonds [24], although J. von Neumann [105] had established in 1953 a distinction between algorithms running in polynomial time and those running in exponential time. In addition, Edmonds called good algorithms (with respect to time as a measure of complexity) those running in polynomial time and considered them as algorithms intractable or tractable by real machines. An algorithm is considered to be efficient with regards to a complexity measure if the amount of resources used is limited, in the worst case, by a polynomial function of the input size. This creates a boundary between practical solvability (tractability) and unsolvability (intractability) of abstract problems. This boundary is set with polynomial functions due to their stability with basic arithmetic functions and their relatively slow rate of increase. The importance of computational complexity theory in modern cryptography is undeniable; the security of current cryptosystems is based on the computational hardness of the abstract problems underlying the decryption process, which will be discussed in more detail in Section 1.5. Chapter 1. Preliminaries 36 1.4 Natural Computing How can we outperform machines nowadays? Are there computable functions for computing models that Turing machines cannot do? Since the definition of a Turing machine provides universal devices (Turing-Church thesis), the most computational power is achieved, nevertheless, the efficiency of these devices still can be improved. Computer science has developed a branch to address this problem, known as Natural Computing [21, 66, 91]. This field of study looks into models and computational techniques that are inspired by nature, as well as examining natural phenomena in terms of information processing. Natural computing can be differentiated in three main categories: (1) those that draw inspiration from nature to create new problem solving techniques; (2) those that use computers to replicate natural phenomena; and (3) those that use natural materials (e.g., molecules) to compute. This work can be included in the (1) category, and it will be the focus of this section. It is also important to highlight the relevance of quantum computing in the field of Unconventional Computation, nevertheless, it is still not clear in the computer science community whether it belongs to Natural Computing or not. Because of this, it will not be studied in more depth in this work, but some references are recommended [45, 96]. The main research fields that make up this branch bio-inspiration are DNA computing,cellular automata,artificial neural networks,evolutionary computing, and membrane computing, among others. This section provides a brief overview of the basics of natural computing, more precisely, the fields mentioned above, focusing on the biological motivation and some design concepts. 1.4.1 DNA Computing The father of this entire branch of natural computation was L. Adelman in 1994 [2], where he demonstrated a novel technique to solve a version of the Hamiltonian path problem, using DNA as a method of computation. This field, called DNA computing, not only includes theoretical inspiration from biochemistry, but also studies real-world applications [25] and experiments in new biological hardware implementations [37]. For a theoretical overview, we refer to [75]. There are several computing models based on or inspired by DNA, in this subsection, an overview of the three most classical ones is presented: •Adelman model. This computing model was based on filtering proce- 1.4. Natural Computing 37 dures. It is defined an aggregate over a alphabet Σ, as a multiset of elements of Σ, and a tube a multiset of aggregates over Σ. The basic molecular instructions are given below. – Extract(T, s). The inputs are a tube Tand a symbol s∈Σ, and the outputs are two tubes: +(T, s) = {σ∈T:s∈σ}and −(T, s) = {σ∈T:s /∈σ}; – Mix(T1, T2). The inputs are two tubes T1, T2, and returns T1∪T2; – Detect(T). The input is a tube Tand returns Yes, if Thas an aggregate and No, otherwise. Moreover, for the unrestricted model, the Amplify(T, {T1, T2}) operation is included. It is interesting to note that only the Extract operations implement massive parallelism. This computing model is universal [6]. •Amos model. In this computing model, tubes are also fundamental; the main difference from the previous model is that now a tube over an alphabet Σ is a finite multiset of strings over Σ, that is, now the order matters. The basic molecular instructions now allow the elimination of a finite amount of symbols from a tube, copy and union of a finite set of tubes, and a novel instruction Selection(T), which randomly selects an element of T, it is not empty, return No, otherwise. Here, only the delete instruction offers massive parallelism. This computing model is universal [6]. •Roweis sticker model. This now includes a random access memory represented as: –Memory chain of degree (n, k, m), with n≥k·m. A simple DNA chain of length n, made of ksubchains of length m. –Stickers associated with a memory chain. A simple chain of length mcomplementary to a region. It can be depicted in 1.1. A region is activated if it is complemented by an associated sticker, and it is deactivated otherwise. A memory complex of degree (n, k, m),with n≥kis a double strand made of a memory chain as mentioned, complemented by some associated stickers. Now the separate,activate and deactivate, implement massive parallelism, and its universality was also proved in [6]. Chapter 1. Preliminaries 38 ATCGG AAAAA TCATA GCACT TAGCC AGTAT CGTGA TTTTT Figure 1.1: A chain of degree (20,4,5), and stickers associated to it. 1.4.2 Celullar Automata Acellular automaton [108] (for short, CA) is a computational system composed of an infinite array of cells, each with a state from a finite set. Cells modify their states according to a local update rule, which determines the new state based on the old states of the cell and its neighbours. All cells use the same update rule, which are applied simultaneously in all cells. This update is repeated at regular intervals, resulting in a time evolution of the system. CAs have been studied for more than half a century, with the first studies by John von Neumann in the late 1940s being inspired by biology and related to selfreplication in universal systems (Burks 1970 [11]; von Neumann 1966 [65]). Since then, CAs have become popular as discrete models of physical systems due to their several fundamental properties, such as being massively parallel, homogeneous, and having all interactions being local. Ad-dimensional cellular automaton consists of a d-dimensional grid of cells that can take a value from a finite set of integers. The value of each cell in the time step t+ 1 is a function of the values of a small local neighbourhood of cells in time t. Cells update their state simultaneously according to a given local rule [56]. Formally, a cellular automaton Ccan be defined as a tuple C= (S, s0, G, d, f),where Sis a finite set of states, s0∈S, are the initial states of the CA, Gis the cellular neighbourhood, d∈Nis the dimension of C, and fis the local cellular interaction rule, also referred to as the transition function. Given the position of a cell iin a regular d-dimensional uniform grid, its neighbourhood Gis defined by Gi={i, i +r1, i +r2, . . . , i +rn}, where nis a fixed parameter that determines the neighbourhood size, and 1.4. Natural Computing 39 rjis a fixed vector in the d-dimensional space. The most famous 2-dimensional neighbourhoods are the von Neumann and Moor neighbourhoods that can be visually seen in Figure 1.2. The transition rule fis a mapping from Snonto S, which takes a state si∈S, of a given cell ito another state from the set S. A uniform CA, fis identical for all cells, otherwise it is called nonuniform CA. For a finite-size CA of size N, where Nis the number of cells in the CA, a configuration of the grid at time tis defined as C(t) = (s0(t), s1(t), . . . , sN−1(t)), where si(t) is the state of cell iat instant t, the progression through time is given by the iteration of the global mapping Fdefined as F:C(t)→C(t+ 1), t = 0,1, . . . Von Neumann Neigbourhood Moore Neigbourhood Figure 1.2: Two 2-dimensional cellular automata neighbourhoods. 1.4.3 Artificial Neural Networks A milestone in this branch of Natural Computing was the work made by Mc- Culloch and Pitts in 1943 [59], which they introduced the first ever mathematical model of a neuron that gave rise to the artificial neural networks [27] Chapter 1. Preliminaries 40 (for short, ANN), defined as information processing systems inspired by the nervous system of the human brain. Artificial neural networks (ANN) present a number of features and performance characteristics in common with the nervous system, between them highlights: •Many basic information processing operations take place in individual components known as (artificial) neurons, nodes, or units. •These neurons are capable of both receiving and transmitting stimuli from other neurons and the external environment. •Neurons can be connected to one another forming neural networks. •Information (signals) are transmitted between neurons via connection links called synapses. •The effectiveness of a synapse, which is represented by its strength or weight, reflects the data stored in the neuron. •Gaining knowledge is achieved through a process called learning, which is responsible for adjusting the connection strengths (weight values) to the external stimuli. From a design point of view, an Artificial Neural Network (ANN) can be identified by three main characteristics: (1) a collection of artificial neurons, also known as nodes, units, or neurons; (2) the pattern of connections between neurons, referred to as the network architecture or structure; and (3) a method to determine the weight values, known as its training or learning algorithm. For this subsection we will review the most common types of neuron models, network architectures and learning algorithms. 1. The input signals that enter a biological neuron are conducted through channels located in the synapses, allowing ions to move in and out of the cell. This causes a membrane potential to form, which is the result of the integration of the neural inputs. If the membrane potential is over a certain threshold, an action potential (spike) is generated, causing neurotransmitters to be released at the end of the axon. This neurotransmitter then forms synapses with the dendrites of other neurons. In computational models, this process is represented by a weight between two neurons. The computing element used in most neural networks is 1.4. Natural Computing 41 an integrator, which calculates based on its connection strengths. Figure 1.3 shows a standard artificial neuron, which includes the synapses (with their weight values), the summing junction (integrator), and the activation function f(uk). x x x f(u ) y +1 w w w b 1 2 m km 2m 1m k k k uk Inputs Summing Junction Weights Activation Function Output Figure 1.3: Nonlinear model of a neuron. 2. Neurons in an ANN are organized into functional layers. Most ANNs have a standardized architecture, which consists of an input layer, zero, one or more hidden layers, and an output layer. Depending on the propagation of the signal, two categories of ANNs can be distinguished: feed forward networks, where the signal is propagated only in one direction from the input to the output layer, and recurrent networks, which have at least one loop. 3. The process of adjusting the weights in the network is referred to as learning. This is done by using an algorithm that assigns a value to each input stimulus. The input stimulus used to train the network is a set of input data. There are three main learning approaches: supervised, unsupervised, and reinforcement learning. Chapter 1. Preliminaries 48 semiprime factorization problem is also conjectured to be a computationally hard problem. A generalization of the semiprime factorization problem is the least prime divisor (LPD): “Given a natural number n≥2, determine the least natural number m≥2 such that mis a divisor of n”. Obviously, such mmust be a prime number. This problem can be characterized by the partial function FLPD defined as follows: FLPD(n) = mif and only if n≥2 and mis the least divisor of ngreater than 2. 1.5.1.2 DSA Cryptosytem For given real numbers aand b, the logarithm logbais a number csuch that bc=a. Analogously, in any group G, powers bkcan be defined as all integers k, and the discrete logarithm logbais an integer ksuch that bk=a. Notice that if Gis a cyclic group of order n, then a=bk=bk+j·nfor every integer j. In modular arithmetic, a number gis a primitive root modulo nif every number acoprime to nis congruent to a power of gmodulo n. That is, gis a primitive roof modulo nif for every acoprime to n, there is some integer kfor which gk≡amod n. That value kis called the index or discrete logarithm of ato the base gmodulo n. So gis a primitive root modulo nif and only if gis a generator of the multiplicative group of integers modulo n. A fundamental result in Arithmetic, the Fermat’s little theorem [106], states that if an integer pis a prime number, then, for any integer a, the number ap−ais an integer multiple of p;ap−1≡1 mod p. This justifies the use of the groups Z∗ pfor a prime number p, that is, the group of multiplication modulo the prime p. This group has pelements that can be represented by a generator gas G={e, g, g2, . . . , gp−1}, being ethe neutral eleme nt of G. The discrete logarithm problem (DLP) is the following: given a group G, a generator gof the group and an element xof G, find the discrete logarithm to the base gof xin the group G. It is conjectured that this problem is computationally hard problem. A decision version of this problem can be described as follows: given a generator gof the group G, an element xof the group G, and an integer k, determine whether or not xhas a discrete logarithm base gsmaller than k. This problem belongs to the complexity classes NP, co-NP and BPQ [93] as it can be reduced to the integer factorization problem stated before. This problem can be characterized by the partial function FDLP defined as follows: FDLP(g, p, x) = kif and only if 0 ≤k≤p−1 is the discrete logarithm of xto the base g, where x∈(Zp)∗and gis a generator of (Zp)∗. 1.5. Cryptography 49 It has yet to be demonstrated that it is not feasible to create an efficient algorithm for computing the discrete logarithm modulo pwhen p−1 is composed of “large” prime factors. Any large integer input nfor DSA is used as the modulus for both public and private keys. To break the DSA system, one must calculate the discrete logarithm in modulo n. The difficulty of solving the Discrete Logarithm Problem (DLP) for suitable choices of Gis in stark contrast to the relative ease of computing discrete exponentiation. This has made the DLP a fundamental component of many cryptographic applications, such as public-key encryption algorithms, digital signature schemes and key agreement protocols. Many systems, such as banks, government processes and systems with confidential data, rely on this method to ensure the security of verifying the identity of an individual or entity. Chapter 1. Preliminaries 50 2 Biology of Viruses The objective of this chapter is to introduce basic concepts related to viruses, from both a biological and a computational point of view, which will be used as inspiration for this thesis. Biological viruses are defined, and several characteristics are presented. More precisely, in the first section, we define the concept of a virus and we open the question: Are viruses alive? After that, we present the viral structure, composition, architecture, life cycle of viruses, and viral transmission. For more details on this field, see [52, 64, 107]. Finally, a brief overview of computer viruses is presented as the first inspiration of computer science in this biological structure. 2.1 ≪Viruses, are viruses≫ Although in the late 19th century Dimitri Iwanoski and Martinus W. Beijerinick began to suspect the existence of “contagious living fluids” that could transmit the disease called tobacco mosaic, which affects the tobacco plant, the true nature of viruses was not known until the middle of the 20th century. In fact, the Latin word virus, which means “poison”, was used until the beginning of the twentieth century to refer to any pathogenic agent. Viruses are very small infectious particles, between 20 and 300 nm (1nm = 10−9m), whose genetic material consists of a single nucleic acid, DNA or RNA. 51 Chapter 2. Biology of Viruses 52 They have a simple structural organization and replicate by a particular process that uses the molecular mechanism of a host cell. That is, they are obligate parasites because they require the metabolic machinery of a living host cell. Viruses can infect plants, animals, and bacteria. They have clear differences from cells such as the presence of only one type of nucleic acid and not both (although there are exceptions), an extremely simple structure, dependence on a host cell (obligate parasitism) and inability to divide from a preexisting virus, as both eukaryotes and prokaryotes do. Viruses also possess unique characteristics, such as being the world’s greatest source of genetic innovation, constantly ’inventing’ new genes, and being able to colonize their host permanently [98, 104]. This means that there is still much debate about whether viruses are living things. “Viruses are viruses” [54], this singular definition of viruses was presented by Lwoff in 1957 in order to highlight the difficulty and arbitrariness of the different “definitions” of viruses up to that time. He defined living organisms as independent units with integrated and interdependent structures and functionalities, therefore, he considered that viruses are not life since he did not consider them to be organisms. Luria, a virologist of the same era, defined a living organism [53], as one that exhibits individuality, historical continuity, and evolutionary independence rather than functional independence. Then, viruses fit into this definition. Later, Morowitz [55], in 1969, established that a living organism is one that extracts energy from the environment, uses it to perform physical or chemical work, converting energy into organization. Decades later, Harold [40], established that living things differ from non-living things in their ability to maintain, reproduce, and multiply states of matter characterized by an extreme degree of organization, viruses can modify elements of host cells such as cell membranes and cytoskeletons, reorganizing them into a very specific structure that would serve for viral replication. As a conclusion to this debate, despite being the inspiration for this work, virus replication is not mechanical; in fact, viruses have evolved to reorganize, coordinate, manipulate, and modify cellular structures and processes for their own benefit in order to replicate, evolve and, most importantly, perpetuate. Everything points to the fact that new perspectives must be taken to redefine living organisms; especially viruses, which are still defined with knowledge and concepts from the 1950s. 2.2. General features 53 2.2 General features Size The smallest viruses can measure only 20 nm and the largest viruses reach 300 nm, by comparison, cells usually measure on the order of 1000 nm. Due to this characteristic of a minute size, viruses can only be visualized with the aid of an electronic microscope. Chemical composition Viruses are composed mainly of deoxyribonucleic acid (DNA) or ribonucleic acid (RNA) and proteins. Some also contain lipids and carbohydrates. Viral structure The central part of the virus is the genome or nucleoid, which is surrounded by a protein coat called the capsid. In some viruses another more external structure is added, the envelope, and the viruses that have it are classified as enveloped viruses. When there is no envelope, it is said to be a naked virus. The viral genome contains the nucleic acid, either DNA or RNA, both of which can be single or double stranded. Also noteworthy is the polarity that the RNA strand can have, if it is positive it acts as messenger RNA, however, if it is negative the strand is reverse sequence or acts as an antimessenger. This is differential in the replication process, which we will see later. A visual example can be seen in Figure 2.1. The viral genome contains all genetic information and it is responsible for the infectious capacity of the virus. The capsid is the result of the agglomeration of smaller subunits called caspomers or morphological units. Its functions are to protect the genome, to provide the viral symmetry that we will see below, to facilitate the absorption of naked viruses and to have antigenic capacity. The assembly formed by the nucleoid and the capsid is called the nucleocapsid. The envelope is a lipoprotein bilayer derived from the nuclear membrane or cytoplasmic membrane of the host cell. Its functions are nucleocapsid protection, receptor binding and antigenicity. Chapter 2. Biology of Viruses 54 Figure 2.1: General Viral structure of a enveloped virus (left) and naked virus (right), illustration inspired in [64], and created with BioRender.com. Symmetry In viruses we do not speak of forms but of symmetries. Symmetry is the arrangement of the nucleocapsid in space. Different types can be observed: (a) helical, (b) icosahedral, and (c) complex. An example of them can be seen in Figure 2.2. •Helical symmetry is when the caspomers are arranged in a helix. This can be rigid, like a tube without a sheath, or flexible, rolled up on itself. Some examples are the influenza virus, measles virus, rabies virus, and the Ebola virus. •icosahedral viruses look like the polyhedron it is named after, this particular distribution of space is due to the good surface/volume ratio of this geometric body. Some examples are human papillomavirus, rhinovirus and hepatitis B virus. •Viruses with complex symmetry are those that do not have a clearly identifiable capsid and are none of the above. Some examples are poxviruses, geminiviruses, and many bacteriophages. 2.3. Life cycle of viruses 55 Figure 2.2: Image inspired in [31] and created with BioRender.com. 2.3 Life cycle of viruses Viruses are obligate intracellular parasites. Therefore, viruses must gain entry into target cells and usurp the cellular machinery of the host cell to replicate and propagate. These multiple steps involving viral propagation that occur within cells is termed the life cycle of viruses which can be differentiated into 3 stages: (1) entry, (2) genome replication, and (3) exit. This structure can be visualized in Figure 2.3. Entry Entry is the first step of virus infection, involving recognition of the viral receptor by a viral particle. Entry can be divided into four phases: (a) uptake or attachment, (b) penetration, (c) cytoplasmic trafficking and (d) decapsidation. Absorption or attachment is the first encounter between viral particles and host cells, which involves two types of proteins: attachment proteins and viral receptors. The interaction between these elements favors the entry of the virus into the cell. At this stage, tropism becomes evident, which is the tendency of the cell to react to an external stimulus, in this case a virus, allowing it to Chapter 2. Biology of Viruses 56 Figure 2.3: Life cycle of a DNA virus, created with BioRender.com. infect the cell. After uptake of virus particles by target cells, the next step is penetration into the cytoplasm. This can occur by the following mechanisms: (i) direct entry, (ii) endocytosis and (iii) fusion. •Directly, only the genome passes through. •By endocytosis, the cytoplasmic membrane invaginates (folding inward of a tissue) and engulfment of naked viruses occurs. A small vesicle is formed inside the cell containing the virus, which is then released. •Fusion is a mechanism by which two membranes fuse, the viral envelope and the cell membrane. In this case, the viral nucleocapsid enters directly into the cytoplasm, leaving the viral envelope behind. After penetration, the virus particles need to reach an appropriate site within the cell for replication of their genome. This process is called intracellular traffic. As virus particles approach their replication site, from the cell periphery to arrival, the capsid must be removed by cellular protein enzymes that degrade it, 2.3. Life cycle of viruses 57 a process referred to as decapsidation, which can also be considered intracellular traffic. Genome replication This is the most important stage of viral multiplication, differentiated into two main types according to viral nucleic acid, DNA or RNA. •For viruses with a DNA genome, transcription of a portion of the DNA occurs in the cell nucleus. While in the cytoplasm, translation of early proteins originates, these will help for DNA replication. Then, replication of the genome begins, which follows the same biochemical rules as cellular DNA. Finally, the synthesis of late proteins occurs in the cytoplasm, and these will form the viral capsid. •However, for viruses with an RNA genome, we must differentiate between positive-stranded RNA(+) and negative-stranded RNA(-) viruses. RNA(+) is sufficient to initiate infection since they act as mRNA. Negative strands need to synthesize mRNA using RNA(-) as a template, these strands are not infectious by themselves. These stages of replication can lead to various outcomes at the host cell level: to a productive infection with or without cytopathic effect, to an abortive infection (if not completed), to a mutation, to a dormant state if the virus is not released, or to a transformation if it remains in the cell, leading to changes in the cell. Release The release can be divided into 2 steps: (a) assembly or maturation and (b) liberation. •After replication of viral proteins and genomes, these are packaged into new virions (morphologically complete and infectious viral particle) that are ready for release from the host cell; this occurs in the nucleus for DNA viruses and in the cytoplasm for RNA viruses. In addition, extracellular maturation may be required; which is essential for the infectivity of some viruses. Chapter 3. Virus Machines 64 •The propagation of viruses can only be made between hosts or a host and the environment (that can be understood as a special host). Specifically, a virus machine can be viewed as an heterogeneous network whose nodes are called hosts that represent processing units. Each host will contain a number of viruses (only one kind of virus is studied). The hosts are connected by transmission channels allowing transmissions between the hosts or the environment and creating the host graph, which is a weighted directed graph (for short, WDG) where the weights are natural numbers that represents the replication rate by going through each channel. The process of virus transmission will be controlled by instructions in the sense that at any moment each channel is closed unless one instruction opens it. The instructions are activated individually following the semantics given by an instruction graph, which is also a WDG. Finally, each instruction is associated with, at most, one channel by a instruction-channel graph, so for an activated instruction attached to a channel, the channel will be opened allowing to transmit one virus and being replicated by the weight of the channel. Virus machines can be also studied with some input hosts, where an amount of viruses (information encoding) are added to some distinguished hosts as an input of the virus machine. In addition, the non-deterministic behavior of these devices allows us to study these devices in generating mode. Finally, virus machines can work in accepting mode. 3.2 Definition For this section, the computing paradigm that gives the title of the thesis, virus machines, is formally defined in addition to an explicit example. First, the syntax is presented: Definition 3.1. A Virus Machine of degree (p, q), p ≥1, q ≥1is a tuple Π = (Γ, H, I, DH, DI, GC, n1, . . . , np, i1, hout), where: •Γ = {v}is the singleton alphabet; •H={h1, . . . , hp}and I={i1, . . . , iq}are ordered sets such that v∈ H∪I,H∩I=∅and hout ∈ I∪Γ: either hout ∈Hor hout represents the environment (denoted by h0); •DH= (H∪{hout}, EH, wH)is a weighted directed graph, where EH⊆H× (H∪{hout}), such that (h, h)∈ EHfor each h∈H,out-degree(hout)=0 and wHis a mapping from EHonto N\ {0}; 3.2. Definition 65 •DI= (I, EI, wI)is a weighted directed graph, where EI⊆I×I,wIis a mapping from EIonto N\ {0}and the out-degree of each node is less than or equal to 2; •GC= (VC, EC)is an undirected bipartite graph, where VC=I∪EHbeing {I, EH}the partition associated with it: every edge connects an element from I(an instruction) with, at most, an arc from EH; •i1∈Irepresents the initial instruction; •nj∈N(1 ≤j≤p). AVirus Machine (VM, for short) of degree (p, q), Π = (Γ, H, I, DH, DI, GC, n1, . . . , np, i1, hout), can be viewed as an ordered set of phosts labelled with h1, . . . , hp, where host hjinitially contains exactly njviruses (njcopies of v), and an ordered set of qcontrol instruction units labelled with i1, . . . , iq. Symbol hout represents the output region which can be a host if hout ∈Hor hout can refer to the environment, in this case we denote 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. If s′= 0, viruses may exit to the environment. In any moment, at most one instruction is activated and then the channel (hs, hs′) (arc in GC) with weight ws,s′attached with it, will be opened. Then, ws,s′viruses will be transmitted/replicated from hsto hs′. By default, each channel is closed. Arcs from the directed graph DIrepresent instruction transfer paths, and they have associated within a weight. Finally, the undirected bipartite graph GCrepresents the instruction-channel network by which an edge (ij,(hs, hs′)) indicates a control relationship between instruction ijand channel (hs, hs′). In what follows, the semantics associated with the computing paradigm of virus machines is described. An instantaneous description or a configuration Ct at an instant tof a virus machine is described by a tuple (a1,t, . . . , ap,t, ut, a0,t) where a0,t, a1,t, . . . , ap,t are natural numbers, ut∈I∪ {#}, where # ∈ H∪h0∪I is an object for characterizing halting configurations. The meaning of Ctis the following: at instant tthe environment contains exactly a0,t viruses, the host hs(1 ≤s≤p) contains exactly as,t viruses, and if ut∈I, then the instruction utwill be activated at step t+ 1 (otherwise, if ut= #, then no instruction will be activated). The initial configuration of the system Π = (Γ, H, I, DH, DI, GC, n1, . . . , np, i1, iout) is C0= (n1, . . . , np, i1,0). A configuration Ct= (a1,t, . . . , ap,t, ut, a0,t) yields configuration Ct+1 = (a1,t+1, . . . , ap,t+1, Chapter 3. Virus Machines 66 ut+1, a0,t+1) in one transition step if we can pass from Ctto Ct+1 if we can pass from Ctto Ct+1 in the following form. (a) First, given that Ctis a non-halting configuration we have ut∈I. Then the control instruction unit utis activated. (b) If utis attached to a channel (hs, hs′) then the channel will be opened and the procedures depends of the value of as,t: •If it is zero, there is no virus transmission. •Otherwise, there is virus transmission, only one virus is consumed from host hsand ws,s′copies of vare produced in the region hs′, that is: as,t+1 =as,t −1, as′,t+1 =as′,t +ws,s′, where ws,s′=wH(hs, hs′). (c) If utis not attached to any channel then there is no virus transmission. (d) Object ut+1 ∈I∪ {#}is obtained as follows: •If out-degree(ut) = 2, then there are two different instructions ut′ and ut′′ such that (ut, ut′),(ut, ut′′ )∈EIwith weights wt,t′, wt,t′′ , respectively. If both weights are equal, then next instruction is chosen non-deterministically, otherwise: –If instruction utis attached to a channel (hs, hs′): ∗If there is virus transmission, then ut+1 is the instruction corresponding to the highest weight path (max{wt,t′, wt,t′′ }). ∗If there is no virus transmission, then ut+1 is the instruction corresponding to the lowest weight path (min{wt,t′, wt,t′′ }). –If instruction utis not attached to a channel, then the next instruction ut+1 (ut′or ut′′ ) is selected in a non-deterministic way. •If out-degree(ut) = 1, then the system behaves deterministically and ut+1 follows the unique possible path. •If out-degree(ut) = 0 then ut+1 = #, and Ct+1 is a halting configuration. 3.2. Definition 67 Acomputation is defined as a sequence (finite or infinite) of configurations such that Ct+1 is obtained from Ctafter applying the computation step described above. If the computation is finite, that is, for some k≥0, the sequence is C0,C1,...,Ck, where Ckis a halting configuration. In this case, it is called a halting computation, otherwise it is a non-halting computation. Virus machines can also be studied with an input, according to the following definition. Definition 3.2. A Virus Machine with input, of degree (p, q, r), p ≥1, q ≥ 1,1≤r≤pis a tuple Π = (Γ, H, Hr, I, DH, I, GC, n1, . . . , np, i1, hout), where: •(Γ, H, I, DH, DI, GC, n1, np, i1, hout)is a Virus Machine of degree (p, q). •Hr={hj1, . . . , hjr} ⊆ His the ordered set of rinput hosts, and hout ∈ Hr. If Π is a virus machine with input of degree (p, q, r), p ≥1, q ≥1,1≤r≤p and (α1, . . . , αr)∈Nr, the initial configuration of Π with input (α1, . . . , αr) is (n1, . . . , nj1+α1, nj1+1, . . . , njr+αr, . . . , np, i1,0). Thus, for each r-tuple (α1, . . . , αr), it is associated with an initial configuration as stated before. 3.2.1 An illustrative Example For a better understanding of these devices, an explicit example is defined besides the visual representation that will be used in this thesis. Let the VM of degree (4,6) defined as Π1= (Γ, H, I, DH, DI, DC, n1, n2, n3, n4, i1, hout) (3.1) where: •Γ = {v}, is the singleton alphabet; •H={h1, . . . , h4},I={i1, . . . , i6}and hout =h0/∈H; •DH= (H∪ {h0}, EH, wH), where EH={(h1, h2),(h1, h3),(h2, h3), (h3, h4),(h4, h2),(h4, h0)}, and wH(h1, h2) = wH(h3, h4) = 2, otherwise wH(hj, hj′) = 1; •DI= (I, EI, wI), where EI={(i1, i1),(i1, i2),(i2, i3),(i2, i4),(i3, i1), (i4, i5),(i4, i6),(i5, i6)}, and wI(i1, i1) = wI(i2, i3) = wI(i2, i4) = wI(i4, i6) = 2, otherwise wI(ij, ij′) = 1; Chapter 3. Virus Machines 68 •GC= (EH∪I, EC), where EC={(i1,(h1, h2)),(i2,(h1, h3)),(i3,(h2, h3)), (i4,(h3, h4)),(i5,(h4, h2)),(i6,(h4, h0))}; •n1, . . . , n4∈N. The VM Π1is depicted in Figure 3.1. Here, hosts are represented as squares whose value inside represents the initial amount of viruses, instructions are blue circles and the weights of the arcs of instruction and host graph are written unless the weight is 1, the instruction-channels arcs are represented by red dotted lines. n i h n i h n i h i n h i i 1 1 1 3 2 3 2 3 2 4 4 4 6 5 2 2 2 2 2 2 Host Graph Inst-Chan Graph Instruction Graph Figure 3.1: Example of a VM of degree (4,6). Specifically, the computation of this virus machine can be explained as follows. First, the initial configuration C0= (n1, n2, n3, n4, i1,0),. In the first step, instruction i1is activated and the channel (h1, h2) is opened. Next configuration will depend if n1is zero or not: •If n1= 0, then there is no virus transmission and next instruction is selected following the least weight path, that is instruction i2: C1= (0, n2, n3, n4, i2,0). •If n1>0, then one virus is consumed from h1and sent to h3replicated by 2, next instruction follows the highest weight path, that is instruction 3.2. Definition 69 i1again, this process will be repeated until h1is empty, that is, n1times, this loop is going to be used a lot throughout this work, for clarity we will write three dots as follows: C1= (n1−1, n2, n3+ 2, n4, i1,0),as h1(n1), · · · Cn1= (n1−n1, n2, n3+ 2 ·n1, n4, i1,0), From this configuration, as host h1has ran out of viruses, there is no virus transmission in the next step and next instruction follows the least weight path, that is instruction i2: Cn1+1 = (0, n2, n3+ 2 ·n1, n4, i2,0). In a simple glance, it can be seen that the second case generalizes the first, that is, after n1+1 transition steps, host h1is empty and the number of viruses at host h3are increased by 2 ·n1. Now instruction i2will be activated in the next transition step, this instruction is associated with channel (h1, h3), as h1is empty, there is no virus transmission. As the weights of the two possible next instructions are equal, non-deterministic behavior arises in this step and one of both instructions i3,i4, is non-deterministically selected creating two possible computations. For this example we will choose instruction i4, thus the following configuration is verified Cn1+2 = (0, n2, n3+ 2 ·n1, n4, i4,0), for this case let us assume that n2>0, then a virus is sent from h3to h4as channel (h3, h4) is attached to i4, and that virus is replicated by 2, next instruction follows the highest weight path, thus i6and the configuration holds Cn1+3 = (0, n2−1, n3+2·n1, n4+ 2, i6,0). From here, i6opens the channel (h4, h0), as h4is not empty, one virus is sent to the environment, finally, next instruction is the halting instruction # due to the out-degree of i6is zero, thus the following halting configuration is reached: Cn1+4 = (0, n2−1, n3+ 2 ·n1, n4+ 2,#,1) In summarize, after n1+ 4 transition steps, the machine halts for this computation and the output is 1. Now, before proving the universality of these computing devices, proper definitions and examples of the three work modes are presented. 3.2.2 Function Computing Mode Let Π a VM with input Π + (α1+· · · +αr), we say that the result of this machine working in computing mode is the total number of viruses sent to Chapter 3. Virus Machines 70 the output region during any computation. Now we can formally define virus machines providing function computing devices: Definition 3.3. Let f:Nk→Nbe a partial function. We say that fis computable by a virus machine Πof kinput hosts if for each (x1, . . . , xk)∈Nk the following holds: •If (x1, . . . , xk)∈dom(f), the result of Π+(x1, . . . , xk)halts and is equal to f(x1, . . . , xk). •Otherwise, every computation of Π + (x1, . . . , xk)is a non-halting computation. For example, let Πempty be the virus machine of degree (1,1,1) computing the empty function as depicted in Figure 3.2, that is, the function f:N→N, which verifies that dom(f) = ∅. It can be easily seen that there is only one possible computation and it is a non-halting computation. The configuration remains as Ck= (x1, i1,0) for every k≥0. x1 h1 i1 Figure 3.2: VM Πempty +x1computing the empty function. For another point of view, let Πmin be a virus machine with input of degree (3,3,2) computing the function min :N2→Nthat returns the minimum between two natural numbers, it can be seen in Figure 3.3. Πempty = (Γ, H, H2, I, DH, DI, GC,0, i1, hout), where, •Γ = {v}is the singleton alphabet; 3.2. Definition 71 •H={h1, h2, h3},H2={h1, h2},hout =h0, and I={i1, i2, i3}; •DH= (H∪ {h0}, EH, wH), where EH={(h1, h3),(h2, h0)}, and wH(h1, h3) = wH(h2, h0) = 1; •DI= (I, EI, wI), where EI={(i1, i2),(i1, i3),(i2, i1),(i2, i3)}, and wI(i1, i2) = wI(i2, i1) = 2, otherwise wI(ij, ik) = 1. •GC= (EH∪I, EC), where EC={(i1,(h1, h3)),(i2,(h2, h0))}. x1 h1 x2 h2 h3 i1i2 i3 2 2 Figure 3.3: VM Πmin + (x1, x2) computing the min function. The computation behaviour of this device depends on the input values: x1= 0 For this case, the computation of Πmin + (x1, x2) is the following: C0= (0, x2,0, i1,0), C1= (0, x2,0, i3,0),as h1(0), C2= (0, x2,0,#,0). Hence, the output of the system is 0. x2= 0 For this case, the computation of Πmin + (x1, x2) is the following: C0= (x1,0,0, i1,0), C1= (x1−1,0,1, i2,0),as h1(x1), C2= (x1−1,0,1, i3,0),as h2(0), C3= (x1−1,0,1,#,0). Chapter 3. Virus Machines 72 Hence, the output of the system is again zero 0. x2≥x1For this case, the following computation holds: C0= (x1, x2,0, i1,0),        C1= (x1−1, x2,1, i2,0),as h1(x1), C2= (x1−1, x2−1,1, i1,1),as h2(x2), · · · C2x1= (x1−x1, x2−x1, x1, i1, x1), C2x1+1 = (0, x2−x1, x1, i3, x1),as h1(0), C2x1+2 = (0, x2−x1, x1,#, x1). Hence, the output is x1, which is the minimum between x1and x2. x1> x2For this case, the following computation holds: C0= (x1, x2,0, i1,0),        C1= (x1−1, x2,1, i2,0),as h1(x1), C2= (x1−1, x2−1,1, i1,1),as h2(x2), · · · C2x2= (x1−x2, x2−x2, x2, i1, x2), C2x2+1 = (x1−x2−1,0, x2+ 1, i2, x2),as h1(x1−x2), C2x2+2 = (x1−x2−1,0, x2+ 1, i3, x2),as h2(0), C2x1+3 = (x1−x2−1,0, x2+ 1,#, x2). Hence, the output is x2, which is the minimum between x1and x2. In summarize, we have proven the “integrity of the machine”, as for any input (x1, x2)∈N, the machine halts and returns the min(x1, x2). That is, we have formally verified the machine, the technique that will be used in this thesis is defined in the following chapter, Section 4.1. 3.2.3 Generating Mode Taking the same behavior of output of the system, as the virus machines provides non-deterministic devices. Definition 3.4. We say that a virus machine Πin generating mode can generate a natural number nif the output of one of its computations is n. It is denoted by N(Π) the set of numbers generated by a virus machine Πin generating mode. 3.2. Definition 73 For this subsection, two other virus machines, in this case in generating mode, are presented: Let Πempty′be the virus machine of degree (1,1) generating the empty set which can be depicted in Figure 3.4: Πempty′= (Γ, H, I, DH, DI, GC,0, i1, hout), where, •Γ = {v},H={h1},I={i1}and only the instruction graph have arcs that is (i1, i1), with weight wI(i1, i1) = 1. h1 i1 Figure 3.4: VM Πempty′generating the empty set. It is clear that the computation never halts, thus no number is generated, that is, the empty set. Let Πodd be the virus machine of degree (2,5) generating the set of odd numbers which can be depicted in Figure 3.5: Πodd = (Γ, H, I, DH, DI, GC,2,0, i1, hout), where, •Γ = {v},H={h1, h2},hout =h0, and I={i1, . . . , i5}; •DH= (H∪ {h0}, EH, wH), where EH={(h1, h0),(h1, h2),(h2, h0), (h2, h1)}, and wH(h1, h2) = wH(h2, h0) = 2, otherwise wH= 1; •DH= (I, EI, wI), where EI={(i1, i2),(i2, i3),(i2, i5),(i3, i4),(i4, i5)}, and wI(ij, ik) = 1 for each (ij, ik)∈EI; Chapter 3. Virus Machines 80 1 h′hr 2 il1il′ 1 il2 il3 Figure 3.7: VM ΠADD simulating the instruction l1: (ADD(r), l2, l3). configurations are reached C′ 2(n+ 1,1, il2,0) or C′′ 2(n+ 1,1, il3,0). Thus, after 2 computation steps, the ADD-type instruction has been properly simulated. 3.3.1.2 Module ΠSUB Let ΠSUB = (Γ, H, H1, I, DH, DI, GC,0,0, hout) a virus machine of degree (2,3,1) if l2=l3, and of degree (2,2,1) if l2=l3, defined as follows: •Γ = {v}, H ={hr, h′′ }, H1={hr}, I ={il1, il2, il3}, hout =h′′ ; •DH= ({h0, hr, h′′ }, EH, wH), where EH={(hr, h′′ )}, and wH(hr, h′′ ) = 1; •DI= (I, EI, wI), where EI={(il1, il2),(il1, il3)}, and wI(il1, il2)=2, wI(il1, il3) = 1. •GC= (I∪EH, EC), where EC={(il1,(hr, h′′ ))}. The virus machine ΠSUB can be depicted in Figure 3.8. Now let us see that ΠSUB simulates the instruction l1: (SUB(r), l2, l3). For each n∈N, the initial configuration of ΠSUB +nis C0= (n, 0, il1,0) and its computation is: In the first step, instruction il1is activated, thus the channel (hr, h′′ ) is opened, and two possible computations are followed depending on n: 3.3. Universality 81 hrh′′ il1 il2 il3 2 Figure 3.8: VM ΠSUB simulating the instruction l1: (SUB(r), l2, l3). 1. If n > 0, then there is virus transmission, one host is consumed from hrand reaches h′′ . Next instruction will follow the highest weight path, that is, instruction il2with the configuration C1= (n−1,1, il2,0). 2. If n= 0, then there is no virus transmission and next instruction takes the least weight path, that is, instruction il3with the configuration C1= (n, 0, il3,0). In summary, we have been simulate properly the SUB-type instruction. 3.3.1.3 Module ΠOUT PUT Let ΠOUT PUT = (Γ, H, H1, I, DH, DI, GC,0, hout) a virus machine of degree (1,2,1), defined as follows: •Γ = {v}, H =H1={h1}, I ={ilh, iEND}, hout =h0; •DH= ({h0, h1}, EH, wH), where EH={(h1, h0)}, and wH(h1, h1) = 1; •DI= (I, EI, wI), where EI={(ilh, ilh),(ilh, iEND)}, and wI(ilh, ilh) = 2, wI(ilh, iEND) = 1. •GC= (I∪EH, EC), where EC={(ilh,(hr, h0))}. The virus machine ΠOUT PUT can be depicted in Figure 3.9. Let us simulate the output of the system, for each n∈N. The initial configuration of ΠOUT PUT +nis C0= (n, ilh,0) and its computation is: •Firstly, instruction ilhis activated, then, Chapter 3. Virus Machines 82 h1 ilhiEND 2 Figure 3.9: VM ΠOUT PUT simulating the output of the system.. 1. If n > 0, one virus is sent from host h1to the environment and next instruction is ilh, as it follows the highest weight path. 2. If n= 0, then there is no virus transmission and next instruction is iEND, as it follows the least weight path. •The instruction ilhis activated until the host h1is empty and then goes to instruction iEND. This takes us to the following configuration Cn+1 = (0, iEND, n), as out-degree(iEND) = 0, we reach the halting configuration Cn+2 = (0,#, n). Finally, the virus machine ΠMassociated with the register machine Mis the assembling of all modules of these types. Notice that the first instruction i1 in ΠMhas to be the instruction associated with label l0, that is, the instruction il0. Once the halting instruction lhis reached at M, the viruses from h1are sent to the environment. Therefore, Theorem 3.3.1 is proved. 3.3.2 Computing Partial Recursive functions The authors also proposed an alternate method to confirm the Turing-comple- teness of these devices, as described in [90]: Virus machines as function computing are used to prove the universality by showing that they can compute all partial recursive functions. For this purpose, another definition related with the concept of computation of a subset of Nkis needed: Definition 3.6. Let A⊆Nk, we say that Ais computed by a virus machine Π with kinput hosts working in the computing mode, if Πcomputes the partial characteristic function C∗ Aof A, defined as: C∗ A(x1, . . . , xk) = 1,if (x1, . . . , xk)∈A ↑,otherwise 3.3. Universality 83 Proof. The idea of this proof is to design the non-restricted virus machines such that they compute: 1. The basic or initial functions: constant zero, successor and projection functions. 2. The composition of functions, from virus machines computing the functions to be composed. 3. The primitive recursion of functions, from virus machines computing the functions that participate in the recursion. 4. The unbounded minimization of functions, from a virus machine computing the function to be minimized. 3.3.2.1 Modules In order to create virus machines that can compute any partial recursive function, they will be constructed in a modular manner. A module is a virus machine, with the initial instruction labeled as the in instruction and with at least one instruction labeled as an out instruction. The out instructions must have an out−degree of less than two, so that they can be connected to another instruction. This way, a module m1can be connected before another module m2by attaching the out instructions of m1to the in instruction of m2. The design of a module must be carefully planned to prevent inconsistencies with other modules and to enable the module to be reused. To meet the first requirement, we will assume that all the hosts (with the exception of those belonging to the module’s parameters) and instructions of a module are unique to that module, different from any other module or Virus Machine. The second condition is fulfilled if we guarantee that after the module has been executed, all its hosts, except its parameters, contain the same number of viruses as before the execution, excluding hosts that have been specially initialized. For this proof and the following, two kinds of modules are considered: action and predicate modules. The action modules are named as verbs and they require that out instructions are connected with the in instruction of the following module, or the following instruction of the virus machine. Predicate modules are named as questions and the out instructions are divided in yes or no representing the answer of the predicate, both are connected with the next instruction as in action modules. The modules used are the following: Chapter 3. Virus Machines 84 •EMPTY(h): action module that empties the host h. An internal host h′is introduced which will store all the viruses from h, thus it is not necessary to fix the number of viruses in h′for reusing it. h 0 h′ in send out 1 2 •ADD(h1, h2): action module that adds to the host h2, the amount of viruses in h1which remains equal. An internal host his needed, the idea behind this machine is to sent duplicated the number of viruses from h1 to h, then from this host one virus is sent to h2and other comes back to h1until his empty. Thus we have h1with the same number of viruses, hempty as in the beginning, and h2storing the addition mentioned. 0 hh1h2 2 in replicate send sendback out 1 2 2 1 •COPY(h1, h2): action module that sets the number of viruses from h1in h2without modifying h1. For this proposal, we only have to assemble two modules: It is important to note that if h2=hout, then the EMPTY(hout) module cannot be used, for those cases, it is understood that the empty module is skipped. in EMPTY(h2) ADD(h1, h2)out 3.3. Universality 85 •SET(h, n): action module that sets to nthe number of viruses in h, to do this, we only need an internal host h′initialized with nvirus and then use COPY(h, h′). •AREEQUAL?(h1, h2): predicate module that compares if the amount of viruses in h1and h2are equal or not. For this implementation, we first copy the values from h1and h2to two internal hosts h′ 1and h′ 2 respectively, and then decrease those hosts one by one the number of viruses until one of both is empty. Then we check if the other host is empty. In the alternative case the answer is no. Otherwise the answer is yes. Notice that the module can be reused because the hosts h′ 1and h′ 2 are initialized with the COPY modules. 0 h 0 h1′ 0 h2′ in COPY(h1, h′ 1) COPY(h2, h′ 2)send1 send2 finalcheck no no yes 2 2 1 21 1 •ISZERO?(h): predicate module that checks if host his empty or not. This has a very simple design due to the semantics of the virus machines. We send to an internal host h′one virus from h, if his empty, we answer yes, if not, then we return that virus to hand the answer is no. Finally, let us notice that a virus machine Π can be considered as an action module without parameters, but Π would be a module of only one use, to solve this problem, we would need to fix Π to its initial state, by means of the following module: •RESART(Π): action module that sets the number of viruses in each host hjof Π to its initial value nj. This module is created by assembling p modules, where pis the number of hosts of the machine: in SET(h1, n1)· · · SET(hp, np)out Chapter 3. Virus Machines 86 3.3.2.2 Basic Functions Let us start by describing the basic functions computed by virus machines: •The constant zero function,O:N→N, defined by O(x) = 0, for every x∈N, can be computed by the virus machine ΠOwith input: –The hosts are H={h, hzero}, and H1={h}is the input host and hzero =hout, both initialized as 0. –The initial and only instruction is halt. –The network has 0 arcs. It can be easily seen that, after one step, the machine halts and returns 0, for every Π + xwith x∈N. •The successor function,S:N→N, defined by S(x) = x+ 1, for every x∈N, can be computed by the virus machines ΠSwith input described as follows: –The hosts are HS={h, hone}, together with the internal hosts of the module ADD(h, hone) with H1={h}being the input host and hout =hone. –the initial values are zero except for hone which starts by 1. –The instructions IS={halt}, together with the instruction of the ADD(h, hone). –Initial instruction is the in instruction from ADD(h, hone). –The network is given by the following assemble: ADD(h, hone)halt Thus, the number of viruses in his added to host hone that already had one virus, and the successor function is computed. •The projection functions,πm j:Nm→N, with m≥1 and 1 ≤j≤m, defined by πm j(x1, . . . , xm) = xj, for every (x1, . . . , xm)∈Nm, can be computed by the virus machine Ππm jwith input: –The hosts are Hπm j={h1, . . . , hm, hout}, together with the internal hosts of COPY(hj, hout), with Hm={h1, . . . , hm}the input hosts. 3.3. Universality 87 –The initial values are zero. –The instructions Iπm j={halt}, together with the instructions of the module COPY(hj, hout). –The initial instruction is the in instruction of the COPY(hj, hout) module. –The network is given by the following assembler: COPY(hj, hout)halt Thus, the i-th component from hjis copied into hout, and the projection function is computed. 3.3.2.3 Composition of Functions Now composition of functions is simulated by virus machines: Definition 3.7. Let f:Nm− → N, and g1:Nn− → N,...gn:Nm− → N. Then the composition of fwith g1, . . . , gm, denoted by C(f;g1, . . . , gm), is a partial function from Nnto Ndefined as follows: C(f;g1, . . . , gm)(x1, . . . , xn) = f(g1(x1, . . . , xn), . . . , gm(x1, . . . , xn)) for each (x1, . . . , xn)∈Nn. Let Πf,Πg1,Πgmbe the virus machines with input, computing the function f, g1, . . . , gm, respectively. Let assume that for each fun ∈ {f, g1, . . . , gm}the virus machine Πfun of degree (pfun, qfun, r) where r=mif fun =fand r=n otherwise, is described as follows: •The hosts are Hfun ={hfun 1, . . . , hfun pfun }whose initial contents are nfun 1, . . . , nfun pfun , the output host hfun out , and the input hosts are hf 1, . . . , hf mand hfun 1, . . . , hfun n for fun ∈ {g1, . . . , gm}. •Instructions are Ifun ={ifun 1, . . . , ifun qfun }where the initial instruction is ifun start. •The network is defined by the three graphs Dhfun , DIfun and GCfun . The composition of fwith g1, . . . , gmcan be computed by the virus machine ΠC(f;g1,...,gm)with input: Chapter 3. Virus Machines 88 •The hosts are H={h1, . . . , hn} ∪ Hf∪Hg1∪ · · · ∪ Hgm, together with the internal hosts of the modules. •The initial values of the hosts are (0,...,0, nf 1, . . . , nf pf, ng1 1, . . . , ng1 pg1, . . . , ngm 1, . . . , ngm pgm) together with the internal hosts of the modules, input hosts are Hn= {h1, . . . , hn}and output host is hf out. •The instructions are I=If∪Ig1∪ · · · ∪ Igm∪ {halt}, together with the internal instructions of the modules. The initial instruction is the in instruction of the first module. •The network of the machine is given by the following assemble of modules divided in three stages: 1. First, we add the input into the input hosts of Πg1,...,Πgm. ADD(h1, hg1 1)· · · ADD(hn, hg1 n) ADD(h1, hg2 1)· · · ADD(hn, hg2 n) . . . ADD(h1, hgm 1)· · · ADD(hn, hgm n) 2. Second, we simulate the functions g1, . . . , gm. Πg1· · · Πg1 3. Finally, by intrucing the outputs of the previous simulations as input for Πf, we can simulate fand finish the computation. ADD(hg1 out, hf 1)· · · ADD(hgm out, hf m)Πfhalt 3.3. Universality 89 3.3.2.4 Primitive Recursion of Functions We turn our focus to the primitive recursion of functions simulated by virus machines: Definition 3.8. Let f:Nm− → N, and g:Nm+2− → N. Then the function obtained by primitive recursion from fand g, denoted by Rec(f;g), is a partial function from Nm+1 to Ndefined as follows, for each (x1, . . . , xm+1)∈Nm+1 we have Rec(f;g)(x1, . . . , xm+1) = f(x1, . . . , xm)if xm+1 = 0 g1(x1, . . . , xm, xm+1, y),otherwise, where y=Rec(f;g)(x1, . . . , xm+1 −1) Let Πfand Πgbe the virus machines with input simulating fand grespectively. Let us also suppose that both machines are described as in the previous section. Then, the function Rec(f;g) can be computed by the virus machine ΠRec(f;g)described as follows: •The hosts H={h1, . . . , hm+1, h′, hone, hout, h′ out} ∪ Hf∪Hg, in addition to the internal hosts of the modules. •The initial values are (0,...,0, nf 1, . . . , nf pf, ng 1, . . . , ng1 pg), whose input hosts are Hm+1 ={h1, . . . , hm+1}, and the outuput is hout. •The instructions are If∪Ig∪ {halt}, in addition to the instructions of the modules. •The network of the machine is constructed by assembling the following modules: 1. Notice that the function Rec(f;g) repeatedly compute the function gas many as (m+1)-th argument times, the first time the function fis calculated, all other times it is not necessary. 2. First, the input hosts of Πfis introduced as the input. ADD(h1, hf 1)· · · ADD(hm, hf m) Chapter 3. Virus Machines 96 AREEQUAL?(h+, h−) COPY(hx, hout)halt infinite loop yes no 3.4 Bounded virus machines Lastly, authors in [14] considered a more “realistic” case of virus machines in the way that the amount of viruses in each host during the computation is bounded. As expected, the computational power of virus machines falls drastically in this case. Let us recall from Section 1.1.1 that SLIN is the family of semi-linear sets of natural numbers. This section will be focused on proving a characterization of the semi-linear sets, for this purpose, the double inclusion technique is used, which differs from what the authors did in [14], but we think this demonstration could be more straightforward for the reader. Let us see the first inclusion, which is simpler to prove: Lemma 3.4.1. NV M(∗,∗, n)⊆SLIN, for each n≥0. Proof. Let Π be a VM with a bound in the number of viruses in each host, the number of instructions and hosts are given, and hence the total number of configurations reached by Π is finite. Let Cbe their set and let C0be the initial configuration of Π. We construct the right-linear grammar G= (N, {v},C0, P), where N=C and Pcontains the following rules: •C → C′, for C,C′∈Csuch that there is a transition C ⇒ C′in Π during which no viruses has been sent to the environment in that step. •Let Kbe the set of natural weights of the channels attached to the environment (which is finite because of the number of hosts is bounded). C → vkC′, for C,C′∈Csuch that there is a transition C ⇒ C′in Π during which one virus has been sent to the environment and replicated by k viruses in that step. •C → λ, for C ∈ Cand Cis a halting configuration. The way of controlling the derivation of the non-terminals in Nensures the fact that N1(Π) is the length set of the regular language L(G), hence it is semi-linear. 3.4. Bounded virus machines 97 The opposite inclusion is based on the observation that any semi-linear set of numbers is the union of a finite set with a finite number of arithmetical progressions. Thus, it suffices to prove the closure under union and the fact that singleton sets and arithmetical progressions are in NV M(∗,∗, n) for all n≥2. We will reach this in the following series of lemmas. Lemma 3.4.2. Each singleton {n}with n≥1, is in NV M(1,1,1) Proof. It suffices to take a virus machine with only one host, containing initially one virus, a channel of weight nfrom this host to the environment, and an instruction attached to that channel. In the first step, one virus is sent to the environment replicated by n. This leads to a halting configuration where the output is exactly n, hence the computed number is n. Lemma 3.4.3. Each arithmetical progression {n·i|i≥1}, n ≥1, is in NV M(2,4,2). Proof. For a given nas in the statement of the lemma, we consider the VM depicted in Figure 3.10. Instruction i1is activated and opens the channel which sends one virus to the environment replicated by n. Now the non-deterministic decision is taken: •In case i4is the instruction selected, this leads to a halting configuration and the number computed is n·1. •Otherwise, instruction i2and i3add one virus to the host h1and keeps h2with one virus. From this, we reach instruction i1and the process starts again. Consequently, the machine computes {n·i|i≥1}. Nevertheless, we have to compute not only these kinds of arithmetic progressions, but also of the form {n·i+r|i≥1}, for any n≥1 and r≥1. This is ensured by the following general result: Lemma 3.4.4. For all p, q, n ≥1, if Q∈NV M(p, q, n)and r≥1, then {x+r|x∈Q} ∈ NV M(p+ 1, q + 1, n). Proof. Let Π be a VM generating a given set Q. Then, we add to this machine a further host, instruction, and channel with weight rlabeled with haux, iaux and (haux, hout), respectively. This host initially contains one virus and iaux is Chapter 3. Virus Machines 98 1 h1 1 h22 n i1 i2 i3 i4 Figure 3.10: A VM generating an arithmetical progression. 1 haux r iaux i1 Figure 3.11: Idea of extension for arithmetic progression. attached to the new channel. Finally, if i1is the initial instruction of Π, then the arc (iaux, i1) belongs to the instruction graph and iaux is the new initial instruction. A visual idea is presented in Figure 3.11. In the first step, 1 virus is sent to the environment replicated by r, so rviruses are sent and then VM Π starts to compute, so if the machine Π computes x, then it has to be added to r. Now let us see the closure under union by the following lemma: Lemma 3.4.5. If Q1∈NV M(p1, q1, n1)and Q2∈NV M(p2, q2, n2)for some p1, q1, n1, p2, q2, n2≥1, then Q1∪Q2∈NV M(p1+p2, q1+q2+1, max{n1, n2}). Proof. Let Π1,Π2two virus machines that generate the given sets Q1, Q2resp. Let i11, i12be the initial instructions of Π1,Π2, respectively. We constructed a VM as suggested in Figure 3.12. In the VM the non-deterministic decision of instruction i1will enable either the (sub)machine Π1of the (sub)machine Π2. Hence, Π can compute whatever any of the two machines Π1,Π2can compute. 3.4. Bounded virus machines 99 i1 i11 i12 Figure 3.12: Idea of the union construction. All these lemmas lead us to the following result: Lemma 3.4.6. SLIN ⊆NV M(∗,∗, n)for all n≥2. This lemma in addition to Lemma 3.4.1 proves the following theorem: Theorem 3.4.7. SLIN =NV M(∗,∗, n), for all n≥2. An interesting direct application of this theorem is that all closure properties of the family SLIN are transferred to the family NV M(∗,∗,∗). For instance, we get the closure under sum, intersection and complement. But it fails in the case of the product of sets. Corollary 3.4.8. There are sets Q1, Q2in the family NV M(∗,∗,2) such that Q1Q2={nm |n∈Q1, m ∈Q2}is not in NV M(∗,∗,2). Proof. It suffices to consider Q1=Q2={2,3, . . . }. Then, from Lemma 3.4.4 we know Q1, Q2∈NV M(∗,∗,2). Since Q1Q2is the set of all composite numbers and this set is non semi-linear, from Theorem 3.4.7 it follows that Q1Q2/∈NV M(∗,∗,2). Chapter 3. Virus Machines 100 4 Computing Mode In this first chapter of the body part, virus machines in computing mode are closely studied in the sense of computing mathematical operations and functions, providing an interesting formal framework for attacking practical problems. The Chapter is organized as follows. First, the method applied to formally verify the virus machines is presented, next, Section 4.2 is devoted to define the basic arithmetic calculations (published in [84]), after that, computational power is again discussed by simulating a small universal virus machine (published in [86]), this section can be viewed as an extension of Chapter 3, where universality of virus machines simulating register machines. Section 4.4 computes the Cantor and G¨odel pairing functions (published in [86]). The Chapter ends with virus machines attacking the RSA and DSA cryptosystems. 4.1 Formal Verification From the simple examples presented in the previous chapter, one can notice that some loops were presented, for example, in the virus machine Πequal of Figure 3.6, instructions i1and i2where repeated each 2 steps. When more complex devices are studied, these loops are big enough to study apart and can highlight information about the behaviour of the machine, called, invariants. Furthermore, a method to formally verify that a computational device of a 101 Chapter 4. Computing Mode 102 model solves a given problem is to find these invariant formulas in some relevant loops of the device, in such a way that the veracity of those formulas at the end of the loops provides integrity. For example, for Πequal, the following invariant holds: φ(k)≡C2k= (n1−k, n2−k, 1+2k, i1,0), for each 0 ≤k≤min(n1, n2), this formula can be easily proved by induction, then, as it is true for each k, with 0 ≤k≤min(n1, n2), φ(min(n1, n2)) is also true, from here, the verification of the device becomes straightforward. For this and the following chapters, this method is widely applied, thus the formal verification of most devices will be focused on showing the invariant formulas that hold those devices. If these formulas become hard to reach, a detailed proof of them is provided. 4.2 Basic Arithmetic Operations In this section, we provide different modules for the different basic arithmetic operations; that is, addition, substraction, multiplication and division (both quotient and remainder). In these types of machines, the encoding of natural numbers will be given by an unary encoding; that is, the input number n∈N will be encoded by vn; that is, ncopies of the object v. In what follows, we introduce the different modules and some of their properties. This work was published in [84]. 4.2.1 Add module This module is a Virus Machines with two input hosts, where the two terms of the addition are introduced as an input. Let the Virus Machine Πadd = (Γ, H, Hr, I, DH, DI, GC,0,0, i1, hout) of range (2,3,2) where: •Γ = {v},H=H2={h1, h2},I={i1, i2, i3}; •DH= ({h0} ∪ H, EH, wH), where EH={(h1, h0),(h2, h0)}and wH(h1, h0) = wH(h2, h0) = 1; •DI= (I, EI, wI), where EI={(i1, i1),(i1, i2),(i2, i2),(i2, i3)}and wI(i1, i1) = wI(i2, i2)=2, wI(i1, i2) = wI(i2, i3) = 1; 4.2. Basic Arithmetic Operations 103 •GC= (I∪EH, EC), where EC={{i1,(h1, h0)},{i2,(h2, h0)}}; •hout =h0. A visual representation of this Virus Machine can be found in Fig. 4.1. The idea is that all the viruses present in the initial configuration to the environment (i.e. the output region). Let (a, b) be the input of Π; then the following invariants hold in this machine. a h1 b h2 i1i2i3 2 2 Figure 4.1: Virus Machine Πadd + (a, b). ϕ(k)≡ Ck= (k, a −k, b, i1), for 0 ≤k≤a In the first ksteps, aviruses go from h1to the environment. Then, in configuration ano viruses are available in h1, therefore the next instruction is i2. ϕ′(k)≡ Ca+1+k= (a+k, 0, b −k, i2), for 0 ≤k≤b From configuration Ca+1, instruction i2is executed until no more viruses are available in the host h2, and thus i3will be selected as the next instruction. Finally, in configuration Ca+b+2, instruction i3, that is not attached to any channel, thus next instruction is # and the computation halts. Therefore, Ca+b+3 = (a+b, 0,0,#). Chapter 4. Computing Mode 104 4.2.2 Sub module The Virus Machine presented computes the reduced difference, represented with the symbol b −operation; that is, ab −b=a−bif a≥b, 0 otherwise. The Virus Machine Πsub = (Γ, H, H2, I, DH, DI, GC,0,0,0, i1, hout) of range (3,3,2) where: •Γ = {v},H={h1, h2, h3},H2={h1, h2},I={i1, i2, i3}; •DH= ({h0} ∪ H, EH, wH), where EH={(h1, h3),(h2, h3),(h1, h0)}and wH(h1, h0) = wH(h2, h0) = 1; •DI= (I, EI, wI), where EI={(i1, i2),(i1, i3),(i2, i1),(i2, i4),(i3, i3), (i3, i4)}and wI(i1, i2) = wI(i2, i1) = wI(i3, i3)=2, wI(i1, i3) = wI(i2, i4) = wI(i3, i4) = 1; •GC= (I∪EH, EC), where EC={(i1,(h2, h3)),(i2,(h1, h3)), (i3,(h1, h0))}; •hout =h0. A visual representation of this Virus Machine can be found in Fig. 4.2. The idea is that viruses from h1are “countered” by viruses from h2and, if any virus remains in h1, then goes to the environment. Let (a, b) be the input of Π, and let mod(a, b) be the modulus operator; then the following invariants hold in this machine. ϕ(k)≡ Ck= (0, a − ⌊k 2⌋, b − ⌈k 2⌉, k, i1+mod(k,2)), for 0 ≤k≤min{2(a+ 1) − 1,2b)}. Here, two different cases can arise. If a < b, then the first 2(a+1)−1 steps, instructions i1and i2will alternate one after the other, in order to send to h3(a “garbage” host) one virus each host alternatively. As h1will run out of viruses before h2, in the configuration C2(a+1)−1, since no more viruses are available in host h1, instruction i4is selected as the next instruction, and configuration C2(a+1)+1 is a halting configuration. Otherwise, if a≥b, then the first 2bsteps, instructions i1and i2will alternate one after the other. In this case, h2will run out of viruses before h1, thus in the configuration C2b, instruction i3will be the next instruction. Then, from that point, the following invariant holds: ϕ′(k)≡ C2b+k= (k, a −b−k, 0, k, i3), for 0 ≤k≤a−b After a−bsteps, a−bviruses will be sent to the environment and, since no more viruses are available in host h1, next instruction is i4, that will lead to a halting configuration C2b+a−b+2. 4.2. Basic Arithmetic Operations 105 a h1 b h2 h3 i1i2 i3i4 2 2 2 Figure 4.2: Virus Machine Πsub + (a, b). 4.2.3 Mult module A Virus Machine capable of returning the multiplication of two given numbers is given below. The Virus Machine Πmul = (Γ, H, H2, I, DH, DI, GC,0,0,0,0, i1, hout) of range (4,5,2) where: •Γ = {v},H={h1, h2, h3, h4},H2={h1, h2},I={i1, . . . , i5}; •DH= ({h0} ∪ H, EH, wH), where EH={(h1, h3),(h2, h4),(h3, h1), (h3, h0)}and wH(h1, h3)=2, wH(h2, h4) = wH(h3, h1) = wH(h3, h0) = 1; •DI= (I, EI, wI), where EI={(i1, i2),(i1, i5),(i2, i2),(i2, i3),(i3, i1), (i3, i1),(i4, i3)}and wI(i1, i2) = wI(i2, i2) = wI(i3, i4) = 2, wI(i1, i5) = wI(i2, i3) = wI(i3, i1) = wI(i4, i3) = 1; •GC= (I∪EH, EC), where EC={(i1,(h2, h4)),(i2,(h1, h3)),(i3,(h3, h1)), (i4,(h3, h0))}; •hout =h0. We can see the idea of this Virus Machine in Fig. 4.3. Let (a, b) be the input of Π. The following invariant holds: Chapter 4. Computing Mode 112 4.4.1 Cantor module A Virus Machine with input capable of returning the Cantor pairing function of two given natural numbers is given below. ΠCan = (Γ, H, H2, I, DH, DI, GC,0,0,0,1,0, i1, hout) of range (5,17,2) where: •Γ = {v},H={h1, . . . , h5},H2={h1, h2},I={i1, . . . , i17}; •DH= ({h0} ∪ H, EH, wH), where EH={(h1, h3),(h3, h1),(h3, h2),(h1, h0),(h2, h3),(h3, h4),(h2, h1) (h4, h3),(h1, h2),(h5, h3),(h3, h5)}and wH(h1, h3) = wH(h2, h3) = wH(h4, h3) = 2, wH(hj, hk) = 1 otherwise; •DI= (I, EI, wI), where EI={(i1, i1),(i1, i2),(i2, i3),(i2, i4),(i3, i2),(i4, i4),(i4, i5),(i5, i5),(i5, i6), (i6, i7),(i6, i8),(i7, i6),(i8, i9),(i8, i12),(i9, i9),(i9, i10),(i10, i8),(i10, i11) ,(i11, i10),(i12, i12),(i12, i13),(i13, i13),(i13, i14),(i14, i15),(i14, i16),(i15, i14), (i16, i16),(i16, i17)}and wI(i2, i3) = wI(i6, i7) = wI(i7, i8) = wI(i8, i9) = wI(i10, i11) = wI(i14, i15) = wI(ik, ik) = 2 for each (ik, ik)∈EI, otherwise wI(ij, ip) = 1; •GC= (I∪EH, EC), where EC={(i1,(h1, h3)),(i2,(h3, h1)},(i3,(h3, h2)),(i4,(h1, h0)),(i5,(h2, h3)), (i6,(h3, h2)),(i7,(h3, h4)),(i8,(h2, h1)),(i9,(h4, h3)),(i10,(h3, h4)), (i11,(h3, h5)),(i12,(h1, h2)),(i13,(h5, h3)),(i14,(h3, h1)),(i15,(h3, h5)), (i16,(h1, h0))}; •hout =h0 This Virus Machine is represented visually in Fig. 4.8. To recall the Cantor pairing function from Section 1.1.8, given two natural numbers t1, t2, the Cantor pairing function is defined as C(t1, t2) = (t1+t2)(t1+t2+ 1) 2+t1 . Let (t1, t2) be the input of Π. Moreover, let γk(t1, t2) a polynomial function of (t1, t2) for every natural number k. Then the following invariant holds: ϕ(k)≡ Cγk(t1,t2)= (t1, k, t1+t2−k, 0, t1+t2+ 1, k ·(t1+t2+ 1), i8), for 0≤k≤t1+t2 4.4. Pairing Functions 113 t1 h1 t2 h2 h3 1 h4 h5 22 2 i1i2i3i4i5i6i7i8i9i10 i11 i12 i13 i14 i15 i16 i17 2 2 2 2 2 2 2 2 22 22 i1activates h1→h3 i2activates h3→h1 i3activates h3→h2 i4activates h1→env i5activates h2→h3 i6activates h3→h2 i7activates h3→h4 i8activates h2→h1 i9activates h4→h3 i10 activates h3→h4 i11 activates h3→h5 i12 activates h1→h2 i13 activates h5→h3 i14 activates h3→h1 i15 activates h3→h5 i16 activates h1→env Figure 4.8: Virus Machine ΠCan + (t1, t2). First, the computation starts sending t1viruses replicated by two to h3, then we alternate between i2and i3, in that moment t1viruses are sent to both h1and h2. After that, the t1viruses from h1are sent to the environment. From here, i5, i6, i7makes a copy of the number of viruses contained at h2in h3and that is added to h4. Once we have t1+t2viruses at h2and t1+t2+ 1 at h4, the invariant starts and the product between them is computed, in this invariant h1is used as ”garbage host” so those viruses are sent back to h2at the instruction i12. Next, the quotient between the product already computed and 2 is made by instructions i13, i14 and i15. Finally, that quotient is sent to the environment from h1at instruction i16. This whole process leads to a halting configuration Cγ(t1+t2)(t1,t2)+t1+t2+5 2(t1+t2)(t1+t2+1)+6 = ((t1+t2)(t1+t2+1) 2+ t1,0, t1+t2,0, t1+t2+ 1,(t1+t2)(t1+t2+1) 2,#). That is, the machine HALTS in a polynomial number of steps and return, exactly; the Cantor pairing function of (t1, t2). 4.4.2 G¨odel module In this subsection, the Virus Machine with input presented computes the G¨odel pairing function. The Viurs Machine Chapter 4. Computing Mode 114 ΠGod = (Γ, H, H2, I, DH, DI, GC,0,0,1,1,0,0, i1, hout) of range (6,11,2) where: •Γ = {v},H={h1, . . . , h6},H2={h1, h2},I={i1, . . . , i11}; •DH= ({h0} ∪ H, EH, wH), where EH={(h2, h3),(h1, h2),(h4, h5),(h5, h4),(h5, h6),(h6, h5),(h6, h0)}and wH(h2, h3) = wH(h4, h5) = 2, wH= 1 otherwise; •DI= (I, EI, wI), where EI={(i1, i1),(i1, i2),(i2, i3),(i2, i5),(i3, i4),(i3, i3),(i4, i4),(i4, i2),(i5, i6), (i5, i9),(i6, i6),(i6, i7),(i7, i8),(i7, i5),(i8, i7),(i9, i10),(i10, i10),(i10, i11)} and wI(i1, i1) = wI(i2, i3) = wI(i3, i3) = wI(i4, i4) = wI(i5, i6) = wI(i6, i6) = wI(i7, i8) = wI(i10, i10) = 2, wI(ij, ik) = 1 otherwise; •GC= (I∪EH, EC), where EC={(i1,(h2, h3)),(i2,(h1, h2)),(i3,(h4, h5)),(i4,(h5, h4)),(i5,(h3, h2)), (i6,(h4, h5)),(i7,(h5, h4)),(i8,(h5, h6)),(i9,(h6, h5)),(i10,(h6, h0))}; •hout =h0 This Virus Machine is represented visually in Fig. 4.9. As stated in Section 1.1.8, the G¨odel pairing function is defined as C(t1, t2) = 2t1(2y+1)−1. In addition, let αk(t1, t2) and βk′(t1, t2) two functions with input (t1, t2)∈Nwhich both are exponential functions for every natural numbers k, k′. Let also suppose that (t1, t2) is the input of Π, then the following invariants hold: φ(k)≡ Cαk(t1,t2)= (0, t1−k, k, 2t2+ 1,2k,0,0, i2),for 0 ≤k≤t1 φ′(k′)≡ Cβk(t1,t2)= (0,0, t1+k′,2t2+ 1 −k′,2t1,0, k′·2t1, i5),for 0 ≤k′≤ 2t2+ 1 First, we send the t2viruses to the host h3replicated by two, this with n3= 1 makes that in h3there would be 2t2+ 1 viruses, after that we reach the first invariant from i2to i4that will compute 2keach time until 2t1is reached in host h4. After that, the other invariant starts to compute the product k′·2t1from i5to i8, when this process finishes, we have (2t2+1)·2t1viruses at h6. Finally, we make the difference (2t2+ 1) ·2t1−1 with the instruction i9and at i10 we send all those viruses to the environment. This whole process leads to a halting configuration Cβ2t2+1+3+(2t2+1)2t1= (0, t1+2t2+1,0,2t1,1,0,#,(2t2+1)2t1−1). 4.5. Attacking Cryptosystems 115 t1 h1 t2 h2 1 h3 1 h4h5h6 22 i1i2 i3 i4i5 i6i7i8 i9i10 i11 2 2 22 2 2 2 2 Figure 4.9: Virus Machine ΠGod + (t1, t2). 4.5 Attacking Cryptosystems In this section, virus machines attacking two cryptosystems are considered in order to show the capability of these devises to attack practical problems in computing mode. The first, devoted to attack the RSA cryptosystems, has been published in [81]. The second one, is devoted to the DSA cryptosystems. 4.5.1 RSA Cryptosystem Before presenting the virus machine, let as recall the integer factorization problem and the RSA cryptosystem stated in chapter 1.5.1.1. 4.5.1.1 The integer factorization problem The integer factorization problem is the following: given a natural number greater than 1, find its prime factorization. It is conjectured to be a computationally hard problem. A decision version of this problem is the semiprime factor problem that can be described as follows: given two natural numbers x, y greater than 1, determine whether or not xhas a factor less than y. This Chapter 4. Computing Mode 116 problem belongs to the complexity classes NP,co-NP and BPQ [93]. It is interesting to notice that if that problem is NP-complete or co-NP-complete then NP =co-NP, for further information we refer to [30]. A generalization of the semiprime factorization problem is the least prime divisor (LPD): “Given a natural number n≥2, determine the least natural number m≥2 such that mis a divisor of n”. Obviously, such mmust be a prime number. This problem can be characterized by the partial function FLPD defined as follows: FLPD(n) = mif and only if n≥2 and mis least divisor of n greater than 2. Throughout this section, a deterministic virus machine solving the least prime divisor problem (that is, computing the partial function FLP D), will be designed and the formal verification of it will be considered. 4.5.1.2 Solving the least prime divisor problem by a deterministic virus machine In order to solve the least prime divisor problem by using virus machines, it suffices to design such a machine that computes the partial function FLPD characterizing this problem. Specifically, in this Section a deterministic virus machine that computes FLPD, is presented. Let the virus machine with input ΠLPD = (Γ, H, H1, I, DH, DI, GC,0,2,0,0,1, i1, h0) of degree (5,10,1), where, •Γ = {v}is the singleton alphabet; •H={h1, h2, h3, h4, h5},H1={h1}and I={i1, . . . , i10}are ordered sets such that v /∈H∪I,H∩I=∅and h0/∈H∪I∪ {v}; •DH= (H, EH, wH) is the following weighted directed graph: –EH={(h1, h4),(h2, h3),(h2, h5),(h3, h2),(h3, h0),(h4, h1),(h5, h2)}. –wH(h5, h2) = 2 and the weight of the rest of the arcs is equal to 1. •DI= (I, EI, wI) is the following weighted directed graph: –EI={(i1, i2),(i1, i3),(i2, i1),(i2, i6),(i3, i4),(i3, i5),(i4, i9),(i5, i5), (i5, i10),(i6, i7),(i7, i8),(i8, i8),(i8, i9),(i9, i1),(i9, i9),}. –wI(i1, i2) = wI(i2, i1) = wI(i3, i4) = wI(ik, ik) = 2 for each k= 5,8,9, and the weight of the rest of the arcs is equal to 1. 4.5. Attacking Cryptosystems 117 •GC= (VC, EC) is the undirected bipartite graph, where VC=I∪EH and ECis the following set of edges: –EI={(i1,(h2, h3)),(i2,(h1, h4)),(i3,(h1, h4)),(i4,(h4, h1)), (i5,(h3, h0)),(i6,(h5, h2)),(i7,(h2, h5)),(i8,(h4, h1)), (i9,(h3, h2))} Graphically, the virus machine ΠLPD is shown in Figure 4.10. n h1 2 h2 h3 h4 1 h5 2 i1i2 i3 i4 i5 i6 i7 i8 i9 i10 2 2 2 2 2 2 Figure 4.10: A deterministic virus machine ΠLP D +nsolving the LPD problem. Now we must prove mathematically that the designed virus machine computes the partial function FLPD associated with that problem. Specifically, we will set the result as an interesting input: for any odd number. For a detailed formal verification, we refer to Appendix A. Let us suppose that n=p1·qp1where p1= 2 is the least prime factor and qp1=n p1 . Let us consider the following notation: 1. For every j∈N, such that j≥2, we consider qj, the quotient of the integer division between nand j, and αj= 4qj+ 4n+ 7. 2. Let βk=α2+· · · +αk, for every natural number k≥2. Finally, let us consider the following formula: Chapter 4. Computing Mode 118 ϕ(k)≡Cβk= (n, k + 1,0,0,1, i1,0),for 2 ≤k≤p1−1 This formula is an invariant of the machine, and by induction we get the following Proposition. Proposition 4.1. ∀k( 0 ≤k≤p1−1−→ φ(k)is true ). From Proposition 4.1 we deduce that the formula ϕ(p1−1) is true, thus we have ϕ(p1−1) ≡Cβ(p1−1) = ( n, p1,0,0,1, i1,0 ), from here a halting configuration is reached after qp1·(3p1+ 4) transition steps and returns p1. 4.5.1.3 Attacking an explicit example In this Subsection, an explicit and simple example is presented in order to show how this device can be used. Nevertheless, the lack of efficiency is clear and extensions of these machines will be needed. RSA cryptosystem is based on Fermat-Euler theorem: Theorem 4.1. If nand aare coprime positive integers, and φ(n)is the Euler function, then araised to the power φ(n)is congruent to 1modulo n, that is aφ(n)≡1 mod n At first, a codification of the alphabet is needed. For the following examples the American Standard Code for Information Interchange (ASCII, [1]) codification is used. From here, we will be working with two different public keys in order to understand the efficiency of this Virus Machine with different cases. For all the text encrypted and decrypted before decodification see Appendix B. Let (N1= 8633, e1= 875) the public key of Alice1 (14 bits) and (N2= 524294, e2= 875) the public key of Alice2 (29 bits), we do not know the private keys (φ(N1),d1) and (φ(N2),d2) which satisfies ei·di≡1 mod φ(Ni), that is, there is an integer kisuch that ei·di= 1 + ki·φ(Ni) for each i= 1,2. Alice1 and Alice2 want to send a text message mto Bob1 and Bob2 resp. who also has the private key, so she codifies the message mand then she encrypts: m→meimod Ni In the process, we can get the message encrypted M1(B). In order to decrypt the message, Fermat-Euler’s theorem is applied 4.5. Attacking Cryptosystems 119 Mdi= (mei)di=meidi=m1+kφ(Ni)=m·mkiφ(Ni) m·mkiφ(Ni)mod Ni≡m·1 mod Ni, and we conclude that the private key diis needed. If we can get the Euler function of Ni, then we can attack the cryptosystem. For that, let pi, qiprime numbers such as pi<=qiand Ni=pi·qi, by properties of the Euler function we know that φ(Ni) = (pi−1) ·(qi−1) To summarize, the prime factors of Nare needed, for this instance we compute the virus machine designed in the section before with the input: 1. N1= 8633, the halting configuration of this machine is C3171208 = ( 0,0,0,8633,1,#,89 ), so the least prime divisor pof 8633 is 89 and the greater prime divisor q is 8633/89 = 97. 2. N2= 524294, the halting configuration of this machine is C2621470 = ( 0,0,0,524294,1,#,2 ), so the least prime divisor pof 524294 is 2 and the greater prime divisor qis 524294/2 = 262147. Notice that the number of the steps with the first input is higher that the second one, we can conclude that the least prime factor is even more relevant than the number of digits of the input. Now, we can compute the Euler function: 1. φ(N1) = (89 −1) ·(97 −1) = 88 ·96 = 8448, thus, d1can be computed in a polynomial time thanks to the Extended Euclidean algorithm and the result is d= 1091. 2. φ(N2) = (2 −1) ·(262147 −1) = 1 ·262146 = 262146, thus, d2can be computed in a polynomial time thanks to the Extended Euclidean algorithm and the result is d2= 262146. Chapter 4. Computing Mode 120 Finally, we can decrypt the message M: Mdi imod Ni≡mmod Ni, In the end, if we decode the message m, we get the next text: On the day they were going to k i l l him , Santiago Nasar got up at f i v e t hi rt y in the morning to wait f or the boat the bishop was coming on . He ’ d dreamed he was going through a grove o f timber t r e e s where a g entl e d r i z z l e was f a l l i n g , and f or an i nstan t he was happy in hi s dream , but when he awoke he f e l t completely spatt ere d with bird s h i t . He was always dreaming about trees , Placida Linero , h is mother , told me twenty seven years later , r e c a l l i n g the d e t a i l s of that d i s t r e s s i n g Monday . 4.5.2 DSA Cryptosystem As in the previous subsection, before presenting the virus machine, let as recall the discrete logarithm problem and the DSA cryptosystem stated in chapter 4.5.2. 4.5.2.1 The discrete logarithm problems The discrete logarithm problem (DLP) is the following: given a group G, a generator gof the group and an element xof G, find the discrete logarithm to the base gof xin the group G. It is conjectured to be a computationally hard problem. A decision version of this problem can be described as follows: given a generator gof the group G, an element xof the group G, and an integer k, determine whether or not xhas a discrete logarithm base gless than k. This problem can be characterized by the partial function FDLP defined as follows: FDLP(g, p, x) = kif and only if 0 ≤k≤p−1 is the discrete logarithm of xbase g, where x∈(Zp)∗and gis a generator of (Zp)∗. Throughout this section, a deterministic virus machine solving the discrete logarithm problem, will be designed and the formal verification of it will be considered. 4.5. Attacking Cryptosystems 121 4.5.2.2 Solving the discrete logarithm problem by a deterministic virus machine To solve the discrete logarithm problem using virus machines, it suffices to design a machine that computes the partial function FDLP characterizing the discrete logarithm problem. Specifically, in this Section a deterministic virus machine that computes FDLP, is presented. Let us consider the virus machine Π = (Γ, H, H3, I, DH, DI, GC,0,0,0,1,0,0,1,0,...,0, i1, h0) with input of degree (13,20,3), where: •Γ = {v}is the singleton alphabet; •H={h1, h2, . . . , h13},H1={h1, h2, h3}and I={i1, . . . , i20}are ordered sets such that v /∈H∪I,H∩I=∅and h0/∈H∪I∪ {v}; •DH= (H, EH, wH) is the following weighted directed graph: –EH={(h1, h6),(h2, h11),(h3, h13),(h4, h5),(h5, h0),(h6, h1), (h7, h4),(h7, h8),(h8, h7),(h8, h9),(h9, h10),(h10, h4), (h10, h12),(h11, h2),(h12, h7),(h13, h3)}. –wH(h7, h8) = 2 and the weight of the rest of the arcs is equal to 1. •DI= (I, EI, wI) is the following weighted directed graph: –EI={(i1, i2),(i2, i3),(i2, i6),(i3, i3),(i3, i4),(i4, i2),(i4, i5),(i5, i4), (i6, i7),(i6, i8),(i7, i6),(i7, i10),(i8, i8),(i8, i9),(i9, i6),(i9, i9), (i10, i11),((i10, i12),(i11, i10),(i11, i15),(i12, i13),(i12, i16), (i13, i13),(i13, i14),(i15, i15),(i15, i16),(i16, i16),(i16, i17), (i17, i17),(i17, i18),(i18, i18),(i18, i19),(i19, i19),(i19, i20), (i20, i1),(i20, i20)}. –wI(i2, i3) = wI(i3, i3) = wI(i4, i5) = wI(i6, i7) = wI(i7, i6) = wI(i8, i8) = wI(i9, i9) = wI(i10, i11) = wI(i11, i10) = wI(i12, i16) = wI(i13, i13) = wI(i15, i15) = wI(i16, i16) = wI(i17, i17) = wI(i18, i18) = wI(i19, i19) = wI(i20, i20) = 2 and the weight of the rest of the arcs is equal to 1. •GC= (VC, EC) is the undirected bipartite graph, where VC=I∪EH and ECis the following set of edges: Chapter 5. Generating and Accepting Mode 128 5.1.2 Generating power of two numbers 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}; 4. DH={H∪ {hout},{(h1, h2),(h2, h1),(h1, hout),(h2, hout)}, wH}, where wH((h1, h2)) = wH((h2, h1)) = 2, wH((h1, h2)) = wH((h2, hout)) = 1; 5. DI={I∪ {hout},{(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. 5.2. 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 non-halting computation. Let 2nbe the number generated in the computation C= (C0,C1, . . .) Let αk=Pk i=0 2iThe following invariants hold in this machine: φ≡ Cαk+k= (2k,0, i1,0),for 0 ≤k≤n, k even φ′≡ Cαk+k= (2k,0, i3,0),for 0 ≤k≤n, k odd 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+1 steps, 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), n even 5.1. Generating Virus Machines 129 φ′′′ ≡ C2n+n+1 = (0,2n, i6,0), n odd φ(IV)≡ C2·2n+n+2 = (0,0, i7,2n) φ(V) ≡ C2·2n+n+3 = (0,0,#,2n) 1 h1h2 2 2 i1 i2 i3 i4 i5i6 i7 2 2 2 2 i5i6 Figure 5.2: Virus machine generating the set {2n:n∈N}. From i1(respectively, i3), a non-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: 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) Chapter 5. Generating and Accepting Mode 130 When making the non-deterministic decisions, the instructions i5and i6will never be selected in such a computation, thus making the machine non-halting. 5.1.3 Generating finite number sets In this subsection, two different ways of generating finite sets are studied. Lemma 5.1.1 (Host).Let F={m1, . . . , mk}a finite ordered set of natural numbers greater than zero. Then Fcan be generated by a virus machine of 1 host, mk+ 1 instructions and mkviruses in each host at most. Proof. Let Π = (Γ, H, I, DH, DI, GC, n1, i1, hout), where: 1. Γ = {v}; 2. H={h1}; 3. I={i1, . . . , ik+1}; 4. DH= (H∪ {hout},{(h1, hout)}, wH), where wH((h1, hout)) = 1; 5. DI= (I, EI={(ia, ia+1)|ia∈I\ik+ 1} ∪ {(ib, ik+1)|b∈F}, wI), where wI((id, ie)) = 1 ∀(id, ie)∈EI; 6. GC= (I∪EH,{(if,(h1, hout))})∀if∈I\ {ik+ 1}; 7. n1=mk; and 8. hout =h0 A visual representation of this virus machine can be found in Fig. 5.3. 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 nondeterministic step selects imk+1 as 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) 5.1. Generating Virus Machines 131 . . . . . . mk h1 i1im1im1+1 imk−1imk imk+1 Figure 5.3: Virus machine generating the finite set F. Lemma 5.1.2 (Viruses).Let F={m1, . . . , mk}a finite set of natural numbers greater than zero. Then Fcan be generated by a virus machine of khosts, 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, . . . , 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∈ {0, . . . , 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 Chapter 5. Generating and Accepting Mode 132 . . . . . . . . . 1 h1 1 h2 1 hk−1 1 hk m1m2mk−1 mk i1i2 i3 i4i2k−2 i2k−3 i2k−1i2k Figure 5.4: Virus machine generating the finite set F. A visual representation of this virus machine can be found in Fig. 5.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 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 |{z} host j ,1,...,1,#, mj). Let us suppose now that mkis generated, then the following invariant holds: 5.1. Generating Virus Machines 133 φ(x)≡ Cx= (1,1,...,1, i2x+1,0),for 0 ≤x≤k−2, From this, φ(k−2) is true and from 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). Lemma 5.1.3 (Viruses-host).Let F={m1, . . . , mk}a finite set of natural numbers greater than zero. Then Fcan be generated by a virus machine of 2 hosts, 2k+ 1 instructions and 2virus at each host at most. Proof. Let Π = (Γ, H, I, DH, DI, GC, n1, n2, . . . , nk, i1, hout), where: 1. Γ = {v}; 2. H={h1, h2}; 3. I={i1, . . . , i2mk}; 4. DH= (H∪ {hout},{(h1, h2),(h1, hout),(h2, h1),(h2, hout)}, wH), where wH((h1, h2)) = wH((h2, h1)) = 2 and wH((h1, hout)) = wH((h2, hout)) = 1; 5. DI= (I, EI, wI), where EI={(ia, ia+1)|a∈ {1,...,2mk−1}}∪ {(i2mi−1, i2mk)|mi∈F}, wI((ij, ij′)) = 1 ∀(ij, ij′)∈EI; 6. GC= (I∪EH, EC), where EC={{i2j+1,(h1, hout)},{i2j,(h1, h2)} |j∈ {0, . . . , mk}, j even }∪ {{i2j+1,(h2, hout)},{i2j,(h2, h1)} |j∈ {0, . . . , mk}, j odd }; 7. n1= 2 and n2= 0; 8. hout =h0 Chapter 5. Generating and Accepting Mode 134 . . . . . . 2 h1 0 h2 2 2 i1 i2 i3 i4 i2mi−1 i2mi i2mk−1 i2mk Figure 5.5: Virus machine generating the finite set F. A visual representation of this virus machine can be found in Fig. 5.5. Let us prove that for each mi∈F, there exists a computation of Π such that it produces miviruses in the environment in the halting configuration. Let mi be the generated number; the following invariant holds: φ(x)≡C2x= (2,0, i2x+1, x)xeven, c2x= (0,2, i2x+1, x)xodd, for each 0 ≤x≤mi−1. In particular, φ(mi−1) is true, let us suppose that miis odd, then the following computation is verified: C2(mi−1) = (2,0, i2(mi−1), mi−1), C2mi= (1,0, i2mk, mi), C2mi+1 = (1,0,#, mi), For mieven the computation is analogous, hence the computation halts in 2mi+ 1 steps and the number generated is mi. With the three above lemmas proved, the following Theorem holds: Theorem 5.1.4. NFIN ⊆NV M(1,∗,∗),NFIN ⊆NV M(∗,∗,1), and NFIN ⊆NV M(2,∗,2). 5.2. Recognizing Virus Machines 135 5.2 Recognizing Virus Machines As stated in chapter 3, virus machines are devices capable of solving mathematical problems also in accepting mode. As in the framework of membrane computing, some special devices have been widely studied in the area of computational complexity theory, named recognizer membrane systems [80]. Similarly, we can think of recognizer virus machines capable of solving decision problems as an extension of the accepting mode presented in 3.2.4. Since there only exists a single type of object in the alphabet of a virus machine, there is a change with respect to the yes −no protocol of P systems. We say that a recognizer virus machine with input solves a decision problem X= (IX, θX) if: •All the computations halt. •hout is the environment. •If θX(u) = 1, u ∈IX, then the virus machine Π + usends a single virus to the environment at some point of a computation. •If θX(u) = 0, u ∈IX, then the virus machine Π + uwill not send any virus to the environment at any moment of the computation. •All the computations of Π + u, u ∈IXare confluent; that is, all the computations return the same result. Now we can make a first definition in this approach to a computational complexity theory thourgh these devices: Definition 5.1. Let X= (IX, θX)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)). Chapter 5. Generating and Accepting Mode 136 –The family Πis polynomial bounded respect to (X, cod, s), i.e. ∃p polynomial such that ∀u∈IX,Π(s(u)) + cod(u)halts in p(s(u)) steps. –The family is sound 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 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.2. 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∈PV M), if there exists k∈Nsuch that Xis solvable by the family Πin time bounded by a polynomial, in a deterministic and uniform way. In this section we will see two simple examples of recognizer virus machines, after that universality of virus machines is proved in accepting mode and then a harder problem is presented. 5.2.1 Recognizing Sign and Inverse Sign Function A visual representation of this virus machine can be found in Fig. 5.6. It is easy to see that this machine always halts and will send a virus to the environment if and only if n > 0. From the application of the instruction i1, if there exists a virus in h1, it will be sent to the environment. The following instruction to be applied will be i2, which will lead to a halting configuration. n h1 i1i2 Figure 5.6: Virus machine computing θ(x) = 1 iff x > 0. 5.2. Recognizing Virus Machines 137 A visual representation of this virus machine can be found in Fig. 5.6. It is easy to see that this machine always halts and will send a virus to the environment if and only if n= 0. From the application of the instruction i1, if there exists a virus in h1, it will lead to the instruction i3, making the machine halt without sending viruses to the environment. Otherwise, instruction i2will be selected and it will send the virus located in h2to the environment; then the instruction i3will be selected and the system will halt. n h1 1 h2 i1i2i3 2 Figure 5.7: Virus machine computing θ(x) = 1 iff x= 0. 5.2.2 Universality in Accepting Mode Analogously, we can take a notation of the virus machines in acceptance mode, we say that NaccV M(p, q, n) the collection of all number subsets of Nthat can be accepted by virus machine with in accepting mode at most phosts, q instructions, and nviruses. For unbounded parameters it is written as ∗. Let us also recall the Chapter[REGISTER/Univ] where register machines Mis also used to accept numbers. Denote by Nacc(M) the family of numbers that are accepted by register machine M. In the accepting mode, the register machine is deterministic, replacing l1: (ADD(r), l2, l3) by l1: (ADD(r), l2). It is also presented in that chapter that register machines are also universal in the accepting mode, meaning that register machines can accept the NRE sets. Thus, another method to prove the computational completeness of virus machines is simulating register machines in accepting mode. With the notation fixed, the following Theorem holds. Theorem 5.2.1. NaccV M(∗,∗,∗) = NRE Chapter 6. Uniform Solutions to SAT and Subsetsum 144 computable function. We say that Xis solvable by a family Π = ((Π(n))n∈Nof recognizer virus machines, in time bounded by gin a deterministic and uniform way (denoted by X∈V M(g), if the following holds: •The family Πis polynomially uniform by Turing machines; that is, there exists a deterministic Turing machine working in polynomial time which constructs the virus machine Π(n)form n∈N. •There exist polynomial time computable functions, cod and s, over IX, such that: –For each instance u∈IX,s(u)is a natural number, and cod(u)is a valid input of the virus machine Π(s(u)). –Π(n)is confluent, that is, every computation with the same input must return the same answer. –The family Πis g-bounded with respect (X, cod, s); that is for each instance u∈IX, the minimum length of an accepting computation of Π(s(u)) + cod(u)is bounded by g(|u|). –The family Πis sound with respect to (X, cod, s); that is, for every u∈IX, there exists an accepting computation of Π(s(u)) + cod(u), then ΘX(u) = 1. –The family Πis complete with respect to (X, cod, s); that is, for every u∈IX, if ΘX(u) = 1, then every computation of Π(s(u)) + cod(u)is an accepting one. 6.2 SAT First, let us recall from chapter 1 the definition of the SAT problem. The instances of SAT depend upon two parameters: the number of nvariables, and the number mof clauses. We recall that a clause is a disjunction of literals, occurrences of xior ¬xi, built on a given set X={x1, . . . , xn}of Boolean variables. In what follows we will require that no repetitions of the same literal may occur in any clause; in this way, a clause can be seen as a subset of all possible literals. An assignment of the variables x1, . . . , xnis a mapping a:X→ {0,1}that associates to each variable a truth value. The number of all possible assignments to the variables of Xis 2n. We say that an assignment satisfies the clause Cif, assigned the truth values to all the variables which occur in C, the evaluation of C(considered as a Boolean formula) gives 1 (true) as a result. 6.2. SAT 145 PROBLEM: SAT •INSTANCE: Given C={C1, . . . , Cm}a set of clauses built on a finite set {x1, . . . , xn}of Boolean variables. •QUESTION: Is there an assignment of the variables x1,·, xnthat satisfies all clauses in C? The question that arises is: can SAT be uniformly solved by means of a family Π(⟨n, m⟩)of register virus machines? where Π(⟨n, m⟩) solves all the instances composed by mclauses, built using nvariables. 6.2.1 Codification Let us consider a propositional formula φ=C1∧C2∧ · · · ∧ Cm, with Ci= Yi,1∨ · · · ∨ Yi,pi, for some m≥1, pi≥1, and Yi,j ∈ {xk,¬xk|1≤k≤n}, for each 1 ≤i≤m, 1 ≤j≤pi, where ¬xkrepresents the negation of the Boolean variable xk. We define the cod function as cod(φ) = α1,1, . . . , α1,n, α2,1, . . . , α2,n, . . . , αm,n where for each 1 ≤i≤m, 1≤j≤nwe have: αi,j =   1 if xjappears in Ci 2 if ¬xjappears in Ci 0 otherwise 6.2.2 Uniform Construction The construction will suppose that the number of clauses mis greater or equal than 2, and the number of variables nis greater or equal than 1. For the lower case m=n= 1, it results trivial to solve. With this in mind, let the virus machine Π(⟨n, m⟩) with input of degree (2(n+n·m+m) + 1,5n+ 7n· m+ 2m, m ·n) which solves this problem, working deterministically, can be constructed in an uniform manner, that is, Π(⟨n, m⟩) + cod(φ) solves the SAT problem and the machine Π(⟨n, m⟩) can be built by a deterministic Turing machine in polynomial time (depending on the size s(φ) = n·m). To make it simpler to comprehend the behaviour of the machines, the uniform construction will be divided into seven distinct modules: •Bthat will make the assignment to the variables, •Djwith 1 ≤j≤nwhich decode that assignment for each variable xj, Chapter 6. Uniform Solutions to SAT and Subsetsum 146 •Yij with 1 ≤i≤mand 1 ≤j≤n, which represents the literal xjin the clause Ci, •Eij detect if the assignment of the variable xjverifies the clause Cj, •V ER verifies if all clauses have been verified with the chosen assignment, •RES restore modules Yand Dto start again the loop with next assignment, and •ENDamodules with a∈ {T, F}, both yields to a halting configuration, but if a=Tone virus will be sent to the environment in the previous step. The global idea of these modules can be seen in Figure 6.1 and each module will be explicitly explained afterwards. END B D YY··· Y E D ··· ··· D E Y E Y··· Y E VER END RES F 1,11 2,1 1,1 m,1 m,1 m,n m,n 2 n1,n 1,n 2,n T Figure 6.1: Global idea of the machine. Before explaining each module, we will fix some important notation, for each 1 ≤i≤mand 1 ≤j≤n, let: •bij = 4n+ 4(j−1) ·m+ 4(i−1), •b′ ij = 4n+ 4n·m+ 2(j−1) ·m+ 2(i−1), 6.2. SAT 147 •b′′ ij = 4n+ 6n·m+ 2m+ (j−1) ·m+i, •b′′′ j= 4n+ 7n·m+ 2m+j, these values will be used to enumerate the instructions, on the other hand, to enumerate the auxiliary hosts, for each 1 ≤a≤n+n·m+ 1, let: •auxa=a+n+n·m+m, 6.2.2.1 Bmodule . . . . . . D1 h1h2hn 1 haux1 22 2 i1i2in in+1 i2n+1 in+2 i2n+2 i2n i3n iEND 2 2 2 2 2 ikactivates hk→haux1 in+kactivates haux1→hk(2) i2n+kactivates hk→haux1 for each 1 ≤k≤n Figure 6.2: Bmodule. The Bmodule can be visually described in Figure 6.2, where the true/false assignment is established. If hkis empty, then it is the false assignment for variable xk, if it has one virus then it is the true assignment. The computation Chapter 6. Uniform Solutions to SAT and Subsetsum 148 works as follows. Initially, hosts h1, . . . , hnare empty and haux1contains one virus, but for each loop let us suppose that h1, . . . , hncontain one or zero viruses, if we juxtapose those numbers there will be a binary number that will be increasing by one if we reach again instruction i1. Let us suppose for an instant in the computation, instruction i1will be activated and the number of viruses are 1,...,1,0, xk+1, . . . , xnin hosts h1, . . . , hn, respectively, where xj∈ {0,1}, then one virus is sent from h1to haux1and next instruction is i2, this process is analogously repeated until ikis reached, the channel (hk, haux1) is opened but there is no virus transmission, thus next instruction is in+k, from here, after two steps D1is reached and the number of viruses in hkhas increased by one, leading to the amount of viruses in the hosts has changed to 0,...,0,1, xk+1, . . . , xnin hosts h1, . . . , hn, respectively, that is the next natural number if we look it as its binary encoding representation. If the number of viruses in each host is exactly one, then instruction iEND has been reached, which means that all possible assignments has been tested and none of them verifies all the clauses, thus, the rejecting computation is reached. 6.2.2.2 Djmodule YT 1,j YF 1,j hjhauxj+1 i3n+j 2 Figure 6.3: Djmodule for each 1 ≤j≤n. The Djmodule can be visually described in Figure 6.3, where the true assignment is decoded from the Bmodule, in the sense that if hjhas no viruses, then it is the false assignment and goes to YF 1,j for variable xk, if it has one virus then it is the true assignment and YT 1,j. 6.2.2.3 Yi,j module The Yi,j module can be visually described in Figure 6.4, where it checks if the variable xjat clause Ciis verified with the assignment selected and decoded 6.2. SAT 149 YT i,j YF i,j YT i+1,j YF i+1,j ET i,j EF i,j αi,j hn+[j−1]m+ihauxn+1+[j−1]m+i ibi,j +1 ibi,j +2 ibi,j +3 ibi,j +4 2 2 2 2 Figure 6.4: Yi,j module for each 1 ≤i≤m, 1 ≤j≤n. from modules Band Dj, here the input hosts are presented hn+(j−1)m+iwith the input αi,j for each 1 ≤i≤m, 1 ≤j≤n. Thus, there are three possibilities depending on the input αi,j: •If αi,j = 0, this means that the variable xjdoes not appear in the clause Ci, that is why we go directly from Ya i,j to Ya i+1,j for each a=T, F. •If αi,j = 1, then the literal xjis in the clause Cj, if we go through instruction ibi,j +1, the unique channel in the module is opened, thus one virus is sent and next instruction instruction is ibi,j +3, from here, as host hn+(j−1)m+i, is empty, going trough the least weight path and going to ET i,j, module, where the information that the clause Ciis verified is stored. On the other hand, if we go through ibi,j +2, the procedure is analogous but now the least weight path goes to the next module YF i+1,j, as this clause has not been verified with this variable. •If αi,j = 2, then the literal ¬xjis in the clause Cj, if we go through ibi,j +1, the unique channel in the module is opened, thus one virus is sent and next instruction instruction is ibi,j +3, from here, as host hn+(j−1)m+i, still has other virus, it goes trough the highest weight path to YT i+1,j module, as the clause has not been verified with that variable. On the other hand, if we go through ibi,j +2, the procedure is analogous but now the highest Chapter 6. Uniform Solutions to SAT and Subsetsum 150 weight path goes to the next module EF i,j, where the information that the clause Ciis verified is stored. Here, another clarification is needed for special values of iand j: •If i=m∧j=n: we have to change Ya i+1,j, to V ER for each a=T, F; •if i=m: we have to change Ya i+1,j, to Dj+1 for each a=T, F; 6.2.2.4 Ei,j module ET i,j EF i,j YT i+1,j YF 1+1,j 1 hn+nm+ihauxn+nm+i+1 ib′ ij +1 ib′ ij +2 Figure 6.5: Emodule. The Ei,j module can be visually described in Figure 6.5, where it store if the clause Cjhas been verified with, at least, one of the variables, before reaching the V ER module, as we have defined the modules Yi,j, it can be easily seen that, if the clause Cj, is verified, then the host hauxn+n·m+i+1 will contain one virus, if not, it will be empty. As in the previous modules, another clarification is needed for special values of iand j: •If i=m∧j=n: we have to change Ya i+1,j, to V ER for each a=T, F; •if i=m: we have to change Ya i+1,j, to Dj+1 for each a=T, F; 6.2. SAT 151 . . . . . . . . . . . . V ER RES hn+nm+1 hn+nm+2 hn+nm+m hauxn+nm+2 hauxn+nm+3 hauxn+nm+m+1 1 haux1 i4n+6nm+1 i4n+6nm+2 i4n+6nm+mi4n+6nm+m+1 i4n+6nm+m+2 i4n+6nm+2m iEND 2 22 2 Figure 6.6: V ER module. 6.2.2.5 V ER module The V ER module can be visually described in Figure 6.6, where it checks if all the clauses have been verified, in case this is true, one virus is sent to the environment and a accepting computation is reached, if not, the restart is initialized by returning some hosts to its initial computation (as we will see in the next module). It works as follows: If all the clauses are verified, then all the auxiliary hosts of the previous module has one virus, this means that from instruction i4n+6n·m+1, we are going to the highest weight path with instruction i4n+6n·m+2 and checking if the next clause has been verified until we reach i4n+6n·m+m+1 is reached, which sends one virus to the environment and instruction iEND is activated leading to the halting configuration. Let us now suppose that at least one clause has not been verified, let Ck the first clause that has not been verified, then from instruction i4n+6n·m+1 to i4n+6n·m+k, the computation is the same, but now there is no virus transmission in the channel (hauxn+n·m+k+1 , hn+n·m+k), thus, we go through the least weight path, that is instruction i4n+6n·m+m+k+1, from here, the viruses from the rest of the auxiliary host are sent back to the respective host and module RES is reached. Chapter 6. Uniform Solutions to SAT and Subsetsum 152 6.2.2.6 RET module αi,j hn+[j−1]m+ihauxn+1+[j−1]m+i ib′′ ij ib′′ i−1jib′′ i+1j 2 Figure 6.7: RET −Ymodule. hjhauxj+1 ib′′′ j ib′′′ j−1ib′′′ j+1 Figure 6.8: RET −Dmodule. The RET module is presented in two submodules, the first one is presented in Figure 6.7 and the second in Figure 6.8, the number of viruses are restored for the hosts in the modules Yi,j and Dj, respectively. 6.2.2.7 Result With the assemble of these modules and fixing that the initial instruction is i3n+1 (the first instruction of module D1), we have constructed a recognizer virus machine that solves the SAT problem. Notice that the number of hosts is bounded by the last auxiliary host that is hauxn+n·m+m+1 , that is the host h2(n+n·m)+1. In addition to this, the amount of instructions is bounded by ibn=i5n+7n·m+2m, if we add to this the iEND instruction, we have constructed a virus machine with input of degree (2(n+n·m) + 1,5n+ 7n·m+ 2m+ 1, n ·m), which can be constructed 6.3. Subsetsum 153 (depending on s(φ) = n·m) in polynomial time by a Turing machine, thus, SAT is uniformly solved by means of virus machines. 6.3 Subsetsum First, let us recall from chapter 1 the definition of the Subsetsum problem. PROBLEM: Subsetsum •INSTANCE: Given V={v1, . . . , vn}a set of positive integer numbers, and Sa positive integer number S. •QUESTION: Is there a subset B⊆V, such that X b∈B b=S? The question that arises again is: can the Subsetsum be uniformly solved by means of a family Π(⟨n⟩)of register virus machines? where Π(⟨n⟩) solves all instances composed of sets Vof ndifferent numbers. 6.3.1 Codification Given an instance (V={v1, . . . , vn}, S), we define the codification as cod(V, S)=(v1, . . . , vn, S). Thus, machine Π(⟨n⟩) will have n+ 1 input hosts, and they are Hn+1 ={h1, . . . , hn+1}. 6.3.2 Uniform Construction With the codification fixed, let the virus machine Π(⟨n⟩) with input of degree (2n+ 4,11n+ 3, n + 1) which solves this problem, working deterministically, be constructed in a uniform manner, that is, Π(⟨n⟩) + cod(V, S) solves the Subsetsum problem and the machine Π(⟨n⟩) can be built by a deterministic Turing machine in polynomial time (depending on the size s(V, S) = |V|). As in the previous section, in order to make it simpler to comprehend the behavior of the machines, the uniform construction will be divided into three distinct modules: (i) Bthat will assign the assignment to the possible subsets B, (ii) module Yjwith 1 ≤j≤n, which decode if vjis in the chosen subset, and if vj∈B, then the substraction Sb −vjis made and checks if we have finished or not (iii) ENDamodules with a∈ {T, F}, both yields a halting configuration, but if a=Tone virus will be sent to the environment in the previous step. The global idea of these modules can be seen in Figure 6.9 and each module will be explicitly explained afterward. BIBLIOGRAPHY 256 [11] A. W. Burks. Von neumann’s self-reproducing automata. In A. W. Burks, editor, Essaysoncellularautomata, pages 3–64. University of Illinois Press, 1970. [12] F. G. C. Cabarle and H. N. Adorna. On structures and behaviors of spiking neural p systems and petri nets. In Membrane Computing: 13th International Conference, CMC 2012, Budapest, Hungary, August 28- 31, 2012, Revised Selected Papers 13, pages 145–160. Springer, 2013. [13] F. G. C. Cabarle, K. C. Bu˜no, and H. N. Adorna. Time after time: Notes on delays in spiking neural p systems. In S.-y. Nishizaki, M. Numao, J. Caro, and M. T. Suarez, editors, Theory and Practice of Computation, pages 82–92, Tokyo, 2013. Springer Japan. [14] X. Chen, M. J. P´erez-Jim´enez, L. Valencia-Cabrera, B. Wang, and X. Zeng. Computing with viruses. Theoretical Computer Science, 623:146–159, 2016. [15] A. Cobham. The intrinsic computational difficulty of functions. In Y. Bar-Hillel, editor, Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress (Studies in Logic and the Foundations of Mathematics), pages 24–30, 1965. [16] D. E. Cohen. Computability and Logic. Halsted Press, USA, 1987. [17] S. A. Cook. The complexity of theorem proving procedures. In Proceedings of the Third Annual ACM Symposium, pages 151–158, New York, 1971. ACM. [18] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, Fourth Edition. The MIT Press, 04 2022. [19] W. M. Daley and R. G. Kammer. Digital signature standard (dss). In Federal Information Processing Standards Publication (FIPS), volume 186–2, 2000. [20] R. Davis. The data encryption standard in perspective. IEEE Communications Society Magazine, 16(6):5–9, 1978. [21] L. N. de Castro. Fundamentals of natural computing: an overview. Physics of Life Reviews, 4(1):1–36, 2007. BIBLIOGRAPHY 257 [22] J. F. Dooley. History of cryptography and cryptanalysis: Codes, Ciphers, and their algorithms. Springer, 2018. [23] D. D´ıaz-Pernil, M. A. Guti´errez-Naranjo, M. J. P´erez-Jim´enez, and A. Riscos-N´u˜nez. A uniform family of tissue P systems with cell division solving 3-col in a linear time. Theoretical Computer Science, 404(1):76– 87, 2008. Membrane Computing and Biologically Inspired Process Calculi. [24] J. Edmonds. Minimum partition of a matroid into independent subsets. Journal of Research of the National Bureau of Standards - B. Mathematics and Mathematical Physics, 69(1-2):322–336, 2018. [25] Z. Ezziane. Dna computing: applications and challenges. Nanotechnology, 17(2):R27, 2005. [26] S. Fan, P. Paul, T. Wu, H. Rong, and G. Zhang. On applications of spiking neural P systems. Applied Sciences, 10(20), 2020. [27] L. V. Fausett. Fundamentals of neural networks: architectures, algorithms and applications. Pearson Education India, 1994. [28] D. B. Fogel. What is evolutionary computation? IEEE spectrum, 37(2):26–32, 2000. [29] A. S. Fraser. Simulation of genetic systems by automatic digital computers i. introduction. Australian journal of biological sciences, 10(4):484– 491, 1957. [30] M. R. Garey and D. S. Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979. [31] H. R. Gelderblom. Structure and classification of viruses. In S. Baron, editor, Medical Microbiology, chapter 41. The University of Texas Medical Branch at Galveston, Galveston, 1996. [32] M. R. Geller and Z. Zhou. Factoring 51 and 85 with 8 qubits. Scientific reports, 3(1):3023, 2013. [33] S. Ghosh-Dastidar and H. Adeli. Improved spiking neural networks for eeg classification and epilepsy and seizure detection. Integrated Computer-Aided Engineering, 14(3):187–212, 2007. BIBLIOGRAPHY 258 [34] S. Ghosh-Dastidar and H. Adeli. A new supervised learning algorithm for multiple spiking neural networks with application in epilepsy and seizure detection. Neural networks, 22(10):1419–1431, 2009. [35] S. Ghosh-Dastidar and H. Adeli. Spiking neural networks. International journal of neural systems, 19(04):295–308, 2009. [36] E. Gouzien and N. Sangouard. Factoring 2048-bit rsa integers in 177 days with 13 436 qubits and a multimode memory. Phys. Rev. Lett., 127:140503, Sep 2021. [37] L. Grozinger, M. Amos, T. E. Gorochowski, P. Carbonell, D. A. Oyarz´un, R. Stoof, H. Fellermann, P. Zuliani, H. Tas, and A. Go˜ni-Moreno. Pathways to cellular supremacy in biocomputing. Nature communications, 10(1):5250, 2019. [38] J. Gruska et al. Quantum computing, volume 2005. McGraw-Hill London, 1999. [39] M. A. Guti´errez-Naranjo, M. J. P´erez-Jim´enez, and F. J. Romero- Campero. A linear solution for qsat with membrane creation. In Proceedings of the 6th International Conference on Membrane Computing, WMC’05, page 241–252, Berlin, Heidelberg, 2005. Springer-Verlag. [40] F. Harold. The vital force: a study of bioenergetics. Biochemical Society Transactions, 15, 1987. [41] M. Hellman. New directions in cryptography. IEEE transactions on Information Theory, 22(6):644–654, 1976. [42] M. Ionescu, G. P˘aun, and T. Yokomori. Spiking neural P systems. Fundamenta Informaticae, 71:279–308, 06 2006. [43] M. d. J. P. Jim´enez. M´aquinas en la naturaleza viva. In Ciencia, tecnolog´ıa y humanidades en la era del conocimiento, pages 69–140. Lirandy, 2021. [44] I. Korec. Small universal register machines. Theoretical Computer Science, 168(2):267–301, 1996. [45] T. D. Ladd, F. Jelezko, R. Laflamme, Y. Nakamura, C. Monroe, and J. L. O’Brien. Quantum computers. nature, 464(7285):45–53, 2010. BIBLIOGRAPHY 259 [46] A. Leporati, G. Mauri, C. Zandron, G. P˘aun, and M. J. P´erez-Jim´enez. Uniform solutions to sat and subset sum by spiking neural P systems. Natural Computing, 8:681–702, 2009. [47] P. M. Lewis, R. E. Stearns, and J. Hartmanis. Memory bounds for recognition of context-free and context-sensitive languages. In 6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965), pages 191–202, 1965. [48] Q. Liu, H. Peng, L. Long, J. Wang, Q. Yang, M. J. P´erez-Jim´enez, and D. Orellana-Mart´ın. Nonlinear spiking neural systems with autapses for predicting chaotic time series. IEEE Transactions on Cybernetics, pages 1–13, 2023. [49] L. Long, Q. Liu, H. Peng, J. Wang, and Q. Yang. Multivariate time series forecasting method based on nonlinear spiking neural P systems and non-subsampled shearlet transform. Neural Networks, 15:300–310, 2022. [50] L. Long, Q. Liu, H. Peng, Q. Yang, X. Luo, J. Wang, and X. Song. A time series forecasting approach based on nonlinear spiking neural systems. International Journal of Neural Systems, 32(08):2250020, 2022. [51] L. Long, Q. Liu, H. Peng, Q. Yang, X. Luo, J. Wang, and X. Song. A time series forecasting approach based on nonlinear spiking neural systems. International Journal of Neural Systems, 32(08):2250020, 2022. [52] V. B. Luque, J. C. G. Fern´andez, M. L. Casas, and E. Q. Arroquia. Microbiolog´ıa esencial. Editorial M´edica Panamericana, 2019. [53] S. E. Luria, K. M. Smith, and P. Fredericq. The multiplication of viruses. Springer, 1958. [54] A. Lwoff. The concept of virus. Journal of general microbiology, 17, 1957. [55] A. Macfadyen and H. J. Morowitz. Energy flow in biology: Biological organization as a problem in thermal physics. The Journal of Applied Ecology, 6, 1969. [56] D. Mange and M. Tomassini. Bio-inspired computing machines: Towards novel computational architectures. PPUR presses polytechniques, 1998. BIBLIOGRAPHY 260 [57] C. Mart´ın-Vide, G. P˘aun, J. Pazos, and A. Rodr´ıguez-Pat´on. Tissue P systems. Theoretical Computer Science, 296(2):295–326, 2003. [58] Y. V. Matiyasevich. Hilbert’s tenth problem. American Mathematical Monthly, 102:366, 1993. [59] W. S. McCulloch and W. Pitts. A logical calculus of the ideas immanent in nervous activity. The bulletin of mathematical biophysics, 5:115–133, 1943. [60] A. J. Menezes, P. C. Van Oorschot, and S. A. Vanstone. Handbook of applied cryptography. CRC press, 2018. [61] N. Metropolis. History of computing in the twentieth century. Elsevier, 2014. [62] M. Mitchell. An introduction to genetic algorithms. MIT press, 1998. [63] D. Moody, R. Peralta, R. Perlner, A. Regenscheid, A. Roginsky, and L. Chen. Report on pairing-based cryptography. Journal of Research of the National Institute of Standards and Technology, 120:11, 02 2015. [64] M. Negroni and M. I. Gonz´alez. Virus: Generalidades. Microbiolog´ıa Estomatol´ogica Parte I, 2018. [65] J. V. Neumann and A. W. Burks. Theory of self-reproducing automata. University of Illinois Press, 1966. [66] D. Orellana-Mar´ın. El problema P versus NP. Desarrollo de nuevas t´ecnicas a trav´es de modelos de computaci´on bio-inspirados. PhD thesis, University of Seville, 2019. [67] D. Orellana-Mart´ın, A. Ram´ırez-de Arellano, J. A. Andreu-Guzm´an, ´ A. Romero-Jim´enez, and M. J. P´erez-Jim´enez. A protocol for solutions to dp-complete problems through tissue membrane systems. Mathematics, 11(13):2797, 2023. [68] D. Orellana-Mart´ın, A. Ram´ırez-de Arellano, and M. J. P´erez-Jim´enez. Simulating and validating virus machines. PREPRINT (Version 1) available at Research Square. [69] A. P˘aun and G. P˘aun. Small universal spiking neural P systems. BioSystems, 90(1):48–60, 2007. BIBLIOGRAPHY 261 [70] G. P˘aun. Computing with membranes. Journal of Computer and System Sciences, 61(1):108–143, 2000. [71] G. P˘aun. Membrane computing: an introduction. Springer Science & Business Media, 2002. [72] G. P˘aun and M. J. P´erez-Jim´enez. Membrane computing: Brief introduction, recent results and applications. Biosystems, 85(1):11–22, 2006. Dedicated to the Memory of Ray Paton. [73] G. P˘aun, M. J. P´erez-Jim´enez, and A. Riscos-N´unez. Tissue P systems with cell division. International Journal of Computers Communications & Control, 3(3):295–303, 2008. [74] G. P˘aun, M. J. P´erez-Jim´enez, and A. Riscos-N´u˜nez. Tissue P systems with cell division. International Journal of Computers, Communications & Control, 3:295–303, 09 2008. [75] G. P˘aun, G. Rozenberg, and A. Salomaa. DNA computing: new computing paradigms. Springer, 1998. [76] H. Peng, T. Bao, X. Luo, J. Wang, X. Song, A. Riscos-N´unez, and M. J. P´erez-Jim´enez. Dendrite P systems. Neural Networks, 127:110– 120, 2020. [77] H. Peng, Z. LV, B. Li, X. Luo, J. Wang, X. Song, T. Wang, M. P´erez- Jim´enez, and A. Riscos-Nu˜nez. Nonlinear spiking neural P systems. International Journal of Neural Systems, 30(10):2050008, 2020. [78] H. Peng, J. Wang, M. J. P´erez-Jim´enez, and A. Riscos-N´u˜nez. Dynamic threshold neural P systems. Knowledge-Based Systems, 163:875–884, 2019. [79] H. Peng, J. Wang, M. J. P´erez-Jim´enez, H. Wang, J. Shao, and T. Wang. Fuzzy reasoning spiking neural P system for fault diagnosis. Information Sciences, 235:106–116, 2013. Data-based Control, Decision, Scheduling and Fault Diagnostics. [80] M. J. P´erez-Jim´enez. An approach to computational complexity in membrane computing. In G. Mauri, Gh. P˘aun, M. J. P´erez-Jim´enez, G. Rozenberg, and A. Salomaa, editors, Membrane Computing, pages 85–109, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. BIBLIOGRAPHY 262 [81] M. J. P´erez-Jim´enez, A. Ram´ırez-de Arellano, and D. Orellana-Mart´ın. Attacking cryptosystems by means of virus machines. Scientific Reports, 13(1):21831, 2023. [82] G. P˘aun and M. J. P´erez-Jim´enez. Spiking neural P systems: An overview. In A. Porto Pazos, A. Pazos Sierra, and W. Bu˜no Buceta, editors, Advancing Artificial Intelligence through Biological Process Applications, pages 60–73. IGI Global, 2009. [83] G. P˘aun, G. Rozenberg, and A. Salomaa. The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford, 2010. [84] A. Ram´ırez-de Arellano, D. Orellana-Mart´ın, and M. J. P´erez-Jim´enez. Basic arithmetic calculations through virus-based machines. In J. M. Ferr´andez Vicente, J. R. ´ Alvarez-S´anchez, F. de la Paz L´opez, and H. Adeli, editors, Bio-inspired Systems and Applications: from Robotics to Ambient Intelligence, pages 403–412, Cham, 2022. Springer International Publishing. [85] A. Ram´ırez-de-Arellano, D. Orellana-Mart´ın, and M. J. P´erez-Jim´enez. Generating, computing and recognizing with virus machines. Theoretical Computer Science, 972:114077, 07 2023. [86] A. Ram´ırez-de Arellano, D. Orellana-Mart´ın, and M. J. P´erez-Jim´enez. Using virus machines to compute pairing functions. International Journal of Neural Systems, 33(05):2350023, 2023. [87] A. Ram´ırez-de Arellano, J. A. Rodr´ıguez-Gallego, D. Orellana-Mart´ın, and S. Ivanov. Stochastic virus machines. In Proceedings of the Nineteenth Brainstorming Week on Membrane Computing, 2023. [88] R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978. [89] ´ A. Romero-Jim´enez, L. Valencia-Cabrera, and M. J. P´erez-Jim´enez. Generating diophantine sets by virus machines. In M. Gong, P. Linqiang, S. Tao, K. Tang, and X. Zhang, editors, Bio-Inspired Computing – Theories and Applications, pages 331–341, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. BIBLIOGRAPHY 263 [90] ´ A. Romero-Jim´enez, L. Valencia-Cabrera, A. Riscos-N´u˜nez, and M. J. P´erez-Jim´enez. Computing partial recursive functions by virus machines. In G. Rozenberg, A. Salomaa, J. M. Sempere, and C. Zandron, editors, Membrane Computing, pages 353–368, Cham, 2015. Springer International Publishing. [91] G. Rozenberg, T. B¨ack, and J. N. Kok. Handbook of Natural Computing. Springer Berlin, Heidelberg, Heidelberg, 2012. [92] G. Rozenberg, A. Salomaa, J. M. Sempere, and C. Zandron, editors. Proc. 16th CMC 2015 International Conference on Membrane Computing Valencia, Spain, August 17-21, 2015, Revised Selected Papers, volume 1 of Lecture Notes in Computer Science, Valencia, Spain, 2015. Springer Cham. [93] P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994. [94] T. Song, X. Zeng, P. Zheng, M. Jiang, and A. Rodriguez-Paton. A parallel workflow pattern modeling using spiking neural p systems with colored spikes. IEEE transactions on nanobioscience, 17(4):474–484, 2018. [95] E. D. Sontag and H. Siegelmann. On the computational power of neural nets. J. Comp. Syst. Sci, 50:132–150, 1995. [96] A. Steane. Quantum computing. Reports on Progress in Physics, 61(2):117, 1998. [97] R. E. Stearns, J. Hartmanis, and P. M. Lewis. Hierarchies of memory limited computations. In Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965), pages 179– 190, 1965. [98] C. A. Suttle. Viruses in the sea. Nature, 437, 2005. [99] A. Tavanaei, M. Ghodrati, S. R. Kheradpisheh, T. Masquelier, and A. Maida. Deep learning in spiking neural networks. Neural networks, 111:47–63, 2019. [100] A. M. Turing. Computability and λ-definability. The Journal of Symbolic Logic, 2(4):153–163, 1937. BIBLIOGRAPHY 264 [101] L. Valencia-Cabrera, M. J. P´erez-Jim´enez, X. Chen, B. Wang, and X. Zeng. Basic virus machines. In J. M. Sampere and C. Zandron, editors, 16th International Conference on Membrane Computing (CMC16), pages 323–342, 2015. [102] W. M. van Der Aalst, A. H. Ter Hofstede, B. Kiepuszewski, and A. P. Barros. Workflow patterns. Distributed and parallel databases, 14:5–51, 2003. [103] L. M. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang. Experimental realization of shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature, 414(6866):883–887, 2001. [104] L. P. Villarreal. Are viruses alive? Scientific American, 291, 2004. [105] J. von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the Theory of Games, 2(0):5–12, 1953. [106] E. W. Weisstein. Fermat’s little theorem. https://mathworld. wolfram. com/, 2004. [107] J. Willey, L. Sherwood, C. Woolverton, and L. M. Prescott. Prescott’s Principles of Microbiology. Boston : McGraw-Hill, 2011. [108] S. Wolfram. Cellular automata and complexitiy. Perseus Books, 1994. [109] T. Wu, A. P˘aun, Z. Zhang, and L. Pan. Spiking neural P systems with polarizations. IEEE transactions on neural networks and learning systems, 29(8):3349–3360, 2017. [110] R. Xian, R. Lugu, H. Peng, Q. Yang, X. Luo, and J. Wang. Edge detection method based on nonlinear spiking neural systems. International Journal of Neural Systems, 33(01):2250060, 2023. [111] R. Xian, X. Xiong, H. Peng, J. Wang, A. R. de Arellano Marrero, and Q. Yang. Feature fusion method based on spiking neural convolutional network for edge detection. Pattern Recognition, 147:110112, 2024. [112] G. Zhang, X. Zhang, H. Rong, P. Paul, M. Zhu, F. Neri, and Y.-S. Ong. A layered spiking neural system for classification problems. International journal of neural systems, 32(08):2250023, 2022. BIBLIOGRAPHY 265 [113] Y. Zhang, Q. Yang, Z. Liu, H. Peng, and J. Wang. A prediction model based on gated nonlinear spiking neural systems. International Journal of Neural Systems, 33(06):2350029, 2023.