Booth Id:
MA009
Category:
Materials Science
Year:
2014
Finalist Names:
Stone, Bertrand (School: Chesapeake Science Point Public Charter School)
Abstract:
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.