Decreasing energy functions and lengths of transients for some cellular automata
Éric Goles, Andrew M. Odlyzko · Complex Systems · 1988
Th e work of Ghiglia , Masti n, an d Romero on a p hase unwrapping algorith m gives rise to the following operation : for an y undirect ed graph wit h a rbit ra ry int eger values attached to the verti ces, simulta neous upd at es are perform ed on these values, with t he value of a verte x being cha nged by one in th e direction of th e average of t he values of t he adjace nt vert ices. (When t he average equals t he value of a vertex, th e val ue of th e ver tex is incremented by one, unless all t he neighbors have th e same value, in which case no change is made.) Ea rlier work of Odlyzko a nd Rand all showed that iterat ing t his operation always leads to a cycle of length one or two, but did not give a bound on how many iterat ions might be needed to reach such a cycle. T his paper int rodu ces a new funct ion which does yield a bound for the t rans ient . A novel feature of t his energy is that it contains not only linea r an d bilinea r ter ms, as is common, but also te rms involving th e minimum function .