references.bib

@article{chaitin_algorithmic_1977,
	title = {Algorithmic information theory},
	volume = {21},
	number = {4},
	journal = {IBM journal of research and development},
	author = {Chaitin, G J},
	year = {1977},
	pages = {350--359},
	file = {chaitin-algorithmic-information-theory.pdf:/home/sztal/Zotero/storage/WDKMJQRJ/chaitin-algorithmic-information-theory.pdf:application/pdf}
}

@article{kolmogorov_three_1968,
	title = {Three approaches to the quantitative definition of information},
	volume = {2},
	number = {1-4},
	journal = {International journal of computer mathematics},
	author = {Kolmogorov, A N},
	year = {1968},
	pages = {157--168},
	file = {Kolmogorov65_Three-Approaches-to-Information.pdf:/home/sztal/Zotero/storage/A5WVHFK7/Kolmogorov65_Three-Approaches-to-Information.pdf:application/pdf}
}

@article{chaitin_length_1966,
	title = {On the length of programs for computing finite binary sequences},
	volume = {13},
	number = {4},
	journal = {Journal of the ACM (JACM)},
	author = {Chaitin, G J},
	year = {1966},
	pages = {547--569},
	file = {chaitin-on-the-length-of-binary-sequences.pdf:/home/sztal/Zotero/storage/DIL6DJKD/chaitin-on-the-length-of-binary-sequences.pdf:application/pdf}
}

@book{chaitin_algorithmic_2003,
	edition = {3},
	title = {Algorithmic {Information} {Theory}},
	language = {en},
	publisher = {IBM},
	author = {Chaitin, G J},
	year = {2003},
	file = {Chaitin i Box - ALGORITHMIC INFORMATION THEORY.pdf:/home/sztal/Zotero/storage/MP2WK32I/Chaitin i Box - ALGORITHMIC INFORMATION THEORY.pdf:application/pdf}
}

