Complex Systems

Emergent Open-Endedness from Contagion of the Fittest Download PDF

Felipe S. Abrahão
Klaus Wehmuth
Artur Ziviani

National Laboratory for Scientific Computing (LNCC)
25651-075 – Petropolis, RJ – Brazil


This paper presents a theoretical investigation of the general problem of emergent irreducible information in networked populations of computable systems. In particular, we narrow our scope to study this problem in algorithmic networks composed of randomly generated Turing machines that follow a susceptible-infected-susceptible contagion model of imitation of the fittest neighbor. We show that there is a lower bound for the stationary prevalence (i.e., the average density of infected nodes by the fittest nodes) that triggers expected (local) emergent open-endedness, that is, that triggers an unlimited increase of the expected local emergent algorithmic complexity (or information) of a node as the population size grows. In addition, we show that static networks with a power-law degree distribution following the Barabási–Albert model satisfy this lower bound and thus display expected (local) emergent open-endedness.

Keywords: emergence; algorithmic information; spreading; complex networks; distributed systems