Towards a framework for intuitive programming of cellular automata

Abstract

The ability to obtain complex global behaviour from simple local rules makes cellular automata an interesting platform for massively parallel computation. However, manually designing a cellular automaton to perform a given computation can be extremely tedious, and automated design techniques such as genetic programming have their limitations because of the absence of human intuition. In this thesis, we propose elements of a framework whose goal is to make the manual synthesis of cellular automata rules exhibiting desired global characteristics more programmer-friendly, while maintaining the simplicity of local processing elements. We also demonstrate the power of that framework by using it to provide intuitive yet effective solutions to the two-dimensional majority classification problem, the convex hull of disconnected points problem, and various problems pertaining to node placement in wireless sensor networks.