@article{gauvrit_natural_2014,
	title = {Natural scene statistics mediate the perception of image complexity},
	volume = {22},
	issn = {1350-6285, 1464-0716},
	url = {http://www.tandfonline.com/doi/abs/10.1080/13506285.2014.950365},
	doi = {10.1080/13506285.2014.950365},
	language = {en},
	number = {8},
	urldate = {2019-05-18},
	journal = {Visual Cognition},
	author = {Gauvrit, Nicolas and Soler-Toscano, Fernando and Zenil, Hector},
	month = sep,
	year = {2014},
	pages = {1084--1091},
	file = {Gauvrit i in. - 2014 - Natural scene statistics mediate the perception of.pdf:/home/sztal/Zotero/storage/BK2XMJTW/Gauvrit i in. - 2014 - Natural scene statistics mediate the perception of.pdf:application/pdf}
}

@article{soler-toscano_calculating_2014,
	title = {Calculating {Kolmogorov} {Complexity} from the {Output} {Frequency} {Distributions} of {Small} {Turing} {Machines}},
	volume = {9},
	issn = {1932-6203},
	url = {http://dx.plos.org/10.1371/journal.pone.0096223},
	doi = {10.1371/journal.pone.0096223},
	language = {en},
	number = {5},
	urldate = {2019-05-18},
	journal = {PLoS ONE},
	author = {Soler-Toscano, Fernando and Zenil, Hector and Delahaye, Jean-Paul and Gauvrit, Nicolas},
	month = may,
	year = {2014},
	pages = {e96223},
	file = {Soler-Toscano i in. - 2014 - Calculating Kolmogorov Complexity from the Output .pdf:/home/sztal/Zotero/storage/TJNTBR5P/Soler-Toscano i in. - 2014 - Calculating Kolmogorov Complexity from the Output .pdf:application/pdf}
}

@article{zenil_causal_2019,
	title = {Causal deconvolution by algorithmic generative models},
	volume = {1},
	issn = {2522-5839},
	url = {http://www.nature.com/articles/s42256-018-0005-0},
	doi = {10.1038/s42256-018-0005-0},
	language = {en},
	number = {1},
	urldate = {2019-05-18},
	journal = {Nature Machine Intelligence},
	author = {Zenil, Hector and Kiani, Narsis A. and Zea, Allan A. and Tegnér, Jesper},
	month = jan,
	year = {2019},
	pages = {58--66},
	file = {Zenil i in. - 2019 - Causal deconvolution by algorithmic generative mod.pdf:/home/sztal/Zotero/storage/RZ7U2Z3J/Zenil i in. - 2019 - Causal deconvolution by algorithmic generative mod.pdf:application/pdf}
}

@article{zenil_two-dimensional_2015,
	title = {Two-dimensional {Kolmogorov} complexity and an empirical validation of the {Coding} theorem method by compressibility},
	volume = {1},
	issn = {2376-5992},
	url = {https://peerj.com/articles/cs-23},
	doi = {10.7717/peerj-cs.23},
	abstract = {We propose a measure based upon the fundamental theoretical concept in algorithmic information theory that provides a natural approach to the problem of evaluating n-dimensional complexity by using an n-dimensional deterministic Turing machine. The technique is interesting because it provides a natural algorithmic process for symmetry breaking generating complex n-dimensional structures from perfectly symmetric and fully deterministic computational rules producing a distribution of patterns as described by algorithmic probability. Algorithmic probability also elegantly connects the frequency of occurrence of a pattern with its algorithmic complexity, hence effectively providing estimations to the complexity of the generated patterns. Experiments to validate estimations of algorithmic complexity based on these concepts are presented, showing that the measure is stable in the face of some changes in computational formalism and that results are in agreement with the results obtained using lossless compression algorithms when both methods overlap in their range of applicability. We then use the output frequency of the set of 2-dimensional Turing machines to classify the algorithmic complexity of the space-time evolutions of Elementary Cellular Automata.},
	language = {en},
	urldate = {2019-05-18},
	journal = {PeerJ Computer Science},
	author = {Zenil, Hector and Soler-Toscano, Fernando and Delahaye, Jean-Paul and Gauvrit, Nicolas},
	month = sep,
	year = {2015},
	pages = {e23},
	file = {Zenil i in. - 2015 - Two-dimensional Kolmogorov complexity and an empir.pdf:/home/sztal/Zotero/storage/RHWA2UCD/Zenil i in. - 2015 - Two-dimensional Kolmogorov complexity and an empir.pdf:application/pdf}
}

@article{zenil_algorithmic_2018,
	title = {An {Algorithmic} {Information} {Calculus} for {Causal} {Discovery} and {Reprogramming} {Systems}},
	url = {http://biorxiv.org/lookup/doi/10.1101/185637},
	doi = {10.1101/185637},
	abstract = {We	   introduce	   a	   new	   conceptual	   framework	   and	   a	   model-­‐based	   interventional	   calculus	   to	   steer,	    manipulate,	   and	   reconstruct	   the	   dynamics	   and	   generating	   mechanisms	   of	   non-­‐linear	   dynamical	   systems	    from	    partial	    and	    disordered	    observations	    based	    on	    the	    contributions	    of	    each	    of	    the	    systems,	    by	    exploiting	    first	    principles	    from	    the	    theory	    of	    computability	    and	    algorithmic	    information.	    This	    calculus	    entails	    finding	    and	    applying	    controlled	    interventions	    to	    an	    evolving	    object	    to	    estimate	    how	    its	    algorithmic	    information	    content	    is	    affected	    in	    terms	    of	    positive	    or	    negative	    shifts	    towards	    and	    away	    from	   randomness	   in	   connection	   to	   causation.	   The	   approach	   is	   an	   alternative	   to	   statistical	    approaches	    for	    inferring	    causal	    relationships	    and	    formulating	    theoretical	    expectations	   from	    perturbation	    analysis.	    We	    find	    that	    the	    algorithmic	    information	    landscape	    of	    a	    system	    runs	    parallel	    to	    its	    dynamic	    attractor	    landscape,	   affording	   an	   avenue	   for	   moving	   systems	   on	   one	   plane	   so	   they	   can	   be	   controlled	   on	   the	   other	    plane.	   Based	   on	   these	   methods,	   we	   advance	   tools	   for	   reprogramming	   a	   system	   that	   do	   not	   require	   full	    knowledge	   or	   access	   to	   the	   system’s	   actual	   kinetic	   equations	   or	   to	   probability	   distributions.	    This	   new	    approach	    yields	    a	    suite	    of	    universal	    parameter-­‐free	    algorithms	    of	    wide	    applicability,	    ranging	    from	    the	    discovery	    of	    causality,	    dimension	    reduction,	    feature	    selection,	    model	    generation,	    a	    maximal	    algorithmic-­‐randomness	    principle	    and	    a	    system’s	    (re)programmability	    index.	    We	    apply	    these	    methods	    to	    static	    (e.coli	    Transcription	    Factor	    network)	    and	    to	    evolving	    genetic	    regulatory	    networks	    (differentiating	    naïve	    from	    Th17	    cells,	    and	    the	    CellNet	    database).	    We	    highlight	    their	    ability	    to	    pinpoint	    key	   elements	   (genes)	   related	   to	   cell	   function	   and	   cell	   development,	   conforming	   to	   biological	   knowledge	    from	   experimentally	   validated	   data	   and	   the	   literature,	   and	   demonstrate	   how	   the	   method	   can	   reshape	   a	    system’s	   dynamics	   in	   a	   controlled	   manner	   through	   algorithmic	   causal	   mechanisms.},
	language = {en},
	urldate = {2019-05-18},
	journal = {bioRxiv},
	author = {Zenil, Hector and Kiani, Narsis A. and Marabita, Francesco and Deng, Yue and Elias, Szabolcs and Schmidt, Angelika and Ball, Gordon and Tegner, Jesper},
	month = mar,
	year = {2018},
	file = {Zenil i in. - 2018 - An Algorithmic Information Calculus for Causal Dis.pdf:/home/sztal/Zotero/storage/8V4H8NLS/Zenil i in. - 2018 - An Algorithmic Information Calculus for Causal Dis.pdf:application/pdf}
}

@article{gauvrit_algorithmic_2016,
	title = {Algorithmic complexity for psychology: a user-friendly implementation of the coding theorem method},
	volume = {48},
	issn = {1554-3528},
	shorttitle = {Algorithmic complexity for psychology},
	url = {http://link.springer.com/10.3758/s13428-015-0574-3},
	doi = {10.3758/s13428-015-0574-3},
	abstract = {Kolmogorov-Chaitin complexity has long been believed to be impossible to approximate when it comes to short sequences (e.g. of length 5-50). However, with the newly developed coding theorem method the complexity of strings of length 2-11 can now be numerically estimated. We present the theoretical basis of algorithmic complexity for short strings (ACSS) and describe an R-package providing functions based on ACSS that will cover psychologists’ needs and improve upon previous methods in three ways: (1) ACSS is now available not only for binary strings, but for strings based on up to 9 different symbols, (2) ACSS no longer requires time-consuming computing, and (3) a new approach based on ACSS gives access to an estimation of the complexity of strings of any length. Finally, three illustrative examples show how these tools can be applied to psychology.},
	language = {en},
	number = {1},
	urldate = {2019-05-18},
	journal = {Behavior Research Methods},
	author = {Gauvrit, Nicolas and Singmann, Henrik and Soler-Toscano, Fernando and Zenil, Hector},
	month = mar,
	year = {2016},
	pages = {314--329},
	file = {Gauvrit i in. - 2016 - Algorithmic complexity for psychology a user-frie.pdf:/home/sztal/Zotero/storage/XMVPEXFM/Gauvrit i in. - 2016 - Algorithmic complexity for psychology a user-frie.pdf:application/pdf}
}

@article{zenil_decomposition_2018,
	title = {A {Decomposition} {Method} for {Global} {Evaluation} of {Shannon} {Entropy} and {Local} {Estimations} of {Algorithmic} {Complexity}},
	volume = {20},
	issn = {1099-4300},
	url = {http://www.mdpi.com/1099-4300/20/8/605},
	doi = {10.3390/e20080605},
	abstract = {We investigate the properties of a Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic complexity based on Solomonoff–Levin’s theory of algorithmic probability providing a closer connection to algorithmic complexity than previous attempts based on statistical regularities such as popular lossless compression schemes. The strategy behind BDM is to find small computer programs that produce the components of a larger, decomposed object. The set of short computer programs can then be artfully arranged in sequence so as to produce the original object. We show that the method provides efficient estimations of algorithmic complexity but that it performs like Shannon entropy when it loses accuracy. We estimate errors and study the behaviour of BDM for different boundary conditions, all of which are compared and assessed in detail. The measure may be adapted for use with more multi-dimensional objects than strings, objects such as arrays and tensors. To test the measure we demonstrate the power of CTM on low algorithmic-randomness objects that are assigned maximal entropy (e.g., π) but whose numerical approximations are closer to the theoretical low algorithmic-randomness expectation. We also test the measure on larger objects including dual, isomorphic and cospectral graphs for which we know that algorithmic randomness is low. We also release implementations of the methods in most major programming languages—Wolfram Language (Mathematica), Matlab, R, Perl, Python, Pascal, C++, and Haskell—and an online algorithmic complexity calculator.},
	language = {en},
	number = {8},
	urldate = {2019-05-18},
	journal = {Entropy},
	author = {Zenil, Hector and Hernández-Orozco, Santiago and Kiani, Narsis and Soler-Toscano, Fernando and Rueda-Toicen, Antonio and Tegnér, Jesper},
	month = aug,
	year = {2018},
	pages = {605},
	file = {Zenil i in. - 2018 - A Decomposition Method for Global Evaluation of Sh.pdf:/home/sztal/Zotero/storage/7PQCYKI3/Zenil i in. - 2018 - A Decomposition Method for Global Evaluation of Sh.pdf:application/pdf}
}

@article{chaitin_two_2003,
	title = {Two philosophical applications of algorithmic information theory},
	url = {http://arxiv.org/abs/math/0302333},
	abstract = {Two philosophical applications of the concept of program-size complexity are discussed. First, we consider the light program-size complexity sheds on whether mathematics is invented or discovered, i.e., is empirical or is a priori. Second, we propose that the notion of algorithmic independence sheds light on the question of being and how the world of our experience can be partitioned into separate entities.},
	language = {en},
	urldate = {2019-05-19},
	journal = {arXiv:math/0302333},
	author = {Chaitin, G. J.},
	month = feb,
	year = {2003},
	note = {arXiv: math/0302333},
	keywords = {68Q30, Mathematics - History and Overview},
	file = {Chaitin - 2003 - Two philosophical applications of algorithmic info.pdf:/home/sztal/Zotero/storage/XPRZ7H98/Chaitin - 2003 - Two philosophical applications of algorithmic info.pdf:application/pdf}
}

@article{hudetz_propofol_2016,
	title = {Propofol anesthesia reduces {Lempel}-{Ziv} complexity of spontaneous brain activity in rats},
	volume = {628},
	issn = {03043940},
	url = {https://linkinghub.elsevier.com/retrieve/pii/S0304394016304268},
	doi = {10.1016/j.neulet.2016.06.017},
	abstract = {Consciousness is thought to scale with brain complexity, and it may be diminished in anesthesia. LempelZiv complexity (LZC) of field potentials has been shown to be a promising measure of the level of consciousness in anesthetized human subjects, neurological patients, and across the sleep-wake states in rats. Whether this relationship holds for intrinsic networks obtained by functional brain imaging has not been tested. To fill this gap of knowledge, we estimated LZC from large-scale dynamic analysis of functional magnetic resonance images (fMRI) in conscious sedated and unconscious anesthetized rats. Blood oxygen dependent (BOLD) signals were obtained from 30-min whole-brain resting-state scans while the anesthetic propofol was infused intravenously at constant infusion rates of 20 mg/kg/h (conscious sedated) and 40 mg/kg/h (unconscious). Dynamic brain networks were defined at voxel level by sliding window analysis of regional homogeneity (ReHo) of the BOLD signal. From scans performed at low to high propofol dose, the LZC was significantly reduced by 110\%. The results suggest that the difference in LZC between conscious sedated and anesthetized unconscious subjects is conserved in rats and this effect is detectable in large-scale brain network obtained from fMRI.},
	language = {en},
	urldate = {2019-09-05},
	journal = {Neuroscience Letters},
	author = {Hudetz, Anthony G. and Liu, Xiping and Pillay, Siveshigan and Boly, Melanie and Tononi, Giulio},
	month = aug,
	year = {2016},
	pages = {132--135},
	file = {Hudetz i in. - 2016 - Propofol anesthesia reduces Lempel-Ziv complexity .pdf:/home/sztal/Zotero/storage/CF5WXAIF/Hudetz i in. - 2016 - Propofol anesthesia reduces Lempel-Ziv complexity .pdf:application/pdf}
}

@article{morzy_measuring_2017,
	title = {On {Measuring} the {Complexity} of {Networks}: {Kolmogorov} {Complexity} versus {Entropy}},
	volume = {2017},
	issn = {1076-2787, 1099-0526},
	shorttitle = {On {Measuring} the {Complexity} of {Networks}},
	url = {https://www.hindawi.com/journals/complexity/2017/3250301/},
	doi = {10.1155/2017/3250301},
	language = {en},
	urldate = {2019-09-18},
	journal = {Complexity},
	author = {Morzy, Mikołaj and Kajdanowicz, Tomasz and Kazienko, Przemysław},
	year = {2017},
	keywords = {complex networks, algorithmic information, kolmogorov complexity},
	pages = {1--12},
	file = {Morzy i in. - 2017 - On Measuring the Complexity of Networks Kolmogoro.pdf:/home/sztal/Zotero/storage/JEWZ5RI6/Morzy i in. - 2017 - On Measuring the Complexity of Networks Kolmogoro.pdf:application/pdf}
}

@article{hernndez_ml_2021,
  doi = {10.3389/frai.2020.567356},
  url = {https://doi.org/10.3389/frai.2020.567356},
  year = {2021},
  month = jan,
  publisher = {Frontiers Media {SA}},
  volume = {3},
  author = {Santiago Hern{\'{a}}ndez-Orozco and Hector Zenil and J\"{u}rgen Riedel and Adam Uccello and Narsis A. Kiani and Jesper Tegn{\'{e}}r},
  title = {Algorithmic Probability-Guided Machine Learning on Non-Differentiable Spaces},
  journal = {Frontiers in Artificial Intelligence}
}