Abstract During evolution, some living systems grow more complex. They develop new functions and new structures: flying and wings, digestion and digestive systems, swimming and fins, etc. Due to natural selection, this increase in complexity must be operated while keeping livelihood, i.e., the new structures and functions are added while maintaining the original behavior. In this work, we continue the effort of representing the phenomenon of structural and behavioral extension in abstract discrete dynamical systems in order to elucidate some big-picture tendencies. We choose reaction systems as the formal tool, and propose a translation into this new language of the extensibility framework we developed previously. We argue that using reaction systems makes definitions lighter and therefore should allow for better insights from future exhaustive exploration of the extension space.

Abstract The busy beaver game was introduced by Tibor Radó in 1962 and consists in finding the longest halting run that can be achieved by a Turing machine with a given number of states n . The function $$\text {BB}(n)$$ BB ( n ) measuring this length is a well-studied example of an uncomputable function. In this work, we transpose the concept of the busy beaver game to reaction systems—a set rewriting-based model of computing inspired by biochemical reactions. We give a generalized framework for defining various busy beaver challenges and give concrete instantiations for longest runs, periods, preperiods, etc. We further list several busy beaver champions and bounds, depending on what is optimized and what is measured as the size of a reaction system. Finally, we discuss possible implications of our work to thinking about theoretical biology.

International audience

In this paper we consider prescribed sets of rules working on several objects either in parallel – in this case the rules have to take different objects – or else sequentially in any order – in this case several rules may take the same object to work on. We show that prescribed teams of size two, i.e., containing exactly two rules, are sufficient to obtain computational completeness for strings with the simple rules being of the form $$aI_R(b)$$ – meaning that a symbol b can be inserted on the right-hand side of a string ending with a – and $$D_R(b)$$ meaning that a symbol b is erased on the right-hand side of a string. This result is established for systems starting with three initial strings. Using prescribed teams of size three, we may start with only two strings, ending up with the output string and the second string having been reduced to the empty string. We also establish similar results when using the generation of the anti-object $$b^-$$ on the right-hand side of a string instead of deleting the object b, i.e. $$bI_R(b^-)$$ inserts the anti-object $$b^-$$ and the annihilation rule $$b\,b^-$$ assumed to happen immediately whenever b and $$b^-$$ meet deletes the b.

The conference series Machines, Computations and Universality (MCU) traces its roots back to mid of 1990's, and has since been concerned with gaining a deeper understanding of computation through the study of models of general purpose computation.MCU explores computation in the setting of various discrete models (Turing machines, register machines, cellular automata, tile assembly systems, rewriting systems, molecular computing models, neural models, concurrent systems, etc.) and analog and hybrid models (BSS machines, infinite time cellular automata, real machines, quantum computing, etc.).There is a particular (but not exclusive) emphasis given towards the following:

We consider extended spiking neural P systems with the additional possibility of so-called "white hole rules", which send the complete contents of a neuron to other neurons, and we prove that this extension of the original model can easily simulate register machines. Based on this proof, we then define red-green variants of these extended spiking neural P systems with white hole rules and show how to go beyond Turing with these red-green systems. We also discuss the number of actor neurons needed, and the relation of this model to some special variants of Lindenmayer systems.

In this article, we consider leftist insertion-deletion systems (LIDS), in which all rules have contexts on the same (left) side, and may only insert or delete one symbol at a time. We start by introducing extended rules, in which the contexts may be specified as regular expressions, instead of fix ed words. We prove that in this case the computational completeness is achieved when additional control mechanisms are used (graph control with two states, matrix control with binary matrices and random-context control). We then show how rules with regular contexts can be simulated by conventional rules checking one-symbol (resp. two-symbol) left contexts for insertion and two-symbol (resp. one-symbol) left contexts for deletion. This simulation does not generally hold in the controlled case, however. Hence, we provide a construction simulating an arbitrary 2-tag system using extended rules and which can be rewritten in terms of conventional rules of types above, which implies that the latter systems are universal.

In this article we introduce the operations of insertion and deletion working in random context and semi-conditional modes. We show that conditional application of insertion and deletion rules strictly increases the computational power. In the case of semi-conditional insertion-deletion systems, context-free insertion and deletion rules of one symbol are sufficient to achieve computational completeness. In the random context case, our results expose asymmetry between the computational power of insertion and deletion rules: semi-conditional systems of size (2, 0, 0; 1, 1, 0) (with context-free two-symbol insertion rules, and one-symbol deletion rules with one-symbol left context) are computationally complete, while systems of size (1, 1, 0; 2, 0, 0) (and, more generally, of size (1, 1, 0; p, 1, 1)) are not.

International audience

It is known that insertion-deletion (P) systems with two symbols context-free insertion and deletion rules are not computationally complete. It is thus interesting to consider conditions that would allow such systems to reach computational completeness. In this paper we consider insertion-deletion P systems with insertion and deletion operations applied only at the ends of string (we call them exo-operations). We show that such systems with one-symbol insertion and deletion of up to two symbols are computationally complete, and so are systems with insertion of up to two symbols and one-symbol deletion. The question about the computational power of insertion-deletion P systems with one-symbol insertion and one-symbol deletion operations applied at the ends of string is open. However, the tissue P systems reach computationally completeness even in this case.

Splicing test tube systems are one of the first distributed computing models based on splicing. The model introduces (test) tubes where the splicing operation is applied, which are arranged in a communication network with filters that permits to redistribute the words between the tubes at each step. We show that the computational completeness can be achieved with two tubes when the communication graph does not have self-loops. We also construct a universal splicing test tube system with 2 tubes having 23 rules.

We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems using membrane rules with permitting contexts and working in different transition modes, especially for minimal parallelism. Both partial halting and minimal parallelism are based on an arbitrary set of subsets from the set of rules assigned to the membranes.