On fait généralement remonter l'histoire des automates cellulaires aux années quarante et à Stanislas Ulam. Ce mathématicien s'est intéressé à l'évolution de constructions graphiques engendrées à partir de règles simples. La base en était un espace à deux dimensions divisé en « cellules », soit une sorte de feuille quadrillée. Chacune des cellules pouvait avoir deux états : allumé ou éteint. Partant d'une configuration donnée, la génération suivante était déterminée en fonction de règles de voisinage. Par exemple, si une cellule donnée était en contact avec deux cellules allumées elle s'allumait sinon elle s'éteignait. Ulam, qui utilisait l'un des premiers ordinateurs, a rapidement constaté que ce mécanisme permettait de générer des figures complexes et esthétiques et que dans certains cas, ces figures pouvaient se répliquer. Des règles extrêmement simples permettaient de construire des structures très complexes. À partir de là, se posait la question suivante : ces mécanismes récursifs -- c'est-à-dire en l'occurrence dépendant de leur propre état antérieur -- peuvent-ils expliquer la complexité du réel ? Cette complexité n'est elle qu'apparente, les lois fondamentales étant elles-mêmes simples 1 ?
En parallèle, John von Neumann -- fort des travaux de A. Turing -- s'intéressait à la théorie des automates autoréplicateurs et travaillait à la conception d'une machine autoréplicatrice le « kinématon. » Une telle machine devait être capable, à partir de matériaux trouvés dans l'environnement, de produire n'importe quelle machine décrite dans son programme, y compris une copie d'elle-même. Von Neumann montrait ici comment résoudre le problème de l'autoréférence de la description. Pour s'autorépliquer, la machine devrait en effet contenir une description d'elle-même, mais pour être complète, cette description doit également être décrite, etc. La solution réside dans la capacité donnée à la machine d'interpréter sa description à la fois comme un programme, une séquence d'instruction, et comme un composant. La description sera d'abord interprétée pour construire la nouvelle machine, elle sera ensuite simplement copiée afin de donner à la nouvelle machine une description d'elle-même. Ce mécanisme correspond de fait à l'interprétation actuelle du fonctionnement de la molécule d'ADN découverte après les travaux de von Neumann. A.C. Clarke a rendu les machines de von Neumann célèbre avec la série « 2001 Odyssée de l'espace. » Pour transformer Jupiter en étoile, un premier monolithe se reproduit, les descendants font de même, la population croît ainsi de manière exponentielle pour atteindre rapidement la taille nécessaire à la réalisation d'une aussi gigantesque tâche.
C'est S. Ulam qui a suggéré à von Neumann d'utiliser ce qu'il appelait les « espaces cellulaires » (cellular spaces) pour construire sa machine autoréplicatrice. Il pouvait ainsi s'affranchir des conditions physiques réelles pour travailler dans un univers extrêmement simplifié pourtant apte à engendrer une haute complexité. Le passage à cet univers formel l'a amené à constater :
« En axiomatisant les automates [autoréplicateurs] de cette manière, on a jeté la moitié du problème par la fenêtre et c'est peut-être la moitié la plus importante. On s'est résigné à ne pas expliquer comme ces éléments sont constitués de choses réelles, particulièrement comment ces éléments sont constitués de particules élémentaires ou même de molécules (...) on considérera simplement que des particules élémentaires dotées de certaines propriétés existent. La question à laquelle on espère répondre, ou au moins examiner, est : Quels principes sont mis en ?uvre dans l'organisation de ces molécules dans les êtres vivants fonctionnels (...) Je discuterai de tout cela seulement de ce point de vue limité 2. »
Sur cette base, il conçut un automate cellulaire de quelques 200.000 cellules à 29 états contenant un copieur universel, une description de lui-même et une machine de Turing pour la supervision.
Les automates cellulaires sont sortis des laboratoires en 1970 avec le désormais fameux Jeu de la vie (Life Game) de John Horton Conway.
