Сложност по Колмогоров и изчислителна нередуцируемост

This article examines the relationship between two approaches to the question of why natural regularities admit short descriptions: algorithmic information theory (Kolmogorov complexity and the invariance theorem) and Stephen Wolfram’s concept of computational irreducibility. The first approach provides a measure of description length that is independent of the choice of language up to an additive constant. The second shows that a short rule does not imply a short path to its consequences. Rice’s theorem and Chaitin’s halting probability Ω are discussed as rigorous results on undecidability, together with the testability and limits of Wolfram’s research programme. Concepts are introduced at first use, and the key statements are illustrated with examples.Keywords: Kolmogorov complexity, invariance theorem, cellular automata, computational irreducibility, Rice’s theorem, Chaitin’s halting probability.