{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T05:02:11Z","timestamp":1783141331408,"version":"3.54.6"},"reference-count":47,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2018,8,15]],"date-time":"2018-08-15T00:00:00Z","timestamp":1534291200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"publisher","award":["2015-05299"],"award-info":[{"award-number":["2015-05299"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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\u2013Levin\u2019s 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.,    \u03c0   ) 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\u2014Wolfram Language (Mathematica), Matlab, R, Perl, Python, Pascal, C++, and Haskell\u2014and an online algorithmic complexity calculator.<\/jats:p>","DOI":"10.3390\/e20080605","type":"journal-article","created":{"date-parts":[[2018,8,15]],"date-time":"2018-08-15T10:40:07Z","timestamp":1534329607000},"page":"605","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":87,"title":["A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity"],"prefix":"10.3390","volume":"20","author":[{"given":"Hector","family":"Zenil","sequence":"first","affiliation":[{"name":"Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, Karolinska Institute and SciLifeLab, SE-171 77 Stockholm, Sweden"},{"name":"Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France"},{"name":"Department of Computer Science, University of Oxford, Oxford OX1 3QD, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Santiago","family":"Hern\u00e1ndez-Orozco","sequence":"additional","affiliation":[{"name":"Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, Karolinska Institute and SciLifeLab, SE-171 77 Stockholm, Sweden"},{"name":"Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France"},{"name":"Posgrado en Ciencia e Ingenier\u00eda de la Computaci\u00f3n, Universidad Nacional Aut\u00f3noma de M\u00e9xico (UNAM), Mexico City 04510, Mexico"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0949-046X","authenticated-orcid":false,"given":"Narsis A.","family":"Kiani","sequence":"additional","affiliation":[{"name":"Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, Karolinska Institute and SciLifeLab, SE-171 77 Stockholm, Sweden"},{"name":"Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fernando","family":"Soler-Toscano","sequence":"additional","affiliation":[{"name":"Grupo de L\u00f3gica, Lenguaje e Informaci\u00f3n, Universidad de Sevilla, 41004 Seville, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6812-7337","authenticated-orcid":false,"given":"Antonio","family":"Rueda-Toicen","sequence":"additional","affiliation":[{"name":"Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, Karolinska Institute and SciLifeLab, SE-171 77 Stockholm, Sweden"},{"name":"Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France"},{"name":"Instituto Nacional de Bioingenier\u00eda, Universidad Central de Venezuela, Caracas 1051, Venezuela"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jesper","family":"Tegn\u00e9r","sequence":"additional","affiliation":[{"name":"Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, SciLifeLab and Karolinska Institute, Stockholm SE-171 77, Sweden"},{"name":"Biological and Environmental Sciences and Engineering Division, Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2018,8,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"012308","DOI":"10.1103\/PhysRevE.96.012308","article-title":"Low-algorithmic-complexity entropy-deceiving graphs","volume":"96","author":"Zenil","year":"2017","journal-title":"Phys. Rev. E"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1145\/321784.321794","article-title":"An Example of Information and Computation Trade-Off","volume":"20","author":"Daley","year":"1973","journal-title":"J. ACM"},{"key":"ref_3","first-page":"265","article-title":"Universal sequential search problems","volume":"9","author":"Levin","year":"1973","journal-title":"Probl. Inf. Transm."},{"key":"ref_4","unstructured":"Kivinen, J., and Sloan, R.H. (2002, January 8\u201310). The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions. Proceedings of the 15th Annual Conference on Computational Learning Theory (COLT 2002), Sydney, Australia."},{"key":"ref_5","unstructured":"Li, M., and Vit\u00e1nyi, P. (2009). An Introduction to Kolmogorov Complexity and Its Applications, Springer. [3rd. ed.]."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1523","DOI":"10.1109\/TIT.2005.844059","article-title":"Clustering by compression","volume":"51","author":"Cilibrasi","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Zenil, H., Badillo, L., Hern\u00e1ndez-Orozco, S., and Hern\u00e1ndez-Quiroz, F. (2018). Coding-theorem Like Behaviour and Emergence of the Universal Distribution from Resource-bounded Algorithmic Probability. Int. J. Parallel Emerg. Distrib. Syst., 1\u201320.","DOI":"10.1080\/17445760.2018.1448932"},{"key":"ref_8","unstructured":"Ott, M., Pietsch, W., and Wernecke, J. (2017). Algorithmic Data Analytics, Small Data Matters and Correlation versus Causation. Berechenbarkeit der Welt? Philosophie und Wissenschaft im Zeitalter von Big Data (Computability of the World? Philosophy and Science in the Age of Big Data), Springer."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"e23","DOI":"10.7717\/peerj-cs.23","article-title":"Two-dimensional Kolmogorov complexity and an empirical validation of the Coding Theorem Method by compressibility","volume":"1","author":"Zenil","year":"2015","journal-title":"PeerJ Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1084","DOI":"10.1080\/13506285.2014.950365","article-title":"Natural scene statistics mediate the perception of image complexity","volume":"22","author":"Gauvrit","year":"2014","journal-title":"Vis. Cognit."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"314","DOI":"10.3758\/s13428-015-0574-3","article-title":"Algorithmic complexity for psychology: A user-friendly implementation of the coding theorem method","volume":"48","author":"Gauvrit","year":"2016","journal-title":"Behav. Res. Methods"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/j.cognition.2014.11.038","article-title":"Structure emerges faster during cultural transmission in children than in adults","volume":"136","author":"Kempe","year":"2015","journal-title":"Cognition"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Emmert-Streib, F., and Dehmer, M. (2012). Exploring statistical and population aspects of network complexity. PLoS ONE, 7.","DOI":"10.1371\/journal.pone.0034523"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1080\/01969720802435925","article-title":"A novel method for measuring the structural information content of networks","volume":"39","author":"Dehmer","year":"2008","journal-title":"Cybern. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Dehmer, M.M., Barbarini, N.N., Varmuza, K.K., and Graber, A.A. (2010). Novel topological descriptors for analyzing biological networks. BMC Struct. Biol., 10.","DOI":"10.1186\/1472-6807-10-18"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"559","DOI":"10.3390\/e14030559","article-title":"Entropy and the complexity of graphs revisited","volume":"14","author":"Mowshowitz","year":"2012","journal-title":"Entropy"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Holzinger, A., Ofner, B., Stocker, C., Valdez, A.C., Schaar, A.K., Ziefle, M., and Dehmer, M. (2013). On graph entropy measures for knowledge discovery from publication network data. International Conference on Availability, Reliability, and Security, Springer.","DOI":"10.1007\/978-3-642-40511-2_25"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/j.physa.2014.02.060","article-title":"Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks","volume":"404","author":"Zenil","year":"2014","journal-title":"Physica A"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.semcdb.2016.01.011","article-title":"Methods of information theory and algorithmic complexity for network biology","volume":"Volume 51","author":"Zenil","year":"2016","journal-title":"Seminars in Cell & Developmental Biology"},{"key":"ref_20","first-page":"30","article-title":"Laws of information conservation (nongrowth) and aspects of the foundation of probability theory","volume":"10","author":"Levin","year":"1974","journal-title":"Probl. Pereda. Inf."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","article-title":"On the length of programs for computing finite binary sequences","volume":"13","author":"Chaitin","year":"1966","journal-title":"J. ACM"},{"key":"ref_22","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Probl. Inf. Transm."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"5668","DOI":"10.1016\/j.tcs.2011.06.021","article-title":"Finite state complexity","volume":"412","author":"Calude","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Hirschfeldt, D.R. (2010). Algorithmic Randomness and Complexity, Springer.","DOI":"10.1007\/978-0-387-68441-3"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","article-title":"The definition of random sequences","volume":"9","year":"1966","journal-title":"Inf. Control"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(64)90223-2","article-title":"A formal theory of inductive inference. Part I","volume":"7","author":"Solomonoff","year":"1964","journal-title":"Inf. Control"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Calude, C.S. (2002). Information and Randomness: An Algorithmic Perspective, Springer.","DOI":"10.1007\/978-3-662-04978-5"},{"key":"ref_28","unstructured":"Cover, T.M., and Thomas, J.A. (2012). Elements of Information Theory, John Wiley & Sons."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF03024407","article-title":"The Miraculous Universal Distribution","volume":"19","author":"Kirchherr","year":"1997","journal-title":"Math. Intell."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1109\/TIT.1978.1055913","article-title":"Complexity\u2013Based Induction Systems: Comparisons and Convergence Theorems","volume":"24","author":"Solomonoff","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_31","unstructured":"Kanal, L.N., and Lemmer, J.F. (1986). The Application of Algorithmic Probability to Problems in Artificial Intelligence. Uncertainty in Artificial Intelligence, Elsevier."},{"key":"ref_32","unstructured":"Solomonoff, R.J. (1989, January 26\u201327). A System for Incremental Learning Based on Algorithmic Probability. Proceedings of the Sixth Israeli Conference on Artificial Intelligence, Computer Vision and Pattern Recognition, Tel Aviv, Israel."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Soler-Toscano, F., Zenil, H., Delahaye, J.P., and Gauvrit, N. (2014). Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines. PloS ONE, 9.","DOI":"10.1371\/journal.pone.0096223"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.amc.2011.10.006","article-title":"Numerical Evaluation of the Complexity of Short Strings: A Glance Into the Innermost Structure of Algorithmic Randomness","volume":"219","author":"Delahaye","year":"2012","journal-title":"Appl. Math. Comput."},{"key":"ref_36","unstructured":"Zenil, H. (2013). Une Approche Exp\u00e9rimentalea la Th\u00e9orie Algorithmique de la Complexit\u00e9. [Ph.D. Thesis, Universit\u00e9 de Paris]. (In French)."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/j.aam.2007.01.001","article-title":"Most programs stop quickly or never halt","volume":"40","author":"Calude","year":"2008","journal-title":"Adv. Appl. Math."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1002\/j.1538-7305.1962.tb00480.x","article-title":"On non-computable functions","volume":"41","author":"Rado","year":"1962","journal-title":"Bell Syst. Tech. J."},{"key":"ref_39","unstructured":"Dinneen, M.J., Khousainov, B., and Nies, A. (2012). From Computer Runtimes to the Length of Proofs: With an Algorithmic Probabilistic Application to Waiting Times in Automatic Theorem Proving. Computation, Physics and Beyond International Workshop on Theoretical Computer Science, Springer."},{"key":"ref_40","first-page":"647","article-title":"The determination of the value of Rado\u2019s noncomputable function \u03a3(k) for four-state Turing machines","volume":"40","author":"Brady","year":"1983","journal-title":"Math. Comput."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"125","DOI":"10.3233\/COM-13019","article-title":"Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures","volume":"2","author":"Zenil","year":"2013","journal-title":"Computability"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/0167-2789(86)90237-X","article-title":"Studying artificial life with cellular automata","volume":"22","author":"Langton","year":"1986","journal-title":"Physica D"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1215\/S0012-7094-44-01101-4","article-title":"Unending Chess, Symbolic Dynamics, and a Problem in Semigroups","volume":"11","author":"Morse","year":"1944","journal-title":"Duke Math. J."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1090\/S0025-5718-97-00856-9","article-title":"On the Rapid Computation of Various Polylogarithmic Constants","volume":"66","author":"Bailey","year":"1997","journal-title":"Math. Comput."},{"key":"ref_45","unstructured":"Gauvrit, N., Singmann, H., Soler-Toscano, F., and Zenil, H. (2018, June 13). Acss: Algorithmic Complexity for Short Strings, Package at the Comprehensive R Archive Network. Available online: https:\/\/cran.r-project.org\/web\/packages\/acss\/."},{"key":"ref_46","unstructured":"Rueda-Toicen, A., and Singmann, H. (2018, June 13). The Online Algorithmic Complexity Calculator, R Shiny Code Repository. Available online: https:\/\/github.com\/andandandand\/OACC."},{"key":"ref_47","unstructured":"Soler-Toscano, F., and Zenil, H. (2018, June 13). Kolmogorov Complexity of 3 \u00d7 3 and 4 \u00d7 4 Squares, on the Wolfram Demonstrations Project. Available online: http:\/\/demonstrations.wolfram.com\/KolmogorovComplexityOf33And44Squares\/."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/8\/605\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:18:51Z","timestamp":1760195931000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/8\/605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,15]]},"references-count":47,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2018,8]]}},"alternative-id":["e20080605"],"URL":"https:\/\/doi.org\/10.3390\/e20080605","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,15]]}}}