Tootfinder

Characterizing Agent-Based Model Dynamics via $\epsilon$-Machines and Kolmogorov-Style Complexity
Roberto Garrone (University of Milano-Bicocca)
https://arxiv.org/abs/2510.12729

Characterizing Agent-Based Model Dynamics via $ε$-Machines and Kolmogorov-Style Complexity
We propose a two-level information-theoretic framework for characterizing the informational organization of Agent-Based Model (ABM) dynamics within the broader paradigm of Complex Adaptive Systems (CAS). At the macro level, a pooled $ε$-machine is reconstructed as a reference model that summarizes the system-wide informational regime. At the micro level, $ε$-machines are reconstructed for each caregiver-elder dyad and variable, and are complemented with algorithm-agnostic Kolmogorov-style mea…

Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers
Peter Shaw, James Cohan, Jacob Eisenstein, Kristina Toutanova
https://arxiv.org/abs/2509.22445

Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers
The Minimum Description Length (MDL) principle offers a formal framework for applying Occam's razor in machine learning. However, its application to neural networks such as Transformers is challenging due to the lack of a principled, universal measure for model complexity. This paper introduces the theoretical notion of asymptotically optimal description length objectives, grounded in the theory of Kolmogorov complexity. We establish that a minimizer of such an objective achieves optimal compre…

Formal Framework for Quantum Advantage
Harry Buhrman, Niklas Galke, Konstantinos Meichanetzidis
https://arxiv.org/abs/2510.01953 https://arxiv.org/pdf/2510…

Formal Framework for Quantum Advantage
Motivated by notions of quantum heuristics and by average-case rather than worst-case algorithmic analysis, we define quantum computational advantage in terms of individual problem instances. Inspired by the classical notions of Kolmogorov complexity and instance complexity, we define their quantum versions. This allows us to define queasy instances of computational problems, like e.g. Satisfiability and Factoring, as those whose quantum instance complexity is significantly smaller than their c…

Event-based complexity in atmospheric turbulence
Paolo Paradisi, Rita Cesari
https://arxiv.org/abs/2509.24576 https://arxiv.org/pdf/2509.24576

Event-based complexity in atmospheric turbulence
Since the studies of Kolmogorov and Oboukhov in 1941, the problem of intermittent large velocity excursions was recognized to be one of the most intriguing and elusive aspects of turbulent flows. While many efforts were devoted since 1960s to the magnitude intermittency, related to the statistics of the large increments in the turbulent signals, the attention towards the so-called clustering intermittency has started to increase only in the last two decades, even if some pioneering studies were…

Strong Kurtz Randomness and Binary Expansions of Reordered Computable Numbers
Peter Hertling, Philip Janicki
https://arxiv.org/abs/2509.22406 https://arxiv…

Strong Kurtz Randomness and Binary Expansions of Reordered Computable Numbers
A real number is called left-computable if there exists a computable increasing sequence of rational numbers converging to it. In this article we investigate the Kolmogorov complexity and the binary expansions of a very specific subset of the left-computable numbers. We show in our main result that a real number is reordered computable if, and only if, it is left-computable and not strongly Kurtz random. In preparation of this, we characterize strong Kurtz randomness by a suitable notion of ran…