Normal forms in Virus Machines
A. Ramírez-de-Arellano F. G. C. Cabarle D. Orellana-Martín M. J. Pérez-Jiménez







Normal forms in Virus MachinesSupported by the Zhejiang Lab BioBit Program (Grant No. 2022BCF05).
    Antonio Ramírez-de-ArellanoCorresponding author: Universidad de Sevilla,  Avda. Reina Mercedes s/n, Seville, 41012, Spain

    Dept. of Computer Science and Artificial Intelligence

    University of Seville

    SCORE Laboratory, I3US, University of Seville

    aramirezdearellano@us.es
    Francis George C. CabarleQUAL21 008 USE
    project, “Plan Andaluz de Investigación,
    Desarrollo e Innova­ción” (PAIDI) 2020 and “Fondo Europeo de Desarrollo Regional” (FEDER) of the European Union, 2014-2020 funds.

    SCORE Laboratory, I3US, University of Seville

    Dept. of Computer Science

    University of the Philippines Diliman

    fcabarle@us.es fccabarle@up.edu.ph
    David Orellana-Martín

    Dept. of Computer Science and Artificial Intelligence

    University of Seville

    SCORE Laboratory, I3US, University of Seville

    dorellana@us.es
    Mario J. Pérez-Jiménez

    Dept. of Computer Science and Artificial Intelligence

    University of Seville

    SCORE Laboratory, I3US, University of Seville

    marper@us.es

    
=======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================



A. Ramírez-de-Arellano, F. G. C. Cabarle, D. Orellana-Martín, M. J. Pérez-JiménezNormal Forms in VM




In the present work, we further study the computational power of virus machines (VMs in short).
VMs provide a computing paradigm inspired by the transmission and replication networks of viruses.
VMs consist of process units (called hosts) structured by a directed graph whose arcs are called channels and an instruction graph that controls the transmissions of virus objects among hosts.
The present work complements our understanding of the computing power of VMs by introducing normal forms; these expressions restrict the features in a given computing model.
Some of the features that we restrict in our normal forms include (a) the number of hosts, (b) the number of instructions, and (c) the number of virus objects in each host.
After we recall some known results on the computing power of VMs we give our normal forms, such as the size of the loops in the network, proving new characterisations of family of sets, such as the finite sets, semilinear sets, or NRE. 








Normal forms in Virus MachinesSupported by the Zhejiang Lab BioBit Program (Grant No. 2022BCF05).
    Antonio Ramírez-de-ArellanoCorresponding author: Universidad de Sevilla,  Avda. Reina Mercedes s/n, Seville, 41012, Spain

    Dept. of Computer Science and Artificial Intelligence

    University of Seville

    SCORE Laboratory, I3US, University of Seville

    aramirezdearellano@us.es
    Francis George C. CabarleQUAL21 008 USE
    project, “Plan Andaluz de Investigación,
    Desarrollo e Innova­ción” (PAIDI) 2020 and “Fondo Europeo de Desarrollo Regional” (FEDER) of the European Union, 2014-2020 funds.

    SCORE Laboratory, I3US, University of Seville

    Dept. of Computer Science

    University of the Philippines Diliman

    fcabarle@us.es fccabarle@up.edu.ph
    David Orellana-Martín

    Dept. of Computer Science and Artificial Intelligence

    University of Seville

    SCORE Laboratory, I3US, University of Seville

    dorellana@us.es
    Mario J. Pérez-Jiménez

    Dept. of Computer Science and Artificial Intelligence

    University of Seville

    SCORE Laboratory, I3US, University of Seville

    marper@us.es

    
=======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================





§ INTRODUCTION


In the present work, we consider some normal forms for virus machines, this computing paradigm was introduced in <cit.> are unconventional and natural computing models inspired by networks of virus replications and transmissions.
More information on unconventional and natural computing is found in <cit.> and <cit.>, respectively.
From <cit.> it is shown that VMs are Turing complete, that is, they are algorithms capable of general-purpose computations.
From such works some VMs for computing classes of (in)finite sets of numbers are also shown.
Providing normal forms for VMs allows a more refined or deeper view of their computations: What features and their values for VMs can be increased or decreased to increase or decrease computing power?

Virus machines consists of three graphs: a directed and weighted host graph with nodes and edges referred to as hosts and channels, respectively;
a directed and weighted instruction graph where nodes are instructions and edge weights determine which instruction to prioritise and next activate;
an instruction-channel graph which connects an edge between instructions and channels in the previous graphs.
Hosts contain zero or more virus objects, and activating an instruction means opening a channel since the channels are closed by default.
Opening a channel means that virus objects from one host are replicated and transferred to another host.
Even from this high-level view of VMs and their features, it can be evident that the source of their computing power can be further restricted or refined.
Thus, a deeper understanding of VMs as algorithms is gained in order to aid in developing applications.

Briefly, the idea of a normal form for some computing mo­del is to consider restrictions in the model while maintaining its computer power.
That is, considering lower bounds for ingredients in a computing model is a natural direction for investigation.
For instance, a well-known normal form in language theory is the Chomsky normal form, CNF in short, from <cit.>.
Instead of having an infinite number of forms to write rules in a grammar for context-free sets, CNF shows that two forms are enough.
Normal forms in unconventional or bio-inspired models include spiking neural P systems <cit.> and cellular automata <cit.>, with recent and optimal results in <cit.>, and a recent survey in <cit.>.
In addition to restriction while maintaining the same power, normal forms can provide frontiers.
For instance, by giving some lower bound for some value, further decreasing the value can mean that we only compute a proper subset of problems as before.

This paper contributes the following to the study of virus machines and their computing power.
Normal forms, some of which are optimal bounds, for VMs are provided in the following sense: (a) providing characterisations (previously were inclusions) for generating families of finite sets;
(b) showing new characterisations for finite sets of numbers using restric­tions on the number of required hosts, instructions, or viruses; and (c)
new characterisations are also given for singleton sets of numbers and some linear progressions or combinations.
We also consider new restrictions: limiting or not the host or ins­truction graphs to be a tree graph, that is, an acylcic directed graph. Moreover, the instruction-channel graph can also be li­mited in the sense that one channel can be attached to at most one instruction.
We show, for instance, that some VMs with a tree instruction or host graph and with some lower bounds on the number of hosts, instructions, and viruses can only compute finite sets. Lastly, we highlight a new (and better) characteri­sation of semilinear sets of numbers, in short SLIN, with virus machines.
Our results on normal forms are then used to ask new questions regarding other normal forms and restrictions on VMs.

The present work is a much extended and revised version of the preliminary report in <cit.>.
For instance, results on the family SLIN is especially interesting from the point of view of theory and applications: 
SLIN is a  class enjoying the fact that it is above the family of finite sets NFIN and below the family of Turing computable sets NRE, with SLIN known to be decidable <cit.>; 
the decidability of SLIN helps toward the computational complexity of machines for it;
applications can benefit from the decidability of SLIN, including formal verification, proof assistant <cit.>.

The organisation of the present work is as follows. First, some brief definitions and the state of the art are presented in Section <ref>. After that, novel results are presented with the old ingredients in Section <ref>. We continue with novel results with the new ingredients proposed in Section <ref>. Lastly, some conclusions with open remarks are shown in Section <ref>.




§ DEFINITIONS
 



 §.§ Virus Machines


    Let a virus machine Π of degree (p,q) with p,q ≥ 0 defined as:

    
    Π = (Γ, H, I, D_H, D_H, G_C, n_1,…,n_p,i_1,h_out)


    where:

    
        
  * Γ={v} is the singleton alphabet.
        
  * H={h_1,…,h_p} is the ordered set of hosts, h_out can be either in H or not (for this work, we will suppose always h_out∉ H, I={i_1,…, i_q} the ordered set of instructions.
        
  * D_H = (H∪{h_out}, E_H, w_H) is the weighted and directed (WD) host graph, where the edges are called channels and w_H : H× H∪{h_out}→.
        
  * D_I = (I, E_I, w_I) is the WD instruction graph and w_I : I× I→{1,2}.
        
  * G_C = (E_H ∪ I, E_I) is a unweighted bipartite graph ca­lled channel-instruction graph, where the partition associated is {E_H∪ I}.
        
  * n_1,…,n_p∈ are the initial number of viruses in each host h_1,…, h_p, respectively.
    


Regarding the semantics, a configuration at an instant t≥0 is the tuple _t = (a_1,t,a_2,t,…,a_p,t,u_t,a_0,t)
where for each j∈{1,…, p}, a_j,t∈ represents the number of viruses in the host h_j at instant t, and u_t∈ I∪{#} is the following activated instruction, unless u_t= # that is a halting configuration. Lastly, _0=(n_1,…,n_p,i_1,0) is the initial configuration. 

From a configuration _t, _t+1 is obtained as follows. The instruction that will be activated is u_t if u_t∈ I, otherwise _t is a halting configuration. Let us suppose that u_t∈ I and that it is attached to the channel (h_j,h_j')∈ E_H with weight w∈, then the channel is opened and  two possibilities holds:

    
  * If a_j,t>0, then there is virus transmission, that is, one virus is consumed from h_j and is sent to the host h_j' replicated by w. The next activated instruction will follow the highest weight path in the instruction graph. In case the highest path is not unique, it is chosen nondeterministically. In case there is no possible path, then u_t+1 = #
    
  * If a_j,t=0, then there is no virus transmission and the next instruction follows the least weight path. For the other cases, it is analogous to the previous assumption.


This paper is focused on the computational power of VMs in the generating mode, and for that we fix the same notation as in the foundational paper <cit.>. Let 

NVM(p,q,n) be the family of sets of natural numbers generated by virus machines with at most p hosts, q instructions, and n viruses in each host at any instant of the computation. For unbounded restrictions, they are replaced by *.



  §.§.§ Formal Verification


One technique to mathematically formal verify the integrity of these devices is by designing invariant formulas which highlight interesting properties of the most relevant loops. For the seek of simplicity, some formal verifications will show the invariant formula and how it works; the mathematical proof of these formulas can be easily obtained with the induction technique. Lastly, we propose a novel technique for formal verification, that is, by fixing the sizes of the loops in the instruction graph. 



 §.§ Topology

For this study, several notation and clarifications related to discrete topology must first be presented.


    A path in a directed graph G = (V,E) is an ordered tuple

    (v_1,…,v_n) of vertices such that (v_i,v+1) ∈ E for i=1,…, n-1 and v_i≠ v_j, for i,j= 1,…,n, and i≠ j. Under the same conditions, if (v_n,v_1)∈ E, then the path is called a cycle. A graph without cycles is called a tree. The depth of a tree is the longest path of the tree.

    We say that v_1 is connected to v_n if there is a path w= (e_1,…,e_n-1), whose sequence of vertices is (v_1,…,v_n). We denote by V(v_i)⊆ V the subset of vertices that are connected by a path from v_i.

    A graph G= (V,E) is connected if there are paths that contain each pair of vertices v_i,v_j with i≠ j. A rooted tree is a graph with a distinguished 
    node v_i, called the root, such that for each v_j∈ V, with i≠ j, v_i is connected to v_j. We will note as I(v_i)⊆ V the subset of vertices that forms the rooted tree G_v_i = (I(v_i),E(v_i)) which is a subgraph of G.



    If the instruction graph D_I of a virus machine Π of degree (p,q), with p,q≥ 1,
    
    Π = (H,I,D_H,D_I,G_C,n_1,…,n_p,i_1,h_out),

    is not a rooted tree with root i_1, then there exists another virus machine Π' of degree (p,q'), with q'≤ q, which has the same computation.


    Let Π be the virus machine fixed in the statement, setting the instruction graph to D_I=(I,E_I,w_I), as it is not a rooted tree with root i_1; then I(i_1)≠ I. Let Π' be the virus machine of degree (p,q')=|I(i_1)|), defined as Π but with a new instruction graph D_I(i_1)= (I(i_1),E_I(i_1),w_I(i_1)).

    Due to the semantics associated with virus machines, any instruction that can be activated must be connected by a path from the initial instruction; thus, the set of instructions of Π that can be activated at some instant of the computation is contained in I(i_1), therefore Π' has the same computation.


