Faculté informatique et communications IC, Section d'informatique, Institut des systèmes informatiques et multimédias ISIM (Laboratoire de systèmes logiques LSL)
Cellular automata and other cellular systems : design & evolution
Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2002 ; no 2541.Add to personal list
- Nature abounds in examples of cellular systems. From ant colonies to cellular tissues, from molecular systems to the human brain, cellularity seems to be the way Nature operates. The brain, surely one of the most complex objects to be found on earth, is the quintessence of a cellular system: a huge number of simple elements with an extremely high local connectivity and deprived of any sort of central control, giving rise to a rich global behavior. Cellular interactions thus seem to be the basis for complex phenomena, exhibiting qualities often missing in human artifacts : robustness, self-repair and, more generally, adaptability. The goal of this thesis is to answer the following question: "What may be computed in cellular systems ?". This question is far from obvious and implies many interrogations such as how to obtain the aforementioned qualities, how to program such systems, and, more fundamentally, what does computation mean in a cellular system. This thesis is mainly centered around the abstract and formal model of Cellular Automata. Through the study and the resolution of different tasks by means of evolution or mathematical demonstrations, I will show that it is not unreasonable to expect artificial systems to exhibit some of the qualities of natural systems, and that (guided) artificial evolution is surely the best approach to define the local behavior of elements which, when grouped as a cellular system, give rise to a desired global behavior. Above all, I will argue that truly emergent behavior in such designed systems is only a matter of perspective.