A new Method of Output from Cellular Automata: The Togglecount Transform

Abstract

Cellular automata (CAs) are lattices of simple cells, whose states change according to a set of local rules. Applications range from simulating real world systems to a general platform for computation. Within the eld of computer science, current research is mainly concerned with developing methods for programming CAs to solve particular tasks, as well as the pursuit of CAs with signs of complex behaviour. When it comes to I/O little has been done.

In this project the togglecount transform is introduced and investigated. It is a method for obtaining multiple outputs from a simple transformation over the temporal evolution of a CA, based on the number of state changes for individual cells during the time window of the transform. Investigation is done on elementary CAs (ECAs), and is mainly concerned with the diversity of the output, with respect to CA rule, CA size and the length of the time frame for the transform. The output variation is quantified by counting the number of unique achievable togglecount spectra, coined the "spectral diversity" of the CA.

Research is done both in a qualitative and quantitative manner. A combination of spacetime plots and spectrograms is introduced as a tool for inspecting the togglecount specter over the temporal evolution of the ECA. The specter density plot is introduced as a way of representing the full range of togglecount spectra achievable for a given ECA. Simulations are employed to find the spectral diversity for various sizes of the ECAs, for various transform window sizes.

Bounds for the achievable spectra are found to be intrinsic to the rule, but many ECAs show a relatively wide range of spectra over the set of initial configurations. Spectral diversity generally increases with increasing CA size s, and with transformation window size w when w < s. The ECAs are divided in three classes based on the behaviour of the spectral diversity with respect to window size, some of which has an oscillating behaviour, and a connection is found to an existing classification scheme based on the fourier transform. The results show that the togglecount transform leads to output consisting of multiple variables, and that those variables take a range of values depending on initial configuration.