World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

TOWARDS A FRAMEWORK FOR INTUITIVE PROGRAMMING OF CELLULAR AUTOMATA

    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
    • Andrew Adamatzky, Kybernetes: The International Journal of Systems & Cybernetics 26(2), 126 (1997). Crossref, ISIGoogle 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
    • Henryk Fuks, Physical Review E 55, 2081R (1997). Crossref, ISIGoogle Scholar
    • Peter Gacs, Georgii L. Kurdyumov and Leonid A. Levin, Problems of Information Transmission 14(3), 92 (1978). Google Scholar
    • Mark Land and Richard K. Belew, Physical Review Letters 74(25), 5148 (1995). Crossref, ISIGoogle Scholar
    • Craig. S. Lent and Paul D. Tougaw, Proceedings of the IEEE 85(4), 541 (1997). Crossref, ISIGoogle Scholar
    • Wentian Li, Journal of Statistical Physics 68(6), 829 (1992). Crossref, ISIGoogle Scholar
    • Melanie   Mitchell , Non-Standard Computation ( John Wiley & Sons, Inc. , New York, NY, USA , 1997 ) . Google Scholar
    • Toshinori Munakata, Sudeshna Sinha and William L. Ditto, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 49(11), 1629 (2002). CrossrefGoogle Scholar
    • Paul L. Rosin, IEEE Transactions on Image Processing 15(7), 2076 (2006). Crossref, ISIGoogle Scholar
    • Moshe   Sipper , Evolution of Parallel Cellular Machines: The Cellular Programming Approach ( Springer-Verlag , 1997 ) . CrossrefGoogle 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
    • Heather Turner, Susan Stepney and Fiona Polack, International Journal of Unconventional Computing 3(1), 49 (2007). ISIGoogle Scholar
    • Stephen   Wolfram , A New Kind of Science ( Wolfram Media , 2002 ) . Google Scholar