Computer Engineering Commons^™

Shift-Symmetric Configurations In Two-Dimensional Cellular Automata: Irreversibility, Insolvability, And Enumeration, Peter Banda, John S. Caughman Iv, Martin Cenek, Christof Teuscher

Mathematics and Statistics Faculty Publications and Presentations

The search for symmetry as an unusual yet profoundly appealing phenomenon, and the origin of regular, repeating configuration patterns have been for a long time a central focus of complexity science, and physics.

Here, we introduce group-theoretic concepts to identify and enumerate the symmetric inputs, which result in irreversible system behaviors with undesired effects on many computational tasks. The concept of so-called configuration shift-symmetry is applied on two-dimensional cellular automata as an ideal model of computation. The results show the universal insolvability of “non-symmetric” tasks regardless of the transition function. By using a compact enumeration formula and bounding the number …

Evolution Of Emergent Computation, James P. Crutchfield, Melanie Mitchell

Computer Science Faculty Publications and Presentations

A simple evolutionary process can discover sophisticated methods for emergent information processing in decentralized spatially-extended systems. The mechanisms underlying the resulting emergent computation are explicated by a novel technique for analyzing particle-based logic embedded in pattern-forming systems. Understanding how globally-coordinated computation can emerge in evolution is relevant both for the scientific understanding of natural information processing and for engineering new forms of parallel computing systems.