Decreasing Energy Functions and Lengths of Transients for Some Cellular Automata
Eric Goles
Department of Mathematics, Engineering School, University of Chile,
Casilla 170/3, Correo 3, Santiago, Chile
Andrew M. Odlyzko
AT&T Bell Laboratories, Murrary Hill, NJ 07974, U.S.A.
Abstract
The work of Ghiglia, Mastin, and Romero on a "phase-unwrapping" algorithm gives rise to the following operation: for any undirected graph with arbitrary integer values attached to the vertices, simultaneous updates are performed on these values, with the value of a vertex being changed by one in the direction of the average of the values of the adjacent vertices. (When the average equals the value of a vertex, the value of the vertex is incremented by one, unless all the neighbors have the same value, in which case no change is made.) Earlier work of Odlyzko and Randall showed that iterating this operation always leads to a cycle of length one or two, but did not give a bound on how many iterations might be needed to reach such a cycle. This paper introduces a new "energy function" which does yield a bound for the transient. A novel feature of this energy is that it contains not only linear and bilinear terms, as is common, but also terms involving the minimum function.
