{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:34:03Z","timestamp":1760402043024,"version":"build-2065373602"},"reference-count":60,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T00:00:00Z","timestamp":1579132800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["SFRH\/BD\/141851\/2018"],"award-info":[{"award-number":["SFRH\/BD\/141851\/2018"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Sources that generate symbolic sequences with algorithmic nature may differ in statistical complexity because they create structures that follow algorithmic schemes, rather than generating symbols from a probabilistic function assuming independence. In the case of Turing machines, this means that machines with the same algorithmic complexity can create tapes with different statistical complexity. In this paper, we use a compression-based approach to measure global and local statistical complexity of specific Turing machine tapes with the same number of states and alphabet. Both measures are estimated using the best-order Markov model. For the global measure, we use the Normalized Compression (NC), while, for the local measures, we define and use normal and dynamic complexity profiles to quantify and localize lower and higher regions of statistical complexity. We assessed the validity of our methodology on synthetic and real genomic data showing that it is tolerant to increasing rates of editions and block permutations. Regarding the analysis of the tapes, we localize patterns of higher statistical complexity in two regions, for a different number of machine states. We show that these patterns are generated by a decrease of the tape\u2019s amplitude, given the setting of small rule cycles. Additionally, we performed a comparison with a measure that uses both algorithmic and statistical approaches (BDM) for analysis of the tapes. Naturally, BDM is efficient given the algorithmic nature of the tapes. However, for a higher number of states, BDM is progressively approximated by our methodology. Finally, we provide a simple algorithm to increase the statistical complexity of a Turing machine tape while retaining the same algorithmic complexity. We supply a publicly available implementation of the algorithm in C++ language under the GPLv3 license. All results can be reproduced in full with scripts provided at the repository.<\/jats:p>","DOI":"10.3390\/e22010105","type":"journal-article","created":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T04:14:41Z","timestamp":1579234481000},"page":"105","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Statistical Complexity Analysis of Turing Machine tapes with Fixed Algorithmic Complexity Using the Best-Order Markov Model"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6331-6091","authenticated-orcid":false,"given":"Jorge M.","family":"Silva","sequence":"first","affiliation":[{"name":"Institute of Electronics and Informatics Engineering of Aveiro, University of Aveiro, 3810-193 Aveiro, Portugal"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4397-8792","authenticated-orcid":false,"given":"Eduardo","family":"Pinho","sequence":"additional","affiliation":[{"name":"Institute of Electronics and Informatics Engineering of Aveiro, University of Aveiro, 3810-193 Aveiro, Portugal"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1941-3983","authenticated-orcid":false,"given":"S\u00e9rgio","family":"Matos","sequence":"additional","affiliation":[{"name":"Institute of Electronics and Informatics Engineering of Aveiro, University of Aveiro, 3810-193 Aveiro, Portugal"},{"name":"Department of Electronics, Telecommunications and Informatics, University of Aveiro, 3810-193 Aveiro, Portugal"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1176-552X","authenticated-orcid":false,"given":"Diogo","family":"Pratas","sequence":"additional","affiliation":[{"name":"Institute of Electronics and Informatics Engineering of Aveiro, University of Aveiro, 3810-193 Aveiro, Portugal"},{"name":"Department of Electronics, Telecommunications and Informatics, University of Aveiro, 3810-193 Aveiro, Portugal"},{"name":"Department of Virology, University of Helsinki, 00100 Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,1,16]]},"reference":[{"key":"ref_1","unstructured":"Sacks, D. (2004). Letter Perfect: The Marvelous History of Our Alphabet from A to Z, Broadway Books."},{"key":"ref_2","unstructured":"Drucker, J. (1995). The Alphabetic Labyrinth: The Letters in History and Imagination, Thames and Hudson."},{"key":"ref_3","unstructured":"Copeland, B.J. (2020, January 13). The Modern History of Computing. Available online: https:\/\/plato.stanford.edu\/entries\/computing-history\/."},{"key":"ref_4","first-page":"271","article-title":"General principles of the design of all-purpose computing machines","volume":"195","author":"Newman","year":"1948","journal-title":"Proc. R. Soc. Lond."},{"key":"ref_5","first-page":"230","article-title":"On Computable Numbers, with an Application to the Entscheidungsproblem","volume":"s2-42","author":"Turing","year":"1936","journal-title":"Proc. R. Soc. Lond."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Cooper, S.B., L\u00f6we, B., and Torenvliet, L. (2005). The Church-Turing Thesis: Breaking the Myth, Springer. New Computational Paradigms.","DOI":"10.1007\/b136981"},{"key":"ref_7","unstructured":"Minsky, M.L. (1967). Computation: Finite and Infinite Machines, Prentice-Hall, Inc."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Boolos, G.S., Burgess, J.P., and Jeffrey, R.C. (2002). Computability and Logic, Cambridge University Press.","DOI":"10.1017\/CBO9781139164931"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1002\/j.1538-7305.1924.tb01361.x","article-title":"Certain Factors Affecting Telegraph Speed","volume":"3","author":"Nyquist","year":"1924","journal-title":"Bell Syst. Tech. J."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1002\/j.1538-7305.1928.tb01236.x","article-title":"Transmission of Information","volume":"7","author":"Hartley","year":"1928","journal-title":"Bell Syst. Tech. J."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A Mathematical Theory of Communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"ref_12","unstructured":"Anderson, J.B., and Johnnesson, R. (2006). Understanding Information Transmission, John Wiley & Sons."},{"key":"ref_13","unstructured":"Solomonoff, R.J. (1960). A Preliminary Report on a General Theory of Inductive Inference, United States Air Force, Office of Scientific Research."},{"key":"ref_14","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_15","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/S0019-9958(64)90131-7","article-title":"A formal theory of inductive inference. Part II","volume":"7","author":"Solomonoff","year":"1964","journal-title":"Inf. Control"},{"key":"ref_16","first-page":"1","article-title":"Three Approaches to the Quantitative Definition of Information","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Prob. Inf. Transm."},{"key":"ref_17","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 (JACM)"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/321892.321894","article-title":"A theory of program size formally identical to information theory","volume":"22","author":"Chaitin","year":"1975","journal-title":"J. ACM (JACM)"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Bennett, C.H. (2007). On random and hard-to-describe numbers. Randomness Complex. Leibniz Chaitin, 3\u201312.","DOI":"10.1142\/9789812770837_0001"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1109\/TIT.1970.1054390","article-title":"On the difficulty of computations","volume":"16","author":"Chaitin","year":"1970","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0196-8858(87)90010-8","article-title":"Incompleteness theorems for random reals","volume":"8","author":"Chaitin","year":"1987","journal-title":"Adv. Appl. Math."},{"key":"ref_22","unstructured":"Chaitin, G.J., Arslanov, A., and Calude, C. (1995). Program-Size Complexity Computes the Halting Problem, Department of Computer Science, The University of Auckland. Technical Report."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1006\/jcss.1999.1677","article-title":"Inequalities for Shannon Entropy and Kolmogorov Complexity","volume":"60","author":"Hammer","year":"2000","journal-title":"J. Comput. Syst. Sci. Int."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1111\/jep.12068","article-title":"Entropy and compression: Two measures of complexity","volume":"19","author":"Henriques","year":"2013","journal-title":"J. Eval. Clin. Pract."},{"key":"ref_25","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":"Problemy Peredachi Informatsii"},{"key":"ref_26","first-page":"1265","article-title":"On the symmetry of algorithmic information","volume":"218","year":"1974","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/321386.321395","article-title":"A machine-independent theory of the complexity of recursive functions","volume":"14","author":"Blum","year":"1967","journal-title":"J. ACM (JACM)"},{"key":"ref_28","first-page":"19","article-title":"Generalized Kolmogorov complexity and duality in theory of computations","volume":"25","author":"Burgin","year":"1982","journal-title":"Not. Russ. Acad. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Li, M., and Vit\u00e1nyi, P. (2008). An Introduction to Kolmogorov Complexity and Its Applications, Springer.","DOI":"10.1007\/978-0-387-49820-1"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1093\/comjnl\/11.2.185","article-title":"An information measure for classification","volume":"11","author":"Wallace","year":"1968","journal-title":"Comput. J."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1109\/18.825807","article-title":"Minimum description length induction, Bayesianism, and Kolmogorov complexity","volume":"46","author":"Vitanyi","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1016\/0005-1098(78)90005-5","article-title":"Modeling by shortest data description","volume":"14","author":"Rissanen","year":"1978","journal-title":"Automatica"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Bennett, C.H. (1995). Logical Depth and Physical Complexity. The Universal Turing Machine, a Half-Century Survey, Oxford University Press.","DOI":"10.1007\/978-3-7091-6597-3_8"},{"key":"ref_34","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_35","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/BF01203155","article-title":"Grundlagen der wahrscheinlichkeitsrechnung","volume":"5","year":"1919","journal-title":"Math. Z."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/BF01694181","article-title":"A unified approach to the definition of random sequences","volume":"5","author":"Schnorr","year":"1971","journal-title":"Math. Syst. Theory"},{"key":"ref_37","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_38","doi-asserted-by":"crossref","unstructured":"Zenil, H., Hern\u00e1ndez-Orozco, S., Kiani, N.A., Soler-Toscano, F., Rueda-Toicen, A., and Tegn\u00e9r, J. (2018). A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity. Entropy, 20.","DOI":"10.3390\/e20080605"},{"key":"ref_39","first-page":"336","article-title":"A safe approximation for Kolmogorov complexity","volume":"8776","author":"Bloem","year":"2014","journal-title":"Algorithmic Learn. Theory"},{"key":"ref_40","first-page":"1","article-title":"Coding-theorem like behaviour and emergence of the universal distribution from resource-bounded algorithmic probability","volume":"34","author":"Zenil","year":"2018","journal-title":"Int. J. Parallel Emerg. Distrib. Syst."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Pratas, D., Pinho, A.J., and Ferreira, P.J.S.G. (April, January 30). Efficient compression of genomic sequences. Proceedings of the 2016 Data Compression Conference (DCC), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2016.60"},{"key":"ref_42","first-page":"115","article-title":"Universal sequential search problems","volume":"9","author":"Levin","year":"1973","journal-title":"Problemy Peredachi Informatsii"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0019-9958(84)80060-1","article-title":"Randomness conservation inequalities, information and independence in mathematical theories","volume":"61","author":"Levin","year":"1984","journal-title":"Inf. Control"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1142\/S0129054102001199","article-title":"The fastest and shortest algorithm for all well-defined problems","volume":"13","author":"Hutter","year":"2002","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_45","unstructured":"Hutter, M. (2004). Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability, Springer Science & Business Media."},{"key":"ref_46","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_47","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_48","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_49","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_50","doi-asserted-by":"crossref","unstructured":"Motwani, R., and Raghavan, P. (1995). Randomized Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","article-title":"Computational complexity of probabilistic Turing machines","volume":"6","author":"Gill","year":"1977","journal-title":"SIAM J. Comput."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/978-3-319-58838-4_29","article-title":"On the approximation of the Kolmogorov complexity for DNA sequences","volume":"10255","author":"Pratas","year":"2017","journal-title":"Pattern Recognit. Image Anal."},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Pinho, A.J., Ferreira, P.J.S.G., Neves, A.J.R., and Bastos, C.A.C. (2011). On the Representability of Complete Genomes by Multiple Competing Finite-Context (Markov) Models. PLoS ONE, 6.","DOI":"10.1371\/journal.pone.0021588"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Adamatzky, A. (2019). Algorithmic Information Dynamics of Emergent, Persistent, and Colliding Particles in the Game of Life. From Parallel to Emergent Computing, Taylor & Francis\/CRC Press.","DOI":"10.1201\/9781315167084"},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Pratas, D., Hosseini, M., and Pinho, A.J. (2017, January 21\u201323). Substitutional tolerant Markov models for relative compression of DNA sequences. Proceedings of the 11th International Conference on Practical Applications of Computational Biology & Bioinformatics, Porto, Portugal.","DOI":"10.1007\/978-3-319-60816-7_32"},{"key":"ref_56","unstructured":"Pinho, A.J., Neves, A.J.R., and Ferreira, P.J.S.G. (2008, January 25\u201329). Inverted-repeats-aware finite-context models for DNA coding. Proceedings of the 2008 16th European Signal Processing Conference, Lausanne, Switzerland."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"3250","DOI":"10.1109\/TIT.2004.838101","article-title":"The similarity metric","volume":"50","author":"Li","year":"2004","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_58","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_59","first-page":"173","article-title":"\u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica und verwandter Systeme I","volume":"38","year":"1931","journal-title":"Monatshefte f\u00fcr Mathematik und Physik"},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Russell, B. (2009). Principles of Mathematics, Routledge.","DOI":"10.4324\/9780203864760"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/1\/105\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:19:51Z","timestamp":1760361591000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/1\/105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,16]]},"references-count":60,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,1]]}},"alternative-id":["e22010105"],"URL":"https:\/\/doi.org\/10.3390\/e22010105","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2020,1,16]]}}}