Numerical evaluation of algorithmic complexity for short strings: A glance into the innermost structure of randomness

We describe an alternative method (to compression) that combines several theoretical and experimental results to numerically approximate the algorithmic Kolmogorov-Chaitin complexity of all ? n = 1 8 2 n bit strings up to 8 bits long, and for some between 9 and 16 bits long. This is done by an exhaustive execution of all deterministic 2-symbol Turing machines with up to four states for which the halting times are known thanks to the Busy Beaver problem, that is 11019960576 machines. An output frequency distribution is then computed, from which the algorithmic probability is calculated and the algorithmic complexity evaluated by way of the Levin-Chaitin coding theorem.

• Publication year

  2011

• Venue

  Applied Mathematics and Computation

• Publication date

  2011-01-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.amc.2011.10.006arXiv 1101.4795
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Explicit formulas for OPUC and POPUC associated with measures which are simple modifications of the Lebesgue measure

  2015cited by this paper
• On the Algorithmic Nature of the World

  2009cited by this paper
• Computing the Uncomputable Rado Sigma Function

  2009cited by this paper
• A note on the estimation of string complexity for short strings

  2009cited by this paper
• Randomness And Complexity, from Leibniz To Chaitin

  2007cited by this paper
• Algorithmic information theory

  2007cited by this paper
• On the Kolmogorov-Chaitin Complexity for short sequences

  2007cited by this paper
• Most Programs Stop Quickly or Never Halt

  2006cited by this paper
• Acceleration Techniques for Busy Beaver Candidates ACCELERATION TECHNIQUES FOR BUSY BEAVER CANDIDATES

  2004cited by this paper
• A New Kind of Science

  2003cited by this paper
• 20世紀の名著名論：A.M.Turing: On Computable Numbers with an Application to the Entscheidungsproblem

  2002cited by this paper
• A PRELIMINARY REPORT ON A GENERAL THEORY OF INDUCTIVE INFERENCE

  2001cited by this paper
• A Version of Ω for which ZFC Cannot Predict a Single Bit

  2000cited by this paper
• A Version of $\Omega$ for which ZFC can not Predict a Single Bit

  1999cited by this paper
• The miraculous universal distribution

  1997cited by this paper
• Book Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series))

  1997cited by this paper
• Information and Randomness: An Algorithmic Perspective

  1994cited by this paper
• Information and Randomness: An Algorithmic Perspective

  1994influential reference
• An Introduction to Kolmogorov Complexity and Its Applications

  1993cited by this paper
• The complex behavior of simple machines

  1990cited by this paper
• Attacking the Busy Beaver 5

  1990cited by this paper
• Computing the Busy Beaver Function

  1987cited by this paper
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms

  1984cited by this paper
• The determination of the value of Rado’s noncomputable function Σ() for four-state Turing machines

  1983influential reference
• On the Complexity of Finite Sequences

  1976cited by this paper
• Three approaches to the quantitative definition of information

  1968cited by this paper
• Computer Studies of Turing Machine Problems

  1965influential reference
• On non-computable functions

  1962cited by this paper
• On computable numbers, with an application to the Entscheidungsproblem

  1937cited by this paper
• Cdmtcs Research Report Series Computing a Glimpse of Randomness Computing a Glimpse of Randomness

  year unknowncited by this paper

• Task-related differences in network connectivity and dynamics in people with severe opioid use disorder compared with healthy controls

  2026cites this paper
• Bounding phenotype transition probabilities via conditional complexity

  2025cites this paper
• Highly-sensitive measure of complexity captures Boolean networks’ regimes and temporal order more optimally

  2025cites this paper
• Binarized Neural Networks Converge Toward Algorithmic Simplicity: Empirical Support for the Learning-as-Compression Hypothesis

  2025influential citation
• Highly-sensitive measure of complexity captures boolean networks regimes and temporal order more optimally

  2024cites this paper
• Assembly Theory is an approximation to algorithmic complexity based on LZ compression that does not explain selection or evolution

  2024cites this paper
• An Additively Optimal Interpreter for Approximating Kolmogorov Prefix Complexity

  2024influential citation
• Visualizing Quantum Circuit Probability - estimating computational action for quantum program synthesis

  2023cites this paper
• Brain-imaging evidence for compression of binary sound sequences in human memory

  2023cites this paper
• Visualizing Quantum Circuit Probability: Estimating Quantum State Complexity for Quantum Program Synthesis

  2023cites this paper
• Can compression take place in working memory without a central contribution of long-term memory?

  2023cites this paper
• Language of fungi derived from their electrical spiking activity

  2022cites this paper
• Compression of binary sound sequences in human working memory

  2022cites this paper
• Combining Algorithmic Information Dynamics Concepts and Machine Learning for Electroencephalography Analysis: What Can We Get?

  2022cites this paper
• Comprehensive computational analysis of epigenetic descriptors affecting CRISPR-Cas9 off-target activity

  2022cites this paper
• On the salient limitations of the methods of assembly theory and their classification of molecular biosignatures

  2022cites this paper
• Low complexity, low probability patterns and consequences for algorithmic probability applications

  2022cites this paper
• A Less Traditional Approach to Biomedical Signal Processing for Sepsis Prediction

  2022cites this paper
• What Should I Notice? Using Algorithmic Information Theory to Evaluate the Memorability of Events in Smart Homes

  2022cites this paper
• Algorithmic Information Dynamics of Cellular Automata

  2021cites this paper
• Language of fungi derived from electrical spiking activity

  2021cites this paper
• A theory of memory for binary sequences: Evidence for a mental compression algorithm in humans

  2021cites this paper
• Automatic analysis of artistic paintings using information-based measures

  2021cites this paper
• An Information Theory Approach to Aesthetic Assessment of Visual Patterns

  2021cites this paper
• Algorithmic Probability-Guided Machine Learning on Non-Differentiable Spaces

  2021influential citation
• Un ecosistema llamado universidad

  2021cites this paper
• Children’s working memory develops at similar rates for sequences differing in compressibility

  2020cites this paper
• A Methodology for Evaluating the Extensibility of Boolean Networks' Structure and Function

  2020cites this paper
• Algorithmic Information Dynamics

  2020cites this paper
• Measuring Complexity in Financial Data

  2020cites this paper
• Time for Change: Implementation of Aksentijevic-Gibson Complexity in Psychology

  2020cites this paper
• Quantifying Value with Effective Complexity

  2020cites this paper
• A Review of Methods for Estimating Algorithmic Complexity and Beyond: Options, and Challenges

  2020influential citation
• A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions

  2020cites this paper
• On the Complex Behaviour of Natural and Artificial Machines and Systems

  2020cites this paper
• ALGORITHMICALLY RANDOM GENERALIZED GRAPHS AND ITS TOPOLOGICAL PROPERTIES

  2019cites this paper
• Algorithmic Probability Method Versus Kolmogorov Complexity with No-Threshold Encoding Scheme for Short Time Series: An Analysis of Day-To-Day Hourly Solar Radiation Time Series over Tropical Western Indian Ocean

  2019cites this paper
• Performance of Password Guessing Enumerators Under Cracking Conditions

  2019cites this paper
• La psychologie de la complexité

  2019cites this paper
• ALGORITHMICALLY RANDOM GENERALIZED GRAPHS AND THEIR TOPOLOGICAL PROPERTIES

  2019cites this paper
• Algorithmic complexity of multiplex networks

  2019cites this paper
• Causal deconvolution by algorithmic generative models

  2019cites this paper
• Algorithmic Probability-guided Supervised Machine Learning on Non-differentiable Spaces

  2019influential citation
• Compression is Comprehension, and the Unreasonable Effectiveness of Digital Computation in the Natural World

  2019cites this paper
• Estimations of Integrated Information Based on Algorithmic Complexity and Dynamic Querying

  2019cites this paper
• Detection of Movement toward Randomness by Applying the Block Decomposition Method to a Simple Model of the Circulatory System

  2019cites this paper
• Complexity Steering in Cellular Automata

  2018cites this paper
• Input–output maps are strongly biased towards simple outputs

  2018cites this paper
• Algorithmic Complexity and Reprogrammability of Chemical Structure Networks

  2018cites this paper
• Symmetry and Algorithmic Complexity of Polyominoes and Polyhedral Graphs

  2018cites this paper
• Compression in Working Memory and Its Relationship With Fluid Intelligence.

  2018cites this paper
• Running head : RANDOMNESS AS INFERENCE 1 Subjective randomness as statistical inference

  2018cites this paper
• Subjective randomness as statistical inference.

  2018cites this paper
• An Algorithmic Refinement of Maxent Induces a Thermodynamic-like Behaviour in the Reprogrammability of Generative Mechanisms

  2018cites this paper
• Exploring Halting Times for Unconventional Halting Schemes

  2018influential citation
• Data Dimension Reduction and Network Sparsification Based on Minimal Algorithmic Information Loss

  2018cites this paper
• Symmetry and Correspondence of Algorithmic Complexity over Geometric, Spatial and Topological Representations

  2018cites this paper
• Analogical proportions: From equality to inequality

  2018cites this paper
• A Review of Graph and Network Complexity from an Algorithmic Information Perspective

  2018cites this paper
• Using Algorithmic Complexity to Differentiate Cognitive States in fMRI

  2018cites this paper
• An Algorithmic Look at Financial Volatility

  2018influential citation
• The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy

  2018cites this paper
• Parameter-free Network Sparsification and Data Reduction by Minimal Algorithmic Information Loss

  2018cites this paper
• On Sequential Structures in Incompressible Multidimensional Networks

  2018cites this paper
• Algorithmic information and incompressibility of families of multidimensional networks.

  2018cites this paper
• Algorithmic information distortions and incompressibility in uniform multidimensional networks

  2018cites this paper
• Ab initio Algorithmic Causal Deconvolution of Intertwined Programs and Networks by Generative Mechanism

  2018cites this paper
• Paths to Unconventional Computing: Causality in Complexity

  2017cites this paper
• Algorithmic Networks: central time to trigger expected emergent open-endedness

  2017cites this paper
• Approximations to Algorithmic Probability

  2017cites this paper
• Computing by nowhere increasing complexity

  2017cites this paper
• On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy

  2017cites this paper
• Algorithmically probable mutations reproduce aspects of evolution such as convergence rate, genetic memory, modularity, diversity explosions, and mass extinction

  2017cites this paper
• DNA Sequence Complexity Reveals Structure Beyond GC Content in Nucleosome Occupancy

  2017cites this paper
• Representation and Reality in Humans, Other Living Organisms and Intelligent Machines

  2017influential citation
• Boolean Analogical Proportions - Axiomatics and Algorithmic Complexity Issues

  2017cites this paper
• An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems

  2017cites this paper
• Human behavioral complexity peaks at age 25

  2017cites this paper
• Asymptotic Intrinsic Universality and Natural Reprogrammability by Behavioural Emulation

  2017cites this paper
• Training-free measures based on algorithmic probability identify high nucleosome occupancy in DNA sequences

  2017cites this paper
• Coding-theorem like behaviour and emergence of the universal distribution from resource-bounded algorithmic probability

  2017cites this paper
• Symbolic and Quantitative Approaches to Reasoning with Uncertainty

  2017cites this paper
• Algorithmically probable mutations reproduce aspects of evolution, such as convergence rate, genetic memory and modularity

  2017cites this paper
• The Measure of All Minds: Evaluating Natural and Artificial Intelligence

  2017cites this paper
• A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity

  2016cites this paper
• Implantations et protections de mécanismes cryptographiques logiciels et matériels. (Implementations and protections of software and hardware cryptographic mechanisms)

  2016cites this paper
• Numerical Investigation of Graph Spectra and Information Interpretability of Eigenvalues

  2015cites this paper
• A Computable Measure of Algorithmic Probability by Finite Approximations

  2015cites this paper
• Complexity Measurement Based on Information Theory and Kolmogorov Complexity

  2015cites this paper
• Approximations of algorithmic and structural complexity validate cognitive-behavioral experimental results

  2015influential citation
• Quantifying loss of information in network-based dimensionality reduction techniques

  2015cites this paper
• A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences

  2015cites this paper
• The Information-theoretic and Algorithmic Approach to Human, Animal and Artificial Cognition

  2015cites this paper
• Cross-boundary Behavioural Reprogrammability Reveals Evidence of Pervasive Universality

  2015cites this paper
• Chunking in Working Memory and its Relationship to Intelligence

  2015cites this paper
• On environment difficulty and discriminating power

  2015cites this paper
• Algorithmicity and programmability in natural computing with the Game of Life as in silico case study

  2015cites this paper
• Information Theory, Kolmogorov Complexity and Algorithmic Probability in Network Biology

  2014cites this paper
• Algorithmic Complexity of Financial Motions

  2014cites this paper
• Conceptions du hasard et biais probabilistes chez des enseignants du second degré : effet d'une formation courte

  2014cites this paper