(One intermediate revision by one other user not shown)
Line 341:
This definition can be extended to define a notion of randomness for ''infinite'' sequences from a finite alphabet. These [[algorithmically random sequence]]s can be defined in three equivalent ways. One way uses an effective analogue of [[measure theory]]; another uses effective [[Martingale (probability theory)|martingales]]. The third way defines an infinite sequence to be random if the prefix-free Kolmogorov complexity of its initial segments grows quickly enough — there must be a constant ''c'' such that the complexity of an initial segment of length ''n'' is always at least ''n''−''c''. This definition, unlike the definition of randomness for a finite string, is not affected by which universal machine is used to define prefix-free Kolmogorov complexity.<ref>{{cite journal |doi=10.1016/s0019-9958(66)80018-9 |title=The definition of random sequences |journal=Information and Control |volume=9 |issue=6 |pages=602–619 |year=1966 |last=Martin-Löf |first=Per |doi-access=free }}</ref>
== Applications ==
Kolmogorov complexity has found increasing use in the analysis of real-world systems, particularly for uncovering structure and [[causality]] in data-rich but poorly understood domains.<ref>{{cite journal |last1=Zenil |first1=Hector |last2=Kiani |first2=Narsis A. |last3=Zea |first3=Allan A. |last4=Tegnér |first4=Jesper |title=Causal deconvolution by algorithmic generative models |journal=Nature Machine Intelligence |volume=1 |issue=1 |year=2019 |pages=58-66 |doi=10.1038/s42256-018-0005-0 }}</ref> One notable example is the conceptual framework introduced by Zenil et al. (2019) for extracting generative rules from complex [[Dynamical system|dynamical systems]]. Based on [[Algorithmic information theory]] (AIT) and an associated algorithmic information calculus (AIC),<ref>{{cite journal |last1=Zenil |first1=Hector |last2=Kiani |first2=N. A. |last3=Marabita |first3=F. |last4=Deng |first4=Y. |last5=Elias |first5=S. |last6=Schmidt |first6=A. |last7=Ball |first7=G. |last8=Tegnér |first8=J. |title=An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems |journal=Science |year=2019 |doi=10.1016/j.sci.2019.30270-6 }}</ref> the method—called Algorithmic Information Dynamics (AID)<ref>{{cite journal | last=Zenil | first=Hector | title=Algorithmic Information Dynamics | journal=Scholarpedia | date=25 July 2020 | volume=15 | issue=7 | doi=10.4249/scholarpedia.53143 | doi-access=free | bibcode=2020SchpJ..1553143Z | hdl=10754/666314 | hdl-access=free }}</ref>—was used to reconstruct phase spaces and identify causal mechanisms of discrete systems (including cellular automata). Their approach applied perturbation analysis to quantify the algorithmic complexity of system components, enabling reconstruction of the system’s generative rules without requiring explicit kinetic equations. This method provided insights into the causal structure of systems and their reprogrammability toward desired states.<ref> {{cite book | last1=Zenil | first1=Hector | last2=Kiani | first2=Narsis A. | last3=Tegner | first3=Jesper | title=Algorithmic Information Dynamics: A Computational Approach to Causality with Applications to Living Systems | publisher=Cambridge University Press | year=2023 | doi=10.1017/9781108596619 | isbn=978-1-108-59661-9 | url=https://doi.org/10.1017/9781108596619}}</ref>
==Relation to entropy==
Line 387 ⟶ 384:
==Implications in biology==
In the context of biology to argue that the symmetries and modular arrangements observed in multiple species emerge from the tendency of evolution to prefer minimal Kolmogorov complexity.<ref>{{Cite journal |last1=Johnston |first1=Iain G. |last2=Dingle |first2=Kamaludin |last3=Greenbury |first3=Sam F. |last4=Camargo |first4=Chico Q. |last5=Doye |first5=Jonathan P. K. |last6=Ahnert |first6=Sebastian E. |last7=Louis |first7=Ard A. |date=2022-03-15 |title=Symmetry and simplicity spontaneously emerge from the algorithmic nature of evolution |journal=Proceedings of the National Academy of Sciences |volume=119 |issue=11 |pages=e2113883119 |doi=10.1073/pnas.2113883119 |doi-access=free |pmc=8931234 |pmid=35275794|bibcode=2022PNAS..11913883J }}</ref> Considering the genome as a program that must solve a task or implement a series of functions, shorter programs would be preferred on the basis that they are easier to find by the mechanisms of evolution.<ref>{{Cite journal |last=Alon |first=Uri |date=Mar 2007 |title=Simplicity in biology |url=https://www.nature.com/articles/446497a |journal=Nature |language=en |volume=446 |issue=7135 |pages=497 |doi=10.1038/446497a |pmid=17392770 |bibcode=2007Natur.446..497A |issn=1476-4687}}</ref> An example of this approach is the eight-fold symmetry of the compass circuit that is found across insect species, which correspond to the circuit that is both functional and requires the minimum Kolmogorov complexity to be generated from self-replicating units.<ref>{{Cite journal |last1=Vilimelis Aceituno |first1=Pau |last2=Dall'Osto |first2=Dominic |last3=Pisokas |first3=Ioannis |date=2024-05-30 |editor-last=Colgin |editor-first=Laura L |editor2-last=Vafidis |editor2-first=Pantelis |title=Theoretical principles explain the structure of the insect head direction circuit |url=https://elifesciences.org/articles/91533 |journal=eLife |volume=13 |pages=e91533 |doi=10.7554/eLife.91533 |doi-access=free |pmid=38814703 |pmc=11139481 |issn=2050-084X}}</ref>
More broadly, the principles of Kolmogorov complexity have been extended beyond biology into computational modeling of natural systems. Hernández-Orozco et al. (2021) proposed an algorithmic [[loss function]] grounded in [[Algorithmic information theory]] to quantify the mismatch between predicted and observed system behavior. By integrating this approach with [[Machine learning]], they developed a framework for learning generative rules in non-differentiable and complex environments—bridging the gap between discrete algorithmic representations and continuous optimization.<ref>{{cite journal |last1=Zenil |first1=Hector |last2=Kiani |first2=Narsis A. |last3=Zea |first3=Allan A. |last4=Tegnér |first4=Jesper |title=Causal deconvolution by algorithmic generative models |journal=Nature Machine Intelligence |volume=1 |issue=1 |year=2019 |pages=58-66 |doi=10.1038/s42256-018-0005-0 }}</ref> This framework offers potential for uncovering underlying rules in both biological and artificial systems where structure and function co-evolve.<ref> {{cite book | last1=Zenil | first1=Hector | last2=Kiani | first2=Narsis A. | last3=Tegner | first3=Jesper | title=Algorithmic Information Dynamics: A Computational Approach to Causality with Applications to Living Systems | publisher=Cambridge University Press | year=2023 | doi=10.1017/9781108596619 | isbn=978-1-108-59661-9 | url=https://doi.org/10.1017/9781108596619}}</ref>
