Why are living systems complex? Why does the biosphere contain living beings with complexity features beyond those of the simplest replicators? What kind of evolutionary pressures result in more complex life forms? These are key questions that pervade the problem of how complexity arises in evolution. One particular way of tackling this is grounded in an algorithmic description of life: living organisms can be seen as systems that extract and process information from their surroundings in order to reduce uncertainty. Here we take this computational approach using a simple bit string model of coevolving agents and their parasites. While agents try to predict their worlds, parasites do the same with their hosts. The result of this process is that, in order to escape their parasites, the host agents expand their computational complexity despite the cost of maintaining it. This, in turn, is followed by increasingly complex parasitic counterparts. Such arms races display several qualitative phases, from monotonous to punctuated evolution or even ecological collapse. Our minimal model illustrates the relevance of parasites in providing an active mechanism for expanding living complexity beyond simple replicators, suggesting that parasitic agents are likely to be a major evolutionary driver for biological complexity.

Spatial self-organization emerges in distributed systems exhibiting local interactions when nonlinearities and the appropriate propagation of signals are at work. These kinds of phenomena can be modeled with different frameworks, typically cellular automata or reaction-diffusion systems. A different class of dynamical processes involves the correlated movement of agents over space, which can be mediated through chemotactic movement or minimization of cell-cell interaction energy. A classic example of the latter is given by the formation of spatially segregated assemblies when cells display differential adhesion. Here we consider a new class of dynamical models, involving cell adhesion among two stochastically exchangeable cell states as a minimal model capable of exhibiting well-defined, ordered spatial patterns. Our results suggest that a whole space of pattern-forming rules is hosted by the combination of physical differential adhesion and the value of probabilities modulating cell phenotypic switching, showing that Turing-like patterns can be obtained without resorting to reaction-diffusion processes. If the model is expanded allowing cells to proliferate and die in an environment where diffusible nutrient and toxic waste are at play, different phases are observed, characterized by regularly spaced patterns. The analysis of the parameter space reveals that certain phases reach higher population levels than other modes of organization. A detailed exploration of the mean-field theory is also presented. Finally we let populations of cells with different adhesion matrices compete for reproduction, showing that, in our model, structural organization can improve the fitness of a given cell population. The implications of these results for ecological and evolutionary models of pattern formation and the emergence of multicellularity are outlined.