An almost machine-independent theory of program-length complexity, sophistication, and induction

DOI10.1016/0020-0255(91)90021-LzbMath0717.68044MaRDI QIDQ2638781

Moshe Koppel, Henri Atlan

Publication date: 1991

Published in: Information Sciences (Search for Journal in Brave)

zbMATH Keywords

program-length complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (11)

Sophistication revisited ⋮ Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics) ⋮ Algorithmic Statistics: Forty Years Later ⋮ The cellular computer DNA: Program or data ⋮ Sophistication vs logical depth ⋮ Complexity and meaning in nonlinear dynamical systems ⋮ Information measures for infinite sequences ⋮ Predictability: a way to characterize complexity ⋮ Two Problems for Sophistication ⋮ A comparative classification of complexity measures ⋮ Finite state incompressible infinite sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Process complexity and effective random tests
• Randomness conservation inequalities; information and independence in mathematical theories
• A Theory of Program Size Formally Identical to Information Theory
• General random sequences and learnable sequences
• Complexity-based induction systems: Comparisons and convergence theorems
• Complexity oscillations in infinite binary sequences
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• A formal theory of inductive inference. Part I

This page was built for publication: An almost machine-independent theory of program-length complexity, sophistication, and induction