Project: Functionals of Cellular Automaton Rules

We model the collection of possible neighborhood configurations in an elementary cellular automaton as a discrete manifold over which the transition function or rule takes on Boolean values. We find the Dirichlet energy of different rules through the Boolean differential calculus by summing over all possible neighborhood configurations. We also perform spectral analysis of different elementary cellular automaton rules using the Walsh–Hadamard transform. The same analysis can be applied to transition functions that act on an entire causal network of cells, with cells in the first layer as the input and cells in the last layer as the output. We compare this measure of cellular automaton behavior with existing ones, including entropy-based measures and Lyapunov exponent estimators. We obtain a method for gradual rule modification that preserves the Dirichlet energy, with applications to enhancing genetic algorithms that attempt to find the right rule for performing a computation. Finally, we discuss possible extensions of this approach and directions for future research.

References

• Beer, T. (1981). Walsh transforms. American Journal of Physics, 49(5), 466-472.
• Borda, M. (2011). Fundamentals in Information Theory and Coding. Berlin, Germany: Springer-Verlag.
• Bengio, Y., Simard, P., & Frasconi, P. (1994). Learning long-term dependencies with gradient descent is difficult. Neural Networks, IEEE Transactions on, 5(2), 157-166.
• Cenek, M., & Mitchell, M. (2009). Evolving cellular automata. Encyclopedia of Complexity and Systems Science, 3233-3242.
• Cook, M. (2004). Universality in elementary cellular automata. Complex Systems, 15(1), 1-40.
• Das, R., Crutchfield, J. P., Mitchell, M., & Hanson, J. M. (1995). Evolving globally synchronized cellular automata. SFI Working Paper 1995-01-005 (1995)
• Erdelyi, A., & Bateman, H. (1954). Tables of integral transforms. New York: McGraw-Hill.
• Egmont-Petersen, M., de Ridder, D., & Handels, H. (2002). Image processing with neural networks—a review. Pattern recognition, 35(10), 2279-2301.
• Evans, L. (2010). Partial differential equations (2nd ed.). Providence, R.I.: American Mathematical Society.
• Graves, A., Mohamed, A. R., & Hinton, G. (2013, May). Speech recognition with deep recurrent neural networks. In Acoustics, Speech and Signal Processing (ICASSP), 2013 IEEE International Conference on (pp. 6645-6649). IEEE.
• Halbach, Mathias, and Rolf Hoffmann. “Implementing cellular automata in FPGA logic.” Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International. IEEE, 2004.
• Jaeger, H. (2001). The “echo state” approach to analysing and training recurrent neural networks-with an erratum note. Bonn, Germany: German National Research Center for Information Technology GMD Technical Report, 148, 34.
• Johnson, J., & Püschel, M. (2000). In search of the optimal Walsh-Hadamard transform. In Acoustics, Speech, and Signal Processing, 2000. ICASSP’00. Proceedings. 2000 IEEE International Conference on (Vol. 6, pp. 3347-3350). IEEE.
• Kuan, C. M., & Liu, T. (1995). Forecasting exchange rates using feedforward and recurrent neural networks. Journal of Applied Econometrics, 10(4), 347-364.
• Mitchell, M., Crutchfield, J. P., & Hraber, P. T. (1994). Evolving cellular automata to perform computations: Mechanisms and impediments. Physica D: Nonlinear Phenomena, 75(1), 361-391.
• Martin, O., Odlyzko, A. M., & Wolfram, S. (1984). Algebraic properties of cellular automata. Communications in mathematical physics, 93(2), 219-258.
• Nandi, S., Kar, B. K., & Chaudhuri, P. P. (1994). Theory and applications of cellular automata in cryptography. Computers, IEEE Transactions on, 43(12), 1346-1357.
• Rybacki, S., Himmelspach, J., & Uhrmacher, A. M. (2009, September). Experiments with single core, multi-core, and GPU based computation of cellular automata. In Advances in System Simulation, 2009. SIMUL’09. First International Conference on (pp. 62-67). IEEE.
• Rosin, P. L. (2006). Training cellular automata for image processing. Image Processing, IEEE Transactions on, 15(7), 2076-2087.
• Shanks, J. L. (1969). Computation of the fast Walsh-Fourier transform. IEEE Transactions on Computers, (5), 457-459.
• Shereshevsky, M. A. (1992). Lyapunov exponents for one-dimensional cellular automata. Journal of Nonlinear Science, 2(1), 1-8.
• Steinbach, B., & Posthoff, C. (2009). Boolean Differential Calculus. In Logic Functions and Equations (pp. 75-103). Springer Netherlands.
• Siegelmann, H. T., & Sontag, E. D. (1995). On the computational power of neural nets. Journal of computer and system sciences, 50(1), 132-150.
• Stauffer, D. (2001). Cellular Automata: Applications. In Vector and Parallel Processing—VECPAR 2000 (pp. 199-206). Berlin, Germany: Springer-Verlag
• Weisstein, E. W., Elementary cellular automaton. In Wolfram MathWorld.
• Weisstein, E. W., Fourier transform. In Wolfram MathWorld.
• Weisstein, E. W., Parseval’s Theorem. In Wolfram MathWorld.
• Wolfram, S. (1986). Theory and applications of cellular automata (Vol. 1). Singapore: World Scientific.
• Wolfram, S. (1984). Universality and complexity in cellular automata. Physica D: Nonlinear Phenomena, 10(1), 1-35.
• Xu, G. (2004). Discrete Laplace–Beltrami operators and their convergence. Computer Aided Geometric Design, 21(8), 767-784.
• Yilmaz, O. (2014). Reservoir Computing using Cellular Automata. arXiv:1410.0162 [cs.NE]