{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T00:10:36Z","timestamp":1725754236692},"reference-count":53,"publisher":"MIT Press","issue":"3\u20134","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,3,16]]},"abstract":"<jats:p>In order to develop systems capable of artificial evolution, we need to identify which systems can produce complex behavior. We present a novel classification method applicable to any class of deterministic discrete space and time dynamical systems. The method is based on classifying the asymptotic behavior of the average computation time in a given system before entering a loop. We were able to identify a critical region of behavior that corresponds to a phase transition from ordered behavior to chaos across various classes of dynamical systems. To show that our approach can be applied to many different computational systems, we demonstrate the results of classifying cellular automata, Turing machines, and random Boolean networks. Further, we use this method to classify 2D cellular automata to automatically find those with interesting, complex dynamics. We believe that our work can be used to design systems in which complex structures emerge. Also, it can be used to compare various versions of existing attempts to model open-ended evolution (Channon, 2006; Ofria &amp; Wilke, 2004; Ray, 1991).<\/jats:p>","DOI":"10.1162\/artl_a_00342","type":"journal-article","created":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T17:40:32Z","timestamp":1630604432000},"page":"220-245","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":1,"title":["Classification of Discrete Dynamical Systems Based on Transients"],"prefix":"10.1162","volume":"27","author":[{"given":"Barbora","family":"Hudcov\u00e1","sequence":"first","affiliation":[{"name":"Charles University, Prague"},{"name":"Czech Institute of Informatics, Robotics, and Cybernetics, Prague. bara.hudcova@gmail.com"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom\u00e1\u0161","family":"Mikolov","sequence":"additional","affiliation":[{"name":"Czech Institute of Informatics, Robotics, and Cybernetics, Prague. tmikolov@gmail.com"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2022,3,16]]},"reference":[{"key":"2022032316101618300_bib1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-0-387-21789-5_2","article-title":"Boolean dynamics with random couplings","volume-title":"Perspectives and problems in nonlinear science: A celebratory volume in honor of Lawrence Sirovich","author":"Aldana","year":"2003"},{"key":"2022032316101618300_bib2","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0167-2789(96)00003-6","article-title":"Median attractor and transients in random Boolean nets","volume":"95","author":"Bhattacharjya","year":"1996","journal-title":"Physica D: Nonlinear Phenomena"},{"key":"2022032316101618300_bib3","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s10710-006-9009-3","article-title":"Unbounded evolutionary dynamics in a system of agents that actively process and transform their environment","volume":"7","author":"Channon","year":"2006","journal-title":"Genetic Programming and Evolvable Machines"},{"key":"2022032316101618300_bib4","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1109\/SSCI44817.2019.9002840","article-title":"Evolving structures in complex systems","volume-title":"Proceedings of the 2019 IEEE Symposium Series on Computational Intelligence","author":"Cisneros","year":"2019"},{"issue":"1","key":"2022032316101618300_bib5","first-page":"1","article-title":"Universality in elementary cellular automata","volume":"15","author":"Cook","year":"2004","journal-title":"Complex Systems"},{"key":"2022032316101618300_bib6","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0167-2789(93)90092-F","article-title":"Turbulent pattern bases for cellular automata","volume":"69","author":"Crutchfield","year":"1993","journal-title":"Physica D: Nonlinear Phenomena"},{"key":"2022032316101618300_bib7","first-page":"177","article-title":"Undecidability of CA classification schemes","volume":"2","author":"Culik","year":"1988","journal-title":"Complex Systems"},{"key":"2022032316101618300_bib8","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1051\/jphys:01987004806097100","article-title":"The random map model: A disordered model with deterministic dynamics","volume":"48","author":"Derrida","year":"1987","journal-title":"Journal de Physique"},{"issue":"2","key":"2022032316101618300_bib9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1209\/0295-5075\/1\/2\/001","article-title":"Random networks of automata: A simple annealed approximation","volume":"1","author":"Derrida","year":"1986","journal-title":"Europhysics Letters"},{"issue":"7","key":"2022032316101618300_bib10","doi-asserted-by":"publisher","first-page":"1695","DOI":"10.1088\/0305-4470\/21\/7\/031","article-title":"Exact solution of Kauffman's model with connectivity one","volume":"21","author":"Flyvbjerg","year":"1988","journal-title":"Journal of Physics A: Mathematical and General"},{"key":"2022032316101618300_bib11","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1038\/scientificamerican1070-120","article-title":"The fantastic combinations of John Conway's new solitaire game \u201cLife.\u201d","volume":"223","author":"Gardener","year":"1970","journal-title":"Scientific American"},{"key":"2022032316101618300_bib12","first-page":"160","article-title":"Introduction to random Boolean networks","volume-title":"Proceeding of the workshops and tutorials of the ninth international conference on the simulation and synthesis of living systems (ALife IX)","author":"Gershenson","year":"2004"},{"issue":"1","key":"2022032316101618300_bib13","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/0167-2789(90)90179-S","article-title":"A hierarchical classification of cellular automata","volume":"45","author":"Gutowitz","year":"1990","journal-title":"Physica D: Nonlinear Phenomena"},{"issue":"12","key":"2022032316101618300_bib14","doi-asserted-by":"publisher","first-page":"R7881","DOI":"10.1103\/PhysRevA.44.R7881","article-title":"Transients, cycles, and complexity in cellular automata","volume":"44","author":"Gutowitz","year":"1994","journal-title":"Physical Review A"},{"issue":"1","key":"2022032316101618300_bib15","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0167-2789(87)90120-5","article-title":"Local structure theory for cellular automata","volume":"28","author":"Gutowitz","year":"1987","journal-title":"Physica D: Nonlinear Phenomena"},{"key":"2022032316101618300_bib16","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-0-387-30440-3_51","article-title":"Cellular automata, Emergent phenomena","volume-title":"Encyclopedia of Complexity and Systems Science","author":"Hanson","year":"2009"},{"key":"2022032316101618300_bib17","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1214\/aoms\/1177705677","article-title":"Probability distributions related to random mappings","volume":"31","author":"Harris","year":"1960","journal-title":"Annals of Mathematical Statistics"},{"key":"2022032316101618300_bib18","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/BF01691062","article-title":"Endomorphisms and automorphisms of the shift dynamical system","volume":"3","author":"Hedlund","year":"1969","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"2022032316101618300_bib19","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1006\/excr.2000.5044","article-title":"Shape-dependent control of cell growth, differentiation, and apoptosis: Switching between attractors in cell regulatory networks","volume":"261","author":"Huang","year":"2000","journal-title":"Experimental Cell Research"},{"key":"2022032316101618300_bib20","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1162\/isal_a_00260","article-title":"Classification of complex systems based on transients","volume-title":"Proceedings of the ALIFE 2020: The 2020 conference on artificial life","author":"Hudcov\u00e1","year":"2020"},{"key":"2022032316101618300_bib21","first-page":"367","article-title":"Attractors, basin structures and information processing in cellular automata","volume-title":"Theory and applications of cellular automata","author":"Kaneko","year":"1986"},{"issue":"1","key":"2022032316101618300_bib22","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2004.11.021","article-title":"Theory of cellular automata: A survey","volume":"334","author":"Kari","year":"2005","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"2022032316101618300_bib23","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/0022-5193(69)90015-0","article-title":"Metabolic stability and epigenesis in randomly constructed genetic nets","volume":"22","author":"Kauffman","year":"1969","journal-title":"Journal of Theoretical Biology"},{"issue":"2","key":"2022032316101618300_bib24","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0022-5193(89)80019-0","article-title":"The NK model of rugged fitness landscapes and its application to maturation of the immune response","volume":"141","author":"Kauffman","year":"1989","journal-title":"Journal of Theoretical Biology"},{"issue":"1","key":"2022032316101618300_bib25","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0167-2789(84)90256-2","article-title":"Self-reproduction in cellular automata","volume":"10","author":"Langton","year":"1984","journal-title":"Physica D: Nonlinear Phenomena"},{"issue":"1\u20133","key":"2022032316101618300_bib26","doi-asserted-by":"publisher","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: Nonlinear Phenomena"},{"key":"2022032316101618300_bib27","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1103\/PhysRevE.55.257","article-title":"Phase transitions in random networks: Simple analytic determination of critical points","volume":"55","author":"Luque","year":"1997","journal-title":"Physical Review E"},{"issue":"1","key":"2022032316101618300_bib28","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0378-4371(00)00184-9","article-title":"Lyapunov exponents in random Boolean networks","volume":"284","author":"Luque","year":"2000","journal-title":"Physica A: Statistical Mechanics and Its Applications"},{"article-title":"A criterion for stability in random Boolean cellular automata","year":"1993","author":"Lynch","key":"2022032316101618300_bib29"},{"key":"2022032316101618300_bib30","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF01223745","article-title":"Algebraic properties of cellular automata","volume":"93","author":"Martin","year":"1984","journal-title":"Communications in Mathematical Physics"},{"key":"2022032316101618300_bib31","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/3527602968.ch4","article-title":"Computation in cellular automata: A selected review","volume-title":"Nonstandard computation","author":"Mitchell","year":"1998"},{"key":"2022032316101618300_bib32","article-title":"Evolving cellular automata with genetic algorithms: A review of recent work","volume-title":"Proceedings of the first international conference on evolutionary computation and its applications (EvCA'96)","author":"Mitchell","year":"2000"},{"volume-title":"Theory of self-reproducing automata","year":"1966","author":"Neumann","key":"2022032316101618300_bib33"},{"issue":"2","key":"2022032316101618300_bib34","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1162\/106454604773563612","article-title":"Avida: A software platform for research in computational evolutionary biology","volume":"10","author":"Ofria","year":"2004","journal-title":"Artificial Life"},{"article-title":"Monte Carlo theory, methods and examples","year":"2013","author":"Owen","key":"2022032316101618300_bib35"},{"key":"2022032316101618300_bib36","doi-asserted-by":"publisher","DOI":"10.1155\/2019\/3728621","article-title":"A novel antifragility measure based on satisfaction and its application to random and biological Boolean networks","volume":"2019","author":"Pineda","year":"2019","journal-title":"Complexity"},{"key":"2022032316101618300_bib37","first-page":"371","article-title":"An approach to the synthesis of life","volume-title":"Artificial life II: Proceedings of the workshop on artificial life","author":"Ray","year":"1991"},{"issue":"5099","key":"2022032316101618300_bib38","doi-asserted-by":"publisher","first-page":"1282","DOI":"10.1126\/science.259.5099.1282","article-title":"Simple systems that exhibit self-directed replication","volume":"259","author":"Reggia","year":"1993","journal-title":"Science"},{"issue":"2","key":"2022032316101618300_bib39","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0304-3975(96)00077-1","article-title":"Small universal Turing machines","volume":"168","author":"Rogozhin","year":"1996","journal-title":"Theoretical Computer Science"},{"key":"2022032316101618300_bib40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31933-4","volume-title":"Turing computability, theory and applications","author":"Soare","year":"2016"},{"key":"2022032316101618300_bib41","first-page":"793","article-title":"Identifying necessary conditions for open-ended evolution through the artificial life world of Chromaria","volume-title":"Proceedings of the ALIFE 14: The fourteenth international conference on the synthesis and simulation of living systems","author":"Soros","year":"2012"},{"key":"2022032316101618300_bib42","doi-asserted-by":"publisher","first-page":"1979","DOI":"10.1007\/978-3-540-92910-9_59","article-title":"Nonclassical computation: A dynamical systems perspective","volume-title":"Handbook of natural computing","author":"Stepney","year":"2012"},{"issue":"2","key":"2022032316101618300_bib43","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0022-0000(77)80007-X","article-title":"Computation and construction universality of reversible cellular automata","volume":"15","author":"Toffoli","year":"1977","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"2022032316101618300_bib44","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","article-title":"On computable numbers with as application to the Entscheidungsproblem","volume":"s2-42","author":"Turing","year":"1937","journal-title":"Proceedings of the London Mathematical Society"},{"issue":"1","key":"2022032316101618300_bib45","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0167-2789(84)90253-7","article-title":"Simulating physics with cellular automata","volume":"10","author":"Vichniac","year":"1984","journal-title":"Physica D: Nonlinear Phenomena"},{"issue":"4","key":"2022032316101618300_bib46","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1162\/artl_a_00041","article-title":"Fisher information at the edge of chaos in random Boolean networks","volume":"17","author":"Wang","year":"2011","journal-title":"Artificial Life"},{"issue":"1","key":"2022032316101618300_bib47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-2789(84)90245-8","article-title":"Universality and complexity in cellular automata","volume":"10","author":"Wolfram","year":"1984","journal-title":"Physica D: Nonlinear Phenomena"},{"volume-title":"A new kind of science","year":"2002","author":"Wolfram","key":"2022032316101618300_bib48"},{"key":"2022032316101618300_bib49","doi-asserted-by":"crossref","first-page":"383","DOI":"10.7551\/mitpress\/6860.003.0034","article-title":"The emergence of memory: Categorisation far from equilibrium","volume-title":"Towards a science of consciousness: The first Tucson discussions and debates","author":"Wuensche","year":"1996"},{"key":"2022032316101618300_bib51","volume-title":"Exploring discrete dynamics","author":"Wuensche","year":"2016","edition":"(2nd ed.)"},{"volume-title":"The global dynamics of cellular automata: An atlas of basin of attraction fields of one-dimensional cellular automata","year":"2001","author":"Wuensche","key":"2022032316101618300_bib50"},{"issue":"1","key":"2022032316101618300_bib52","doi-asserted-by":"publisher","first-page":"1","DOI":"10.25088\/ComplexSystems.19.1.1","article-title":"Compression-based investigation of the dynamical properties of cellular automata and other systems","volume":"19","author":"Zenil","year":"2010","journal-title":"Complex Systems"},{"issue":"3","key":"2022032316101618300_bib53","doi-asserted-by":"publisher","first-page":"265","DOI":"10.25088\/ComplexSystems.20.3.265","article-title":"On the dynamic qualitative behavior of universal computation","volume":"20","author":"Zenil","year":"2012","journal-title":"Complex Systems"}],"container-title":["Artificial Life"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/artl\/article-pdf\/27\/3%E2%80%934\/220\/2003303\/artl_a_00342.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/artl\/article-pdf\/27\/3%E2%80%934\/220\/2003303\/artl_a_00342.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T17:56:02Z","timestamp":1725731762000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/artl\/article\/27\/3%E2%80%934\/220\/106923\/Classification-of-Discrete-Dynamical-Systems-Based"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":53,"journal-issue":{"issue":"3\u20134","published-online":{"date-parts":[[2022,3,16]]},"published-print":{"date-parts":[[2022,3,16]]}},"URL":"https:\/\/doi.org\/10.1162\/artl_a_00342","relation":{},"ISSN":["1064-5462","1530-9185"],"issn-type":[{"type":"print","value":"1064-5462"},{"type":"electronic","value":"1530-9185"}],"subject":[],"published-other":{"date-parts":[[2021]]},"published":{"date-parts":[[2021]]}}}