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

DOI10.1016/J.TCS.2019.03.008MaRDI QIDQ2315017zbMATH OpenOpenAlexWikidataFDO

Authors Felipe S. Abrahão, Klaus Wehmuth, Artur Ziviani

Publication date 31 July 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.09149

zbMATH Keywords

emergencealgorithmic informationcomplex systemsnetwork scienceTuring machinessmall diameter

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: This article investigates emergence and complexity in complex systems that can share information on a network. To this end, we use a theoretical approach from information theory, computability theory, and complex networks. One key studied question is how much emergent complexity (or information) 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 optimize 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 cause these algorithmic networks to 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. We also discuss future research based on how our results are related to some problems in network science, information theory, computability theory, distributed computing, game theory, evolutionary biology, and synergy in complex systems.

Recommendations

• Emergent Open-Endedness from Contagion of the Fittest
• On measuring the complexity of networks: Kolmogorov complexity versus entropy
• Complexity of networks
• The calculi of emergence: Computation, dynamics and induction
• scientific article; zbMATH DE number 1843106

Cites work

• scientific article; zbMATH DE number 5145286 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1911266 (Why is no real title available?)
• scientific article; zbMATH DE number 5252406 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic networks: central time to trigger expected emergent open-endedness
• Algorithmic randomness and complexity.
• Computing halting probabilities from other halting probabilities
• Emergent Open-Endedness from Contagion of the Fittest
• Evolution of contingent altruism when cooperation is expensive
• Foundations of complex systems. Emergence, information and prediction
• Graph theory
• Life as Evolving Software
• Multiaspect graphs: algebraic representation and algorithms
• Network Analysis
• On multiaspect graphs
• Proving Darwin. Making biology mathematical
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• Scale-free networks: a decade and beyond
• The ``paradox of computability and a recursive relative version of the busy beaver function
• The decidable properties of subrecursive functions
• The diameter of a scale-free random graph
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• ``Follow the leader learning dynamics on networks

Cited in

(2)

• On sequential structures in incompressible multidimensional networks
• Algorithmic networks: central time to trigger expected emergent open-endedness

This page was built for publication: Algorithmic networks: central time to trigger expected emergent open-endedness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2315017)