Search

The Game of Life (GoL), one well known 2D cellular automaton, does not typically ensure interesting long-term phenotypic dynamics. Therefore, while being Turing complete, GoL cannot be said to be open-ended. In this work, we extend GoL with the opportunity for local mutations, thus enabling a heterogeneous life-like cellular automaton guided by an evolutionary inner loop. Additionally, we introduce the concept of cell ageing to ensure that cell aliveness (activated by inheritance with variation, and controlled by ageing) and actual cell computation (governed by life-like rules on local neighborhoods) are kept conceptually separated. We conduct an experimental campaign to identify suitable parameters that produce long-term phenotypic dynamics and favor genotypic innovations., Comment: 16 pages, 9 Figures

We propose a novel definition of life in terms of which its emergence in the universe is expected, and its ever-creative open-ended evolution is entailed by no law. Living organisms are Kantian Wholes that achieve Catalytic Closure, Constraint Closure, and Spatial Closure. We here unite for the first time two established mathematical theories, namely Collectively Autocatalytic Sets and the Theory of the Adjacent Possible. The former establishes that a first-order phase transition to molecular reproduction is expected in the chemical evolution of the universe where the diversity and complexity of molecules increases; the latter posits that, under loose hypotheses, if the system starts with a small number of beginning molecules, each of which can combine with copies of itself or other molecules to make new molecules, over time the number of kinds of molecules increases slowly but then explodes upward hyperbolically. Together these theories imply that life is expected as a phase transition in the evolving universe. The familiar distinction between software and hardware loses its meaning in living cells. We propose new ways to study the phylogeny of metabolisms, new astronomical ways to search for life on exoplanets, new experiments to seek the emergence of the most rudimentary life, and the hint of a coherent testable pathway to prokaryotes with template replication and coding.

Mixed microbial communities, usually composed of various bacterial and fungal species, are fundamental in a plethora of environments, from soil to human gut and skin. Their evolution is a paradigmatic example of intertwined dynamics, where not just the relations among species plays a role, but also the opportunities -- and possible harms -- that each species presents to the others. These opportunities are in fact \textit{affordances}, which can be seized by heritable variation and selection. In this paper, starting from a systemic viewpoint of mixed microbial communities, we focus on the pivotal role of affordances in evolution and we contrast it to the artificial evolution of programs and robots. We maintain that the two realms are neatly separated, in that natural evolution proceeds by extending the space of its possibilities in a completely open way, while the latter is inherently limited by the algorithmic framework it is defined. This discrepancy characterises also an envisioned setting in which robots evolve in the physical world. We present arguments supporting our claim and we propose an experimental setting for assessing our statements. Rather than just discussing the limitations of the artificial evolution of machines, the aim of this contribution is to emphasize the tremendous potential of the evolution of the biosphere, beautifully represented by the evolution of communities of microbes.

Since Newton, all classical and quantum physics depends upon the "Newtonian Paradigm". Here the relevant variables of the system are identified. The boundary conditions creating the phase space of all possible values of the variables are defined. Then, given any initial condition, the differential equations of motion are integrated to yield an entailed trajectory in the phase space. It is fundamental to the Newtonian Paradigm that the set of possibilities that constitute the phase space is always definable and fixed ahead of time. All of this fails for the diachronic evolution of ever new adaptations in any biosphere. The central reason is that living cells achieve Constraint Closure and construct themselves. Living cells, evolving via heritable variation and Natural selection, adaptively construct new in the universe possibilities. The new possibilities are opportunities for new adaptations thereafter seized by heritable variation and Natural Selection. Surprisingly, we can neither define nor deduce the evolving phase spaces ahead of time. We can use no mathematics based on Set Theory to do so. These ever-new adaptations with ever-new relevant variables constitute the ever-changing phase space of evolving biospheres. Because of this, evolving biospheres are entirely outside the Newtonian Paradigm. One consequence is that for any universe such as ours there can be no Final Theory that entails all that comes to exist. The implications are large. We face a third major transition in science beyond the Pythagorean dream that "All is Number". We must give up deducing the diachronic evolution of the biosphere. All of physics, classical and quantum, however, apply to the analysis of existing life, a synchronic analysis. We begin to better understand the emergent creativity of an evolving biosphere. Thus, we are on the edge of inventing a physics-like new statistical mechanics of emergence.

We approach the question "What is Consciousness?" in a new way, not as Descartes' "systematic doubt", but as how organisms find their way in their world. Finding one's way involves finding possible uses of features of the world that might be beneficial or avoiding those that might be harmful. "Possible uses of X to accomplish Y" are "Affordances". The number of uses of X is indefinite (or unknown), the different uses are unordered, are not listable, and are not deducible from one another. All biological adaptations are either affordances seized by heritable variation and selection or, far faster, by the organism acting in its world finding uses of X to accomplish Y. Based on this, we reach rather astonishing conclusions: (1) Artificial general intelligence based on universal Turing machines (UTMs) is not possible, since UTMs cannot "find" novel affordances. (2) Brain-mind is not purely classical physics for no classical physics system can be an analogue computer whose dynamical behaviour can be isomorphic to "possible uses". (3) Brain mind must be partly quantum-supported by increasing evidence at 6.0 sigma to 7.3 sigma. (4) Based on Heisenberg's interpretation of the quantum state as "potentia" converted to "actuals" by measurement, where this interpretation is not a substance dualism, a natural hypothesis is that mind actualizes potentia. This is supported at 5.2 sigma. Then mind's actualizations of entangled brain-mind-world states are experienced as qualia and allow "seeing" or "perceiving" of uses of X to accomplish Y. We can and do jury-rig. Computers cannot. (5) Beyond familiar quantum computers, we discuss the potentialities of trans-Turing-systems.

