Complexity Steering in Cellular Automata
Bar Y. Peled
Avishy Y. Carmi
Department of Mechanical Engineering
Ben-Gurion University of the Negev
Abstract
A cellular automaton is presented whose governing rule is that the Kolmogorov complexity of a cell’s neighborhood may not increase when the cell’s present value is substituted for its future value. Using an approximation of this two-dimensional Kolmogorov complexity, the underlying automaton is shown to be capable of simulating binary logic circuits. A similar automaton whose rule permits at times the increase of a cell’s neighborhood complexity is shown to produce animated entities that can be used as information carriers akin to gliders in Conway’s Game of Life. The element that repeatedly generates gliders, the glider gun, is constructed in this automaton using a number of self-replicating mechanisms. Moreover, gliders’ annihilation and creation allow constructing logic gates as well as data encoding mechanisms.
Keywords: cellular automata; Kolmogorov complexity; universal computation; self-replication; negentropy
