Content deleted Content added
IznoRepeat (talk | contribs) m add WP:TEMPLATECAT to remove from template; genfixes |
→History and context: Adding crucial information on recent history and applications |
||
Line 151:
An axiomatic approach to Kolmogorov complexity based on [[Blum axioms]] (Blum 1967) was introduced by Mark Burgin in the paper presented for publication by Andrey Kolmogorov.<ref name=Burgin1982>{{cite journal |last=Burgin |first=M. |year=1982 |title=Generalized Kolmogorov complexity and duality in theory of computations |journal=Notices of the Russian Academy of Sciences |volume=25 |issue=3 |pages=19–23 |url=https://www.mathnet.ru/eng/dan45265}}</ref>
In the late 1990s and early 2000s, methods developed to approximate [[Kolmogorov Complexity]] relied on popular compression algorithms like LZW <ref name="zenil20202">{{cite journal |last1=Zenil |first1=Hector |year=2020 |title=A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions |journal=Entropy |volume=22 |issue=6 |pages=612 |doi=10.3390/e22060612 |doi-access=free |pmid=33286384 |pmc=7517143 }}</ref>, which made difficult or impossible to provide any estimation to short strings until a method based on [[Algorithmic probability]] was introduced <ref>{{cite journal |last1=Delahaye |first1=Jean-Paul |last2=Zenil |first2=Hector |title=Numerical evaluation of algorithmic complexity for short strings: A glance into the innermost structure of randomness |journal=Applied Mathematics and Computation |volume=219 |issue=1 |pages=63–77 |year=2012 |doi=10.1016/j.amc.2011.09.020 |url=https://www.sciencedirect.com/science/article/pii/S0096300311012367 }}</ref> <ref>{{cite journal |last1=Soler-Toscano |first1=Fernando |last2=Zenil |first2=Hector |last3=Delahaye |first3=Jean-Paul |last4=Gauvrit |first4=Nicolas |title=Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines |journal=PLoS ONE |volume=9 |issue=5 |pages=e96223 |year=2014 |doi=10.1371/journal.pone.0096223 |pmid=24787763 |pmc=PMC4013017 |url=https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0096223 }}</ref>, offering the only alternative to compression-based methods. <ref>
Zenil, Hector; Soler Toscano, Fernando; Gauvrit, Nicolas (2022). "Methods and Applications of Algorithmic Complexity: Beyond Statistical Lossless Compression". <i>Emergence, Complexity and Computation</i>. Springer Berlin, Heidelberg. doi:10.1007/978-3-662-64985-5. ISBN 978-3-662-64983-1.
</ref>
==Basic results==
| |||