| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Natl Lab Sci Comp LNCC, BR-25651075 Petropolis, RJ - Brazil
Total Affiliations: 1
|
| Document type: | Journal article |
| Source: | THEORETICAL COMPUTER SCIENCE; v. 785, p. 83-116, SEP 20 2019. |
| Web of Science Citations: | 0 |
| 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. (C) 2019 Elsevier B.V. All rights reserved. (AU) | |
| FAPESP's process: | 15/24493-1 - INECiD: internet and the new age of data science |
| Grantee: | Artur Ziviani |
| Support Opportunities: | Regular Research Grants |