{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:43:53Z","timestamp":1760402633248,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T00:00:00Z","timestamp":1580083200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We investigate chaoticity and complexity of a binary general network automata of finite size with external input which we call a computron. As a generalization of cellular automata, computrons can have non-uniform cell rules, non-regular cell connectivity and an external input. We show that any finite-state machine can be represented as a computron and develop two novel set-theoretic concepts: (i) diversity space as a metric space that captures similarity of configurations on a given graph and (ii) basin complexity as a measure of complexity of partitions of the diversity space. We use these concepts to quantify chaoticity of computrons\u2019 dynamics and the complexity of their basins of attraction. The theory is then extended into probabilistic machines where we define fuzzy basin partitioning of recurrent classes and introduce the concept of ergodic decomposition. A case study on 1D cyclic computron is provided with both deterministic and probabilistic versions.<\/jats:p>","DOI":"10.3390\/e22020150","type":"journal-article","created":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T11:41:57Z","timestamp":1580125317000},"page":"150","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dynamics and Complexity of Computrons"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2992-4154","authenticated-orcid":false,"given":"Murat","family":"Erkurt","sequence":"first","affiliation":[{"name":"Department of Mathematics, Centre for Complexity Science, Imperial College London, South Kensington campus, London SW7 2AZ, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,1,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02429850","article-title":"Lyapunov Exponents for One-Dimensional Cellular Automata","volume":"2","author":"Shereshevsky","year":"1992","journal-title":"J. Nonlinear. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1547","DOI":"10.1088\/0951-7715\/13\/5\/308","article-title":"Cellular automata and Lyapunov exponents","volume":"13","author":"Tisseur","year":"2000","journal-title":"Nonlinearity"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1017\/S0143385700006738","article-title":"The Topological-Entropy of Cellular Automata Is Uncomputable","volume":"12","author":"Hurd","year":"1992","journal-title":"Ergod. Theor. Dyn. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1006\/jcom.1998.0474","article-title":"Lyapunov exponents versus expansivity and sensitivity in cellular automata","volume":"14","author":"Finelli","year":"1998","journal-title":"J. Complex."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1006\/jcss.1998.1609","article-title":"Attractors of linear cellular automata","volume":"58","author":"Manzini","year":"1999","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0304-3975(98)00005-X","article-title":"Ergodicity, transitivity, and regularity for linear cellular automata over Z(m)","volume":"233","author":"Cattaneo","year":"2000","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1629","DOI":"10.1016\/S0304-3975(02)00071-3","article-title":"On computing the entropy of cellular automata","volume":"290","author":"Manzini","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","article-title":"Complexity of Finite Sequences","volume":"22","author":"Lempel","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Zenil, H. (2010). Compression-Based Investigation of the Dynamical Properties of Cellular Automata and Other Systems. Complex Syst., 19.","DOI":"10.25088\/ComplexSystems.19.1.1"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF01217347","article-title":"Computation Theory of Cellular Automata","volume":"96","author":"Wolfram","year":"1984","journal-title":"Commun. Math. Phys."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1038\/311419a0","article-title":"Cellular Automata as Models of Complexity","volume":"311","author":"Wolfram","year":"1984","journal-title":"Nature"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1088\/0031-8949\/1985\/T9\/029","article-title":"20 Problems in the Theory of Cellular Automata","volume":"1985","author":"Wolfram","year":"1985","journal-title":"Phys. Scr."},{"key":"ref_13","unstructured":"Culik, K., and Yu, S. (1988). Undecidedability of CA classification schemes. Complex Systems 2, Complex Systems Publications, Inc."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0167-2789(90)90175-O","article-title":"Transition Phenomena in Cellular Automata Rule Space","volume":"45","author":"Li","year":"1990","journal-title":"Phys. D"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1017\/S014338579706985X","article-title":"Languages, equicontinuity and attractors in cellular automata","volume":"17","author":"Kurka","year":"1997","journal-title":"Ergod. Theor. Dyn. Syst."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2655","DOI":"10.1142\/S0218127402006333","article-title":"A nonlinear dynamics perspective of Wolfram\u2019s new kind of science. Part I: Threshold of complexity","volume":"12","author":"Chua","year":"2002","journal-title":"Int. J. Bifurc. Chaos"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Ewert, T. (2019). A Measure for the Complexity of Elementary Cellular Automata. Complex Syst., 28.","DOI":"10.25088\/ComplexSystems.28.2.219"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1016\/j.physa.2005.02.019","article-title":"Topology regulates pattern formation capacity of binary cellular automata on graphs","volume":"354","author":"Marr","year":"2005","journal-title":"Phys. A"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/11861201_5","article-title":"Generalized automata networks","volume":"Volume 4173","author":"Chopard","year":"2006","journal-title":"Cellular Automata"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/978-3-642-00982-2_26","article-title":"Non-uniform Cellular Automata","volume":"Volume 5457","author":"Dediu","year":"2009","journal-title":"Language and Automata Theory and Applications"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Daza, A., Wagemakers, A., Georgeot, B., Guery-Odelin, D., and Sanjuan, M.A.F. (2016). Basin entropy: A new tool to analyze uncertainty in dynamical systems. Sci. Rep., 6.","DOI":"10.1038\/srep31416"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s002360050075","article-title":"Distance measures for point sets and their computation","volume":"34","author":"Eiter","year":"1997","journal-title":"Acta Inform."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1407","DOI":"10.1109\/18.681318","article-title":"Information distance","volume":"44","author":"Bennett","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"198701","DOI":"10.1103\/PhysRevLett.98.198701","article-title":"Network analysis of the state space of discrete dynamical systems","volume":"98","author":"Shreim","year":"2007","journal-title":"Phys. Rev. Lett."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/2\/150\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:44:44Z","timestamp":1760363084000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/2\/150"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,27]]},"references-count":24,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,2]]}},"alternative-id":["e22020150"],"URL":"https:\/\/doi.org\/10.3390\/e22020150","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2020,1,27]]}}}