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

Autor(es)

Abrahao, Felipe S. ^[1] ; Wehmuth, Klaus ^[1] ; Ziviani, Artur ^[1]

Afiliação do(s) autor(es)

^[1] Natl Lab Sci Comp LNCC, BR-25651075 Petropolis, RJ - Brazil

• Tipo de documento: Artigo Científico
• Fonte: THEORETICAL COMPUTER SCIENCE; v. 785, p. 83-116, SEP 20 2019.
• Citações Web of Science: 0

Resumo

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. (C) 2019 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 15/24493-1 - INECiD: internet e a nova era de ciência de dados
• Beneficiário: Artur Ziviani
• Modalidade de apoio: Auxílio à Pesquisa - Regular