2013/10/11 by Lucas Kang, Kang, Lucas
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Physics and Astronomy · #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #Computational Complexity (cs.CC) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Physical sciences #Modular Robots and Swarm Intelligence #Pattern Formation and Solitons (nlin.PS) #cs.CC #nlin.CG #nlin.PS
paper · pdf · doi:10.48550/arxiv.1310.3311
23 pages (including references and comments), 25 figures, independent research, to be published in nlin.CG, nlin.PS and cs.CC
arxiv created 2013/10/11 · openalex publication_date 2013/10/11 · arxiv updated 2013/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Cellular automata (CA) have been utilized for decades as discrete models of many physical, mathematical, chemical, biological, and computing systems. The most widely known form of CA, the elementary cellular automaton (ECA), has been studied in particular due to its simple form and versatility. However, these dynamic computation systems possess evolutionary rules dependent on a neighborhood of adjacent cells, which limits their sampling radius and the environments that they can be used in. The purpose of this study was to explore the complex nature of one-dimensional CA in configurations other than that of the standard ECA. Namely, "long-distance cellular automata" (LDCA), a construct that had been described in the past, but never studied. I experimented with a class of LDCA that used spaced sample cells unlike ECA, and were described by the notation LDCA-x-y-n, where x and y represented the amount of spacing between the cell and its left and right neighbors, and n denoted the length of the initial tape for tapes of finite size. Some basic characteristics of ECA are explored in this paper, such as seemingly universal behavior, the prevalence of complexity with varying neighborhoods, and qualitative behavior as a function of x and y spacing. Focusing mainly on purely Class 4 behavior in LDCA-1-2, I found that Rule 73 could potentially be Turing universal through the emulation of a cyclic tag system, and revealed a connection between the mathematics of binary trees and Eulerian numbers that might provide insight into unsolved problems in both fields.