Using this result, from now on, all defined virus machines are supposed to be rooted trees with root i_1, which is i_1 the initial instruction. In addition, the same notation of the components of a virus machine Π is used for the following results. 



 §.§ State-of-the-art

This subsection is devoted to reviewing results prior to this work on the computing power of VMs with respect to certain classes or families of computable numbers.





The state-of-the-art is presented in Table <ref>. The virus machines in the generating mode are Turing Universal; that is, they can generate recursively enumerable sets of numbers (NRE) <cit.> for unbounded restrictions. This power is severely reduced when the last ingredient is reduced; more precisely, a semilinear set characterisation (SLIN) is proved for NVM(*,*,2) <cit.>. From now on, not characterisations but inclusions have been proven, for finite sets (NFIN) they are contained in NVM(1,*,*) and NVM(*,*,1) <cit.>. Finally, the set of power of two numbers is contained in NVM(2,7,*) <cit.>.



An interesting and natural question is can we further restrict or provide better lower bounds, for known results about VMs?
That is, provide “better” characterisations of finite sets or even other families of sets such as the singleton sets, see, for instance, Table <ref>.
As we focus on finite sets later, let us see the VMs used in <cit.> to generate finite sets. For NVM(1,*,*) the VM presented in Figure <ref>, and for NVM(*,*,1) the Figure <ref>. The corresponding lemmas were called (viruses) and (hosts), respectively, and we follow the same notation in this work.



§ NOVEL RESULTS WITH OLD INGREDIENTS




 §.§ Finite sets


        Let F = {m_1,…,m_k} a nonempty finite set of natural numbers that m_i>0. Then F can be generated by a virus machine of 2 hosts, 2k+1 instructions, and the 2 virus in each host at most.




Let Π be the virus machine of degree (2,2m_k) defined as

Π = (Γ, H, I, D_H, D_I, G_C, n_1, n_2, i_1,h_out), where:



  * Γ = {v};

  * H = {h_1,h_2};

  * I = {i_1, … , i_2m_k};

  * D_H = (H ∪{h_out}, E_H={(h_1, h_2),(h_1, h_out),(h_2, h_1),(h_2, h_out)}, w_H), where
  w_H((h_1, h_2)) = w_H((h_2, h_1)) =2 and

  w_H((h_1, h_out)) = w_H((h_2, h_out)) = 1;

  * D_I = (I , E_I , w_I ), where E_I={(i_a, i_a+1)  |  a∈{1,…, 2m_k-1}}∪
{(i_2m_i-1,i_2m_k) | m_i∈ F},
  w_I((i_j, i_j')) = 1, for each (i_j,i_j')∈ E_I;

  * G_C = (I ∪ E_H,E_C), where 

[                                                             E_C = ⋃_j ∈{0,…, m_k}, j  even ({i_2j+1,(h_1,h_out)},{i_2j,(h_1,h_2)})∪;                                                                    ⋃_j ∈{0,…, m_k}, j  odd ({i_2j+1,(h_2,h_out)},{i_2j,(h_2,h_1)}); ]

  * n_1 =2 and n_2= 0;


A visual representation of this virus machine can be found in Figure <ref>. Let us prove that for each m_i∈ F,
there exists a computation of Π such that it produces m_i viruses
in the environment in the halting configuration. Let m_i be the generated number; the following invariant holds:


    φ(x) ≡{[ _2x = (2,0,i_2x+1,x)             x  even,; _2x = (0,2,i_2x+1,x)              x  odd, ].


for each 0≤ x≤ m_i-1. In particular, φ(m_i-1) is true, let us suppose that m_i is odd, then the following computation is verified:

    _2(m_i-1)   = (2,0,i_2m_i-1, m_i-1), 
    _2m_i   = (1,0,i_2m_k, m_i), 
    _2m_i+1   = (1,0,#, m_i),


For m_i even the computation is analogous, hence the computation halts in 2m_i+1 steps and the number generated is m_i.


Another interesting result is that this inclusion is strict.



    NFIN⊊ NVM(2,*,2).


    Inclusion is direct by the Lemma <ref>. Let us now focus on inequality; for that, we construct a virus machine from <cit.>, extending the work from <cit.>, which generates the set of all natural numbers except the zero, which verifies the restrictions of the proposition. 

     Let Π_Nat = (Γ, H, I, D_H, D_I, G_C, 1,0, i_1, h_out), where:



  * Γ = {v};

  * H = {h_1,h_2};

  * I = {i_1, … , i_4};

  * D_H = (H ∪{h_out}, {(h_1, h_2),(h_2, h_out),(h_2, h_1)}, w_H), where

  w_H((h_1, h_2)) = 2 and
  w_H((h_2, h_out)) = w_H((h_2, h_1)) = 1;

  * D_I = (I , E_I , w_I ), where E_I={(i_1,i_2),(i_2,_3),(i_3,i_1),(i_3,i_4)}, and

  w_I((i_j, i_j')) = 1  ∀ (i_j,i_j')∈ E_I;

  * G_C = (I ∪ E_H,E_C), where E_C ={{i_1,(h_1,h_2)},{i_2,(h_2,h_1)},
{i_3,(h_2,h_out)}};

  * h_out = h_0;




A visual representation of this virus machine can be found in
Fig. <ref>. Now, let us prove that for each n∈, there exists a halting computation generating the number n. For generating this number, the following invariant holds:


    φ(k) ≡_3k =(1,0,i_1,k),  for each  0≤ k≤ n-1


In particular, φ(n-1) is true, then the following configuration is verified _3(n-1) = (1,0,i_1,n-1), from here, after the 4 transition steps the halting configuration is reached _3n+1 =(1,0,#,n), whose output is the natural number n.




 §.§ Singleton Sets


Now let us move to the second family of sets, the Singleton sets, these are sets of natural numbers with only one element, in this work we include the empty set in this family.


The following sets of numbers are equivalent to singleton sets:
   
       
  * NVM(1,*,1);
       
  * NVM(*,1,*); 
       
  * NVM(1,1,1)
   



    The proof of equivalence is done by the double inclusion technique.
    
        
  * Let us start with the inclusion of the left side, let Γ = {v} be a singleton set of natural number v∈, then it can be generated by the VM Π_sing_1 of degree (1,1) depicted in Figure <ref>, the initial configuration is _0 = (1,i_1,0) and in the following configuration, a virus is consumed and replicated by the weight of the arc, that is, v, and sent to the environment, leading to the halting configuration _1 =(0,#, v). Thus, after one transition step, the set generated is {v}.

    

    For reverse inclusion, suppose any VM with only one host and one virus: the host can only be attached to the environment, and let us fix that the weight of that channel is w∈.
    Thus, the only number generated is w or none, depending on the instruction graph (if the computation halts or not). Thus, we generate a singleton set.
    
    
  * For the inclusion on the left side we can use the VM Π_sing_1 depicted in Figure <ref> as it only has one instruction and the inclusion has already been proven.
    
    Let us focus on the inclusion of the right side. With only one instruction, there are two possibilities in the instruction graph: 
        
  * The node with a self-arc, which creates an infinite loop, thus a non-halting computation and generating the empty set.
        
  * The node with no arcs, thus the machine, halts after only one transition step as there is no other possible path. In this sense, two options can be separated:
        
            
  * The instruction is attached to a channel which is attached to the environment, generating a singleton set.
            
  * The instruction is not attached to a channel which is attached to the environment, thus the set generated is {0}.
        
    

    
  * Lastly, the left side inclusion is again using Π_sing_1, and the right side is direct as the restrictions are stronger than the previous statements.
    





 §.§ Finite linear progressions


The computing power of virus machines highly depends on the instruction graph, to show this, let us see the following result when we bound by 2 the amount of instructions. For this, we will fix the following notation: 

Let NLinFIN = ⋃_x∈⋃_n∈⋃_N∈({x + n· i: 0≤ i≤ N}) ∪{ ∅}, the family of finite linear progressions. The following result holds.


    NVM(p,2,*) = NLinFIN, for each p≥ 2.



    For the right-side inclusion, for any x,n,N∈, let us see that there exists a VM Π_Lin of degree (2,2) that generates the set {x + n· i: 0≤ i≤ N}. The virus machine can be depicted in Figure <ref>.

    

    Suppose that the number generated is x + n· k with 0≤ k ≤ N, then the following computation holds.
    
    
    _0   = (N,1,i_1,0), 
    _1   = (N-1,1,i_1,n), 
       ⋮
    _k-1   = (N-(k-1),1,i_1,n·(k-1)), 
    _k   = (N-k,1,i_2,n· k), 
    _k+1   = (N-k,1-1,#,x + n· k),


    Therefore, the number is generated, the other inclusion is straightforward.

    For the inclusion on the left side, some previous considerations should be taken into account. First, let us fix that I={i_1,i_2} is the set of instructions and i_1 is the initial instruction. We will consider the instruction graphs where there is at least one halting computation. On the other hand, we will consider those in which there is more than one computation, that is, there is a least one non-deterministic decision, otherwise only the singleton sets can be generated (which are included in NLinFIN). 

    With all of this in mind, only one instruction graph remains, the same as depicted in Figure <ref>. What can be different is the instruction-channel graph, if i_1 is attached to channel not connected to the environment, then only singleton sets can be generated, otherwise the arithmetic progression as stated before.





 §.§ Finite linear combinations

Continuing with the idea of the previous subsection, let us see that with 3 instructions we still have a strong limitation in computational power. First, we define a family of sets that we will try to characterise, let:


    a_w_1,w_2,N_1,N_2 =   {w_1x+w_2y+r | 1≤ x≤ N_1, 1≤ y≤ N_2};
    
            b_w_1,w_2,N_1,N_2 =   {f_w_1,w_2^N_1,N_2(x,y) | 1≤ x≤min(N_1,N_2),
        1≤ y≤ |N_2-N_1|};
    
            f_w_1,w_2^N_1,N_2(x,y) =   {[            (w_1+w_2)x+r,        x < min(N_1,N_2);; (w_1+w_2)N_1 + w_2y + r,          x=N_1∧ N_1<N_2,; (w_1+w_2)N_2 + w_1y + r,          x=N_2∧ N_2<N_1,;                          ].


For each w_1,w_2,N_1,N_2∈. Finally, let
A = {a_w_1,w_2,N_1,N_2}_w_1,w_2,N_1,N_2∈,
 B = {b_w_1,w_2,N_1,N_2}_w_1,w_2,N_1,N_2∈, be two family of sets of natural numbers, we define finite linear combinations NCombFIN = {∅}∪ A ∪ B.


    NCombFIN = NVM(p,3,*), for each p≥ 3.



⊆ The idea of this inclusion is to prove that there exists a virus machine for generating: (i) the empty set, (ii) the family of sets A, and (iii) the family of sets B.


    
  (∅) This is trivial, any VM with no halting computations generates the empty set, for instance, a VM of degree (p,3) with p≥ 1, that has a loop of size 3, thus there cannot be a halting computation and the empty set is generated.
    
  (A) Let Π_1 be the virus machine of degree (3,3) visually pre­sented in Figure <ref>. Let us suppose that the number ge­nerated is m = w_1x'+ w_2y' +r; then, the following compu­ta­tion holds. The initial configuration is _0 = (N_1,N_2,1,
i_1,0), from here, one virus is transmitted from host h_1 to the environment replicated by w_1, the following instruction is non-deterministically chosen between i_1 and i_2, here we choose i_1. This process is repeated N_1-x'-1 times. Thus we reach the following configuration, _x'-1 = (N_1-
    x'+1,N_2, 1, i_1,w_1(x'-1)). Here we choose instruction i_2, leading to the configuration C_x'= (N_1-x',N_2,1,i_2,w_1x'). Now the process is analogous with instruction i_2 and host h_2. After y' transition steps, we choose instruction i_3, which will open the channel (h_3,h_0), reaching the halting configuration: C_x'+y'+2= (N_1-x',N_2-y', 0, #, w_1x'+w_2y'+r), that is, after x'+y'+2 steps, the machine halts and sends w_1x'+w_2y'+r viruses to the environment.

 


  (B) Let Π be the VM of degree (3,3) presented in Figure <ref>. Let us see that it can generate any b_w_1,w_2,N_1,N_2, for each w_1,w_2,N_1,N_2∈. The main difference with the previous VM is the loop between instruction i_1 and i_2, that means that we are sending the same amount of viruses from host h_1 and host h_2 to the output region, unless the loop is repeated more than min(N_1,N_2) times, then we are sending viruses only from the host that remains some viruses. After that we send 1 viruses from host h_3 and replicated by r. Finally, the halting configuration is reached, having sent any of the elements from b_w_1,w_2,N_1,N_2.

        
        


⊇ The idea of this proof is based on the possible loops that can exist in a virus machine with 3 instructions. It is important to note that the way to maximise the amount of numbers that can be generated by an explicit virus machine depends on the amount (or size) of nondeterministic loops in the device. 

    We will fix that the initial configuration is always denoted by i_1, and there has to be at least one instruction with out-degree zero; otherwise, we are generating the empty set (which is trivially included). We will fix the instruction with out-degree zero is i_3.

    Lastly, it is important to note that the finite linear progression is included in this family of sets, we just need to fix that w_2=0.

    
        
  Size 0 With no loops, we generate singleton sets and sets of size two, fixing that i_1 is attached to both i_2 and i_3 with weight 1.
        
  Size 1 Here we have the VM presented the previous VM presented in Figure <ref>. The loops can only be in i_1 and i_2. If we fix only one, we can only generate a subset of the previous VM.

        Regarding the host graph, we will suppose that at least one of the instructions from i_1 and i_2 is not attached to a channel associated with the environment. But in those cases we are generating finite linear progressions, that is included in this family of sets. 
        
        
  Size 2 Fixed that the out-degree of instruction i_3, the only possibility is that the loop of size 2 is between instructions i_1 and i_2. In addition to this, there can exist other loops of size 1, these are omitted because we are reaching the previous case. 

        Regarding the host graph, to generate bigger sets than the singleton sets, we need that at least one instruction of i_1 and i_2 send viruses to the environment. We will suppose both of them send viruses from different channels as in other case we are generating the finite linear progressions that are included.

        With all previous cases discarded, there is only one kind of virus machine remaining, this is represented in Figure <ref>.
        
        
  Size 3 This is trivial, as there is no halting computation, thus the empty set is generated.
    




 §.§ Discussion of old ingredients


In this subsection a brief discussion of the results obtained with the previous results is presented in Table <ref>. 






§ NOVEL RESULTS WITH NEW INGREDIENTS


For virus machines in generating mode, the notation used in previous works <cit.> was NVM(p,q,r) where it denotes the family of natural number sets generated by virus machines with at most p hosts, q instructions and r viruses at most at each instant in the computation. The computational completeness has been proven when these ingredients are unbounded <cit.>, that is, NRE = NVM(*,*,*), but the power decreases when one of them is bounded, for example, a characterisation of semilinear sets has been proven in <cit.>, that is, SLIN= NVM(*,*,r) for each r≥ 2. However, the three ingredients mentioned seem to be poor information. We propose the following notation:


    NVM_β(h_p,i_q,nvh_r,wc_s,outd_t,α_ħ^u,α_ι^v),


where:

    
  * p,q,r≥ 1 represent the same as before,
    
  * β∈{T,F} represents if each channel is attached to only one instruction, that is, if there is a bijection between instructions and channels, then β = T, otherwise we have β = F,
    
  * s≥ 1 is the maximum weight of the arcs in the host graph,
    
  * t is the maximum out-degree of each host in the host graph,
    
  * u≥ 0 is the greatest loop in the host graph.
    
  * v≥ 0 is the greatest loop in the instruction graph.


The rationale for why we chose these new ingredients will be clearly shown in the following sections; however, let us take a brief look at an introductory idea behind each new ingredient.

First, we believe that the instruction-channel graphs have something to say in the sense of computational power, that is why we fix bijection that will show a new frontier of computational power when we combine it with other ingredients.

Secondly, fixing the directed graphs as trees is a first intention to approach the topology structure of the graphs, fixing them as trees (when u or v are zero) will allow us to fix characterisations to finite sets, as we will see later. Nevertheless, we believe that not only whether or not there is a loop is important, but also the size of the loop. The relation between these sizes and the power of the devices will have interesting results. Note that u=1 is the same as u=0 as there are no self-arcs in the host graph.

In addition, the weight of the arcs is our unique way to increase the amount of viruses, fixing this weight to one where the power falls substantially, but if it is 2 we can get novel universality results.

Lastly, the out-degree of the hosts, we believe that it is also crucial in the restrictions of the computing power, it will be shown in combination with other ingredients.



 §.§ Finite sets



    If a VM generates an infinite set of natural numbers, then its host graph has at least a cycle.


    Let Π a VM of degree (p,q) whose host graph is acyclic and where n_1,…, n_p∈ is the initial number of hosts. Let us see that the greatest number that can be generated is bounded.

    First, remark that as there are no cycles, the host graph is a tree, to generate the greatest number, we will always choose to transmit the viruses through the maximum weight channel. This idea is shown in Figure <ref>.

    

    Note that in order to obtain more replication with the fixed amount of hosts, that is, to maximise the depth, the out-degree of each host will be fixed to 1. Thus, the host graph will have the structure shown in Figure <ref>.

    

    Thus, the greatest number of viruses that can be generated is sending all viruses from host h_1 to host h_2, and then all of those viruses to host h_3 and so on until h_out. The number of viruses that reach the output region is:
    
    ∑_i=1^p((∏_j=i^pw_j)· n_i).


    In summary, the greatest number that can be generated is bounded, and thus the set generated is finite.



    NVM_F(h_*,i_*, nvh_*, wc_*,outd_*,α^ħ_*,α^ι_0) ⊆ NFIN.


With finite sets, there are some interesting results; you get the characterisation as wc_1 limits to a finite number of viruses.


    The following family of sets are equal to NFIN:
    
        
  *  NVM_F(h_1,i_*,nvh_*,wc_s,outd_t,α^ħ_0,α^ι_0), for each s,t≥ 1.
        
  *  NVM_T(h_*,i_*,nvh_r,wc_*,outd_t,α^ħ_0,α^ι_0), for each r,t≥ 1.
    



    Separating by the two cases, we have:
    
        
  * The proof is followed by the previous corollary and the inclusions of <cit.>. In a simple glance, we can see in Figure <ref> that both the instruction and the host graphs are trees. 
        
  * On the other hand, in Figure <ref> we can highlight that we have one channel associated with only one instruction, that is, β = T.
    


Now we move to similar results with the instruction graph fixed as a tree. For this, the following result holds:


    If the instruction graph is a tree, then all computations halt. In addition, the number of transition steps is bounded by the depth of the tree.



    NVM_F(h_*,i_*, nvh_*, wc_*,outd_*,α^ħ_0,α^ι_*) ⊆ NFIN


    The inclusion is direct by Proposition <ref>, as all computations halt, then every virus machine halts in a finite number of steps, thus the set of numbers that can be generated is finite.



    The following family of sets are equal to NFIN:
    
        
  * NVM_F(h_1,i_*,nvh_*,wc_s,outd_t,α^ħ_0,α^ι_0), for each s,t≥ 1.
        
  * NVM_T(h_*,i_*,nvh_r,wc_*,outd_t,α^ħ_0,α^ι_0), for each r,t≥ 1.
        
  * NVM_F(h_p,i_*,nvh_r,wc_s,outd_t,α^ħ_u,α^ι_0), for each p,r,s,t,
u≥ 2.
    



    The proof of the first two statements is analogous to the proof of Theorem <ref>. For the third statement, it can be proved by applying the Lemma <ref> and the Corollary <ref>.


It is interesting to note that now with v = 0, we have gone from strict inclusion in Proposition <ref> to characterisation in the last statement in Theorem <ref>.



 §.§ Semilinear sets


The authors in <cit.> characterise semilinear sets by VMs in generating mode, that is, SLIN = (*,*,r), for all r≥ 2. Reviewing how the proof was constructed, we can assure the following result with new ingredients:


    SLIN = NVM_T(h_*,i_*, nvh_r,wc_*,outd_t,α^ħ_u,α^ι_v)
 for all r,t,u≥2 and v≥ 3.


The question that arises is can we get another trade-off in the unbounded ingredients? In this section, we will prove that we can by the demonstration of the following theorem:


    SLIN = NVM_F(h_p,i_*, nvh_r,wc_s,outd_t,α^ħ_u,α^ι_*)
 for each p,r,s,t,u≥2.



    ⊇ This part of the proof is equal to the technique applied by the authors in <cit.>. That is simulating the right-linear grammar, this is possible due to the amount of viruses of each host at each moment of the computation is bounded, thus the number of possible configurations is finite. We still are in the same conditions so the same proof can be made.
    
    ⊆ For simplicity, this part of the proof has been divided in two Lemmas. Applying Lemma <ref>, the arithmetic progressions are generated by this family of VMs. Lastly, Lemma <ref> shows the closure under union. Thus, the inclusion is formally proved.
    



    For each n,r≥ 1, we have the following inclusion {n· i + r | i≥ 1}∈ NVM_F(h_2,i_3(n+r), nvh_2,
    wc_2,outd_2,α^ħ_2,α^ι_*). More precisely, it will be generated by the virus machine Π_arith of degree (2,3n+3r) defined as:

    
    Π_arith = (Γ, H = {h_1,h_2}, I , D_H, D_I, G_C, 0,1,i_1,h_0),


    where,
    
        
  * I = {i_1,…,i_3n+3r};
        
  * D_H = (H∪{h_0}, E_H = {(h_1,h_2),(h_1,h_0),(h_2,h_1)}, w_H), where

        w_H(h_1,h_0) = w_H(h_2,h_1) = 1, and w_H(h_1,h_2) = 2;
        
  * D_I = (I, E_I, w_I), where {(i_k,i_k+1) | k∈{1,…, 3n+3r-1}}∪{(i_3n,i_1)}, and w_I (i_k,i_k') = 1 for each (i_k,i_k')∈ E_I;
        
  * G_C = (E_H ∪ I, E_C), where {{i_j,f(j)} | j ∈{1,…, 3n+3r}}, being
        
    f(j) = {[ (h_1,h_0),  j ≡ 0  3,; (h_1,h_2),  j ≡ 1  3,; (h_2,h_1),  j ≡ 2  3. ].

      

    



    Suppose that the number generated is m· n+r with m≥ 1, then the following invariant holds:

    
    φ(k) ≡ C_3k = (1,0,i_1,k· n),  for each  0≤ k < m


    The idea of this invariant is taking the non-deterministic decision at instruction i_3n, that is, to go back to instruction i_1. In particular, φ(m-1) is true. From this, a instruction i_3n is reached, and we take the decision to go to instruction i_3n+1 with the following configuration C_3m = (1,0,i_3n+1,m· n). After that, it is straightforward to reach the halting configuration.

    
    C_3m+3r = (1,0,#,m· n + r)

    
    Thus, there exists a computation that generates the number m· n +r. 

    Regarding the other inclusion, that is, for each halting computation of the machine, the number generated is in the set proposed. It can be seen in a simple glance that for any generated number we will have the previous invariant formula, and after that, we send r viruses to the environment. Thus, the other inclusion is proved.



    Let Q_1,Q_2,…,Q_m⊆ with m>0 arithmetical progressions, then ∪_j=1^mQ_j ∈ NVM_F(h_p,i_*, nvh_r,wc_s,outd_t,α^ħ_u,α^ι_*) for each p,r,s,t,u≥2.



    The main idea of the proof is that we can also keep the host graph in the union of each subset. The induction technique will be used for this purpose.

    Q_1∪Q_2 As both Q_1,Q_2 are arithmetic progression, we can apply the Lemma <ref>, we will denote that Q_j is generated by Π_j for each j∈{1,2}, this sub-index notation is extended to the heterogeneous networks of each machine. Note that the host graphs and the initial amount of viruses of each virus machine remains equal. The construction is visually explained in Figure <ref>. From which it can be seen in a simple glance that it generates Q_1∪ Q_2, proving that Q_1∪ Q_2 is in the families of the statement. 

    ∪_j=1^m-1Q_j ∪Q_m For the inductive step, let us suppose that a virus machine Π_m-1 generates the union with host graph mentioned in the base case. Applying again Lemma <ref>, let Π_m the virus machine that generates the set Q_m. The construction of the virus machine that generates the union of both sets will be analogous to the previous one, visually explained in Figure <ref>, thus it has been proved that ∪_j=1^m Q_j is in the families of the statement.
    
    
    
    




 §.§ Universality


Lastly, it is interesting to note that new frontiers of universality can be obtained with these novel ingredients. 


    NRE = NVM_F(h_*,i_*,nvh_*,wc_s,out_*,α^ħ_*,α^ι_*) for each s≥ 2.



    For the proof, we refer to <cit.>, where the Turing completeness was proven by simulating register machines in a modular way. In that simulation, one can see on a simple glance that the weight of the channels are bounded by 2, thus the theorem is proved.




 §.§ Discussion of new ingredients


Here, table <ref> summarises the previous results in addition to the new results obtained in this work with the proposed new ingredients. First, the singleton sets were characterised in the previous section with the old ingredients; note that including the new ingredients is straightforward. With finite sets, it is interesting to note that the new characterisations were previously inclusions, just fixing the host graph and/or the instruction graph to a tree. Showing the strict inclusion with the loops of size two in the host graph and size three in the instruciton graph. These loops restrictions are the same for characterising the semilinear sets, but unbounding the number of hosts instead, note that despite the β ingredient seems to be very restrictive, we can characterise this family of sets. The most interesting result of this section arises when we unbound the size of the loops in the instruction graph and β = F, which allow us to reduce the number of necessary hosts to two. Last but not least, the universality result from <cit.> has been revised with the new ingredients, showing that there is a huge frontier in computational power, from finite sets with weight 1, to NRE with weight 2.





§ CONCLUSIONS


Some directions for future work include the extension to parallel VMs e.g. <cit.>.
In such VMs more than one instruction can be active at each computation step, so some of the restrictions in the present work may not apply.
Another natural extension of the present work is to apply them to VMs for accepting inputs or as transducers, that is, computing functions using both input and output <cit.>.

The results in normal forms from the present work can be­tter inform the design of applications or implementations of VMs.
For instance, perhaps with ideas from <cit.>, sequels of the simulator from <cit.>, or applications of VMs such as edge detection <cit.>, or cryptography <cit.> can be improved by applying simplifications based on normal forms.
Similarly, knowing which types of instruction, host, or channel graphs are used, the reachability of one configuration from another and other properties, can be decidable: in this case, searching for efficient algorithms and applications to formal verification are open problems.
The results of the classes below NRE help inform the computational complexity of problem solving with a model.
In the case of VMs, a future direction is to investigate deeper into “sub-NRE” classes: in this way a better view of efficiency or lack of it, can be given for VMs.
Lastly, new and optimal lower bounds are expected to improve the results of the present work, summarised in Table <ref>.
New normal forms can perhaps include new ingredients or semantics not previously considered, such as a deeper focus on deterministic versus nondeterministic computations.

fundam


