Back to the program.
Computing with Cellular Automata
Mathieu Capcarrere
EPFL
Lausanne
Switzerland
mcapcarr@philo.unil.ch

Abstract

Cellular Automata as a computational tool have been the subject of interest from the computing community for many years now. More precisely, the development of the Artificial Life field led many to wonder on how to do computation with such tools. Artificial Evolution, which gave good results on specific tasks such as the density classification or the synchronization tasks, was often given as an answer. However, it appeared that the limitations of such an approach were severe and really the question of WHAT meant computation with cellular automata became pregnant. The answer to this question is far from obvious. Mitchell, Crutchfield, Hanson et als. proposed an analysis of "particles" as a partial answer. Wuensche more recently developed the Z parameter as a paraphernalia to treating this question. Before this question appeared in its full-blown form in the A-life/Computer scientist community, there were already propositions going this way with Wolfram's class III and, related, Langton's computing at the edge of chaos. In this presentation, I will argue that computation of CAs is a matter of visual efficiency. Basing our argument on recent results (ours and others) mainly, but not only, on the density and the synchronization task, I will propose a definition of what is computation by means of CAs. This will be the occasion to (re)define emergent behavior, in a limited scope, but also to envisage differently the whole question of what may be sought in computing research in CAs. The practical consequences of this approach will alter the HOW question answer, and most notably how to evolve computing emergent CAs.

Keywords

cellular automata