The evolution of the biosphere unfolds as a luxuriant generative process of new living forms and functions. Organisms adapt to their environment, exploit novel opportunities that are created in this continuous blooming dynamics. Affordances play a fundamental role in the evolution of the biosphere, for organisms can exploit them for new morphological and behavioral adaptations achieved by heritable variations and selection. This way, the opportunities offered by affordances are then actualized as ever novel adaptations. In this paper we maintain that affordances elude a formalization that relies on set theory: we argue that it is not possible to apply set theory to affordances, therefore we cannot devise a set-based mathematical theory of the diachronic evolution of the biosphere., Comment: Minor changes in abstract and sec.2 Added a paragraph in sec.3 on the role of non-ergodicity; added also a paragraph on Turing machines and syntactic information. Sec.5 added a paragraph for clarifying the difference between our statement and the case of chaotic dynamical systems

The ability of responding to environmental stimuli with appropriate actions is a property shared by all living organisms, and it is also sought in the design of robotic systems. Phenotypic plasticity provides a way for achieving this property as it characterises those organisms that, from one genotype, can express different phenotypes in response to different environments, without involving genetic modifications. In this work we study phenotypic plasticity in robots that are equipped with online sensor adaptation. We show that Boolean network controlled robots can attain navigation with collision avoidance by adapting the coupling between proximity sensors and their controlling network without changing its structure. In other terms, these robots, while being characterised by one genotype (i.e. the network) can express a phenotype among many that is suited for the specific environment. We also show that the dynamical regime that makes it possible to attain the best overall performance is the critical one, bringing further evidence to the hypothesis that natural and artificial systems capable of optimally balancing robustness and adaptivity are critical.

Systems that exhibit complex behaviours are often found in a particular dynamical condition, poised between order and disorder. This observation is at the core of the so-called criticality hypothesis, which states that systems in a dynamical regime between order and disorder attain the highest level of computational capabilities and achieve an optimal trade-off between robustness and flexibility. Recent results in cellular and evolutionary biology, neuroscience and computer science have revitalised the interest in the criticality hypothesis, emphasising its role as a viable candidate general law in adaptive complex systems. In this paper we provide an overview of the works on dynamical criticality that are -to the best of our knowledge- particularly relevant for the criticality hypothesis. We review the main contributions concerning dynamics and information processing at the edge of chaos, and we illustrate the main achievements in the study of critical dynamics in biological systems. Finally, we discuss open questions and propose an agenda for future work., Comment: Added references, rephrased some sentences and corrected typos

Random boolean networks are a model of genetic regulatory networks that has proven able to describe experimental data in biology. They not only reproduce important phenomena in cell dynamics, but they are also extremely interesting from a theoretical viewpoint, since it is possible to tune their asymptotic behaviour from order to disorder. The usual approach characterizes network families as a whole, either by means of static or dynamic measures. We show here that a more detailed study, based on the properties of system's attractors, can provide information that makes it possible to predict with higher precision important properties, such as system's response to gene knock-out. A new set of principled measures is introduced, that explains some puzzling behaviours of these networks. These results are not limited to random Boolean network models, but they are general and hold for any discrete model exhibiting similar dynamical characteristics., Comment: 19 pages

The emergence of autocatalytic sets of molecules seems to have played an important role in the origin of life context. Although the possibility to reproduce this emergence in laboratory has received considerable attention, this is still far from being achieved. In order to unravel some key properties enabling the emergence of structures potentially able to sustain their own existence and growth, in this work we investigate the probability to observe them in ensembles of random catalytic reaction networks characterized by different structural properties. From the point of view of network topology, an autocatalytic set have been defined either in term of strongly connected components (SCCs) or as reflexively autocatalytic and food-generated sets (RAFs). We observe that the average level of catalysis differently affects the probability to observe a SCC or a RAF, highlighting the existence of a region where the former can be observed, whereas the latter cannot. This parameter also affects the composition of the RAF, which can be further characterized into linear structures, autocatalysis or SCCs. Interestingly, we show that the different network topology (uniform as opposed to power-law catalysis systems) does not have a significantly divergent impact on SCCs and RAFs appearance, whereas the proportion between cleavages and condensations seems instead to play a role. A major factor that limits the probability of RAF appearance and that may explain some of the difficulties encountered in laboratory seems to be the presence of molecules which can accumulate without being substrate or catalyst of any reaction., Comment: pp 113-126

In this paper we describe a method to identify "relevant subsets" of variables, useful to understand the organization of a dynamical system. The variables belonging to a relevant subset should have a strong integration with the other variables of the same relevant subset, and a much weaker interaction with the other system variables. On this basis, extending previous works on neural networks, an information-theoretic measure is introduced, i.e. the Dynamical Cluster Index, in order to identify good candidate relevant subsets. The method does not require any previous knowledge of the relationships among the system variables, but relies on observations of their values in time. We show its usefulness in several application domains, including: (i) random boolean networks, where the whole network is made of different subnetworks with different topological relationships (independent or interacting subnetworks); (ii) leader-follower dynamics, subject to noise and fluctuations; (iii) catalytic reaction networks in a flow reactor; (iv) the MAPK signaling pathway in eukaryotes. The validity of the method has been tested in cases where the data are generated by a known dynamical model and the Dynamical Cluster Index method is applied in order to uncover significant aspects of its organization; however it is important to stress that it can also be applied to time series coming from field data without any reference to a model. Given that it is based on relative frequencies of sets of values, the method could be applied also to cases where the data are not ordered in time. Several indications to improve the scope and effectiveness of the Dynamical Cluster Index to analyze the organization of complex systems are finally given., Comment: 22 pages

We present and discuss the results of an experimental analysis in the design of Boolean networks by means of genetic algorithms. A population of networks is evolved with the aim of finding a network such that the attractor it reaches is of required length $l$. In general, any target can be defined, provided that it is possible to model the task as an optimisation problem over the space of networks. We experiment with different initial conditions for the networks, namely in ordered, chaotic and critical regions, and also with different target length values. Results show that all kinds of initial networks can attain the desired goal, but with different success ratios: initial populations composed of critical or chaotic networks are more likely to reach the target. Moreover, the evolution starting from critical networks achieves the best overall performance. This study is the first step toward the use of search algorithms as tools for automatically design Boolean networks with required properties., Comment: 13 pages, 7 figures, 2 tables

In this paper we present a new approach to solve the satisfiability problem (SAT), based on boolean networks (BN). We define a mapping between a SAT instance and a BN, and we solve SAT problem by simulating the BN dynamics. We prove that BN fixed points correspond to the SAT solutions. The mapping presented allows to develop a new class of algorithms to solve SAT. Moreover, this new approach suggests new ways to combine symbolic and connectionist computation and provides a general framework for local search algorithms., Comment: 12 pages, 6 figures, 2 tables

Dynamical systems theory and complexity science provide powerful tools for analysing artificial agents and robots. Furthermore, they have been recently proposed also as a source of design principles and guidelines. Boolean networks are a prominent example of complex dynamical systems and they have been shown to effectively capture important phenomena in gene regulation. From an engineering perspective, these models are very compelling, because they can exhibit rich and complex behaviours, in spite of the compactness of their description. In this paper, we propose the use of Boolean networks for controlling robots' behaviour. The network is designed by means of an automatic procedure based on stochastic local search techniques. We show that this approach makes it possible to design a network which enables the robot to accomplish a task that requires the capability of navigating the space using a light stimulus, as well as the formation and use of an internal memory., Comment: 11 pages, 6 figures

We study the properties of the distance between attractors in Random Boolean Networks, a prominent model of genetic regulatory networks. We define three distance measures, upon which attractor distance matrices are constructed and their main statistic parameters are computed. The experimental analysis shows that ordered networks have a very clustered set of attractors, while chaotic networks' attractors are scattered; critical networks show, instead, a pattern with characteristics of both ordered and chaotic networks., Comment: 9 pages, 6 figures. Presented at WIRN 2010 - Italian workshop on neural networks, May 2010. To appear in a volume published by IOS Press

Haplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms on the basis of their genotype. This information allows researchers to perform association studies for the genetic variants involved in diseases and the individual responses to therapeutic agents. A notable approach to the problem is to encode it as a combinatorial problem (under certain hypotheses, such as the pure parsimony criterion) and to solve it using off-the-shelf combinatorial optimization techniques. The main methods applied to Haplotype Inference are either simple greedy heuristic or exact methods (Integer Linear Programming, Semidefinite Programming, SAT encoding) that, at present, are adequate only for moderate size instances. We believe that metaheuristic and hybrid approaches could provide a better scalability. Moreover, metaheuristics can be very easily combined with problem specific heuristics and they can also be integrated with tree-based search techniques, thus providing a promising framework for hybrid systems in which a good trade-off between effectiveness and efficiency can be reached. In this paper we illustrate a feasibility study of the approach and discuss some relevant design issues, such as modeling and design of approximate solvers that combine constructive heuristics, local search-based improvement strategies and learning mechanisms. Besides the relevance of the Haplotype Inference problem itself, this preliminary analysis is also an interesting case study because the formulation of the problem poses some challenges in modeling and hybrid metaheuristic solver design that can be generalized to other problems., Comment: 22 pages, 4 figures Technical Report: DEIS - Alma Mater Studiorum, University of Bologna no. DEIS-LIA-006-07