Characterization of the Line Complexity of Cellular Automata Generated by Polynomial Transition Rules

Overview

Cellular automata are discrete dynamical systems which consist of changing patterns of symbols on a grid. The changes are specified in such a way that the symbol in a given position is determined by the symbols surrounding that position in the previous state. Despite the simplicity of their definition, cellular automata have been applied in the simulation of complex phenomena as disparate as biological systems and universal computers. In this paper, we investigate the line complexity a_T(k), or number of accessible coefficient blocks of length k, for cellular automata arising from a polynomial transition rule T. We first derive recursion formulas for the sequence a_T(k) associated to polynomials of the form 1+x+x^n where n is at least 3 and the coefficients are taken modulo 2. We then derive functional relations for the generating functions associated to these polynomials. Extending to a more general setting, we investigate the asymptotics of a_T(k) by considering a generating function phi(z) = sum_k alpha(k)z^k which satisfies a certain general functional equation relating phi(z) and phi(z^p) for some prime p. We show that for positive integral sequences s_k which are dependent upon a real number x in [1/p,1] and for which lim[k to infinity](log_p s_k - floor(log_p s_k)) = log_p(1/x), the ratio alpha(s_k)/(s_k)^2 tends to a piecewise quadratic function of x.

Competition history

• ISEF 2014 Materials Science · Entry MA009

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.