Paper Info
Title
Algorithmic networks: Central time to trigger expected emergent open-endedness
Abstract
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.
Year
DOI
Venue
2017
10.1016/j.tcs.2019.03.008
Theoretical Computer Science
Keywords
Field
DocType
Emergence,Algorithmic information,Turing machines,Network science,Complex systems,Small diameter
Information theory,Dynamic network analysis,Population,Discrete mathematics,Computer science,Computability theory,Infinity,Theoretical computer science,Population size,Survival of the fittest,Complex network,Artificial intelligence
Journal
Volume
ISSN
Citations 
785
0304-3975
0
PageRank 
References 
Authors
0.34
16
3
Name
Order
Citations
PageRank
Felipe S. Abrahão100.68
Klaus Wehmuth27010.17
Artur Ziviani364656.62