Investigating Transformational Complexity: Counting Functions a Region Induces on Another in Elementary Cellular Automata
Over the years, the field of artificial life has attempted to capture significant properties of life in artificial systems. By measuring quantities within such complex systems, the hope is to capture the reasons for the explosion of complexity in living systems. A major effort has been in discrete d...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2021/7501405 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850223876815978496 |
|---|---|
| author | Martin Biehl Olaf Witkowski |
| author_facet | Martin Biehl Olaf Witkowski |
| author_sort | Martin Biehl |
| collection | DOAJ |
| description | Over the years, the field of artificial life has attempted to capture significant properties of life in artificial systems. By measuring quantities within such complex systems, the hope is to capture the reasons for the explosion of complexity in living systems. A major effort has been in discrete dynamical systems such as cellular automata, where very few rules lead to high levels of complexity. In this paper, for every elementary cellular automaton, we count the number of ways a finite region can transform an enclosed finite region. We discuss the relation of this count to existing notions of controllability, physical universality, and constructor theory. Numerically, we find that particular sizes of surrounding regions have preferred sizes of enclosed regions on which they can induce more transformations. We also find three particularly powerful rules (90, 105, 150) from this perspective. |
| format | Article |
| id | doaj-art-5845b594970746fab05f75df4672b9ff |
| institution | OA Journals |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-5845b594970746fab05f75df4672b9ff2025-08-20T02:05:48ZengWileyComplexity1076-27871099-05262021-01-01202110.1155/2021/75014057501405Investigating Transformational Complexity: Counting Functions a Region Induces on Another in Elementary Cellular AutomataMartin Biehl0Olaf Witkowski1Araya Inc., Tokyo, JapanCross Labs, Cross Compass Ltd., Tokyo, JapanOver the years, the field of artificial life has attempted to capture significant properties of life in artificial systems. By measuring quantities within such complex systems, the hope is to capture the reasons for the explosion of complexity in living systems. A major effort has been in discrete dynamical systems such as cellular automata, where very few rules lead to high levels of complexity. In this paper, for every elementary cellular automaton, we count the number of ways a finite region can transform an enclosed finite region. We discuss the relation of this count to existing notions of controllability, physical universality, and constructor theory. Numerically, we find that particular sizes of surrounding regions have preferred sizes of enclosed regions on which they can induce more transformations. We also find three particularly powerful rules (90, 105, 150) from this perspective.http://dx.doi.org/10.1155/2021/7501405 |
| spellingShingle | Martin Biehl Olaf Witkowski Investigating Transformational Complexity: Counting Functions a Region Induces on Another in Elementary Cellular Automata Complexity |
| title | Investigating Transformational Complexity: Counting Functions a Region Induces on Another in Elementary Cellular Automata |
| title_full | Investigating Transformational Complexity: Counting Functions a Region Induces on Another in Elementary Cellular Automata |
| title_fullStr | Investigating Transformational Complexity: Counting Functions a Region Induces on Another in Elementary Cellular Automata |
| title_full_unstemmed | Investigating Transformational Complexity: Counting Functions a Region Induces on Another in Elementary Cellular Automata |
| title_short | Investigating Transformational Complexity: Counting Functions a Region Induces on Another in Elementary Cellular Automata |
| title_sort | investigating transformational complexity counting functions a region induces on another in elementary cellular automata |
| url | http://dx.doi.org/10.1155/2021/7501405 |
| work_keys_str_mv | AT martinbiehl investigatingtransformationalcomplexitycountingfunctionsaregioninducesonanotherinelementarycellularautomata AT olafwitkowski investigatingtransformationalcomplexitycountingfunctionsaregioninducesonanotherinelementarycellularautomata |