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

DOI10.1016/j.amc.2011.10.006zbMath1448.68250arXiv1101.4795OpenAlexW2116300733MaRDI QIDQ2249007

Jean-Paul Delahaye, Hector Zenil

Publication date: 27 June 2014

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic complexityalgorithmic probabilityhalting probabilityLevin-Chaitin coding theoremKolmogorov-Chaitin complexityprogram-size complexitybusy beaver problemChaitin's \({\Omega}\)Levin's universal distribution

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (11)

Computer Runtimes and the Length of Proofs ⋮ Unpredictability and Computational Irreducibility ⋮ On measuring the complexity of networks: Kolmogorov complexity versus entropy ⋮ A computable measure of algorithmic probability by finite approximations with an application to integer sequences ⋮ An algorithmic look at financial volatility ⋮ Analogical proportions: from equality to inequality ⋮ Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks ⋮ Algorithmic information dynamics of cellular automata ⋮ Model discovery and discrete inverse problems with cellular automata and Boolean networks ⋮ ASYMPTOTIC BEHAVIOR AND RATIOS OF COMPLEXITY IN CELLULAR AUTOMATA ⋮ Turing patterns with Turing machines: emergence and low-level structure formation

Uses Software

• Wolfram Demonstrations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The miraculous universal distribution
• Most programs stop quickly or never halt
• The Determination of the Value of Rado's Noncomputable Function | sum(k) for Four-State Turing Machines
• On Non-Computable Functions
• On the Kolmogorov-Chaitin Complexity for short sequences
• Computer Studies of Turing Machine Problems
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness