Algorithmic networks: Central time to trigger expected emergent open-endedness

• Published in: Theoretical computer science 2019-09, Vol.785, p.83-116
• Main Authors: Abrahão, Felipe S., Wehmuth, Klaus, Ziviani, Artur
• Format: Article
• Language: English
• Subjects: Algorithmic information; Complex systems; Emergence; Network science; Small diameter; Turing machines
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2019.03.008

This article investigates emergence of algorithmic complexity in computable systems that can share information on a network. To this end, we use a theoretical approach from information theory, computability theory, and complex networks theory. One key studied question is how much emergent complexity arises when a population of computable systems is networked compared with when this population is isolated. First, we define a general model for networked theoretical machines, which we call algorithmic networks. Then, we narrow our scope to investigate algorithmic networks that increase the average fitnesses of nodes in a scenario in which each node imitates the fittest neighbor and the randomly generated population is networked by a time-varying graph. We show that there are graph-topological conditions that make these algorithmic networks have the property of expected emergent open-endedness for large enough populations. In other words, the expected emergent algorithmic complexity of a node tends to infinity as the population size tends to infinity. Given a dynamic network, we show that these conditions imply the existence of a central time to trigger expected emergent open-endedness. Moreover, we show that networks with small diameter compared to the network size meet these conditions.