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 difficult, and automated design techniques such as genetic programming have their limitations because of the absence of human intuition. In this paper, 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. Although many of the framework elements that we describe here are not new, we group them into a consistent framework and show that they can all be implemented on a traditional cellular automaton, which means that they are merely more human-friendly ways of describing simple cellular automata rules, and not foreign structures that require changing the traditional cellular automaton model.
References
-
Andrew Adamatzky , Identification of Cellular Automata ( Taylor and Francis , London, Bristol , 1994 ) . Google Scholar - Kybernetes: The International Journal of Systems & Cybernetics 26(2), 126 (1997). Crossref, ISI, Google Scholar
-
David Andre , Forrest H. Bennett III and John R. Koza , Evolution of intricate long-distance communication signals in cellular automata using genetic programming , Artificial Life V: Proceedings of the Fifth International Workshop on the Synthesis and Simulation of Living Systems ( The MIT Press , 1996 ) . Google Scholar - Mathieu Capcarrere. Cellular Automata and other Cellular Systems: Design & Evolution. PhD dissertation, Swiss Federal Institute of Technology Lausanne, March 2002 . Google Scholar
- Physical Review E 55, 2081R (1997). Crossref, ISI, Google Scholar
- Problems of Information Transmission 14(3), 92 (1978). Google Scholar
- Physical Review Letters 74(25), 5148 (1995). Crossref, ISI, Google Scholar
- Proceedings of the IEEE 85(4), 541 (1997). Crossref, ISI, Google Scholar
- Journal of Statistical Physics 68(6), 829 (1992). Crossref, ISI, Google Scholar
-
Melanie Mitchell , Non-Standard Computation ( John Wiley & Sons, Inc. , New York, NY, USA , 1997 ) . Google Scholar - IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 49(11), 1629 (2002). Crossref, Google Scholar
- IEEE Transactions on Image Processing 15(7), 2076 (2006). Crossref, ISI, Google Scholar
-
Moshe Sipper , Evolution of Parallel Cellular Machines: The Cellular Programming Approach ( Springer-Verlag , 1997 ) . Crossref, Google Scholar - Sami Torbey. Towards a framework for intuitive programming of cellular automata. Master's thesis, Queen's University, 2007 . Google Scholar
- Sami Torbey and Selim G. Akl. An exact and optimal local solution to the two-dimensional convex hull of arbitrary points problem. Journal of Cellular Automata (in press) . Google Scholar
- Sami Torbey and Selim G. Akl. An exact solution to the two-dimensional arbitrary-threshold density classification problem. Journal of Cellular Automata (in press) . Google Scholar
-
Sami Torbey and Selim G. Akl , Towards a framework for high-level manual programming of cellular automata , 13th International Workshop on Cellular Automata ( The Fields Institute , 2007 ) . Google Scholar - International Journal of Unconventional Computing 3(1), 49 (2007). ISI, Google Scholar
-
Stephen Wolfram , A New Kind of Science ( Wolfram Media , 2002 ) . Google Scholar


