Jeu de la vieLe Jeu de la vie est un automate cellulaire imaginé par John Horton Conway en 1970. Malgré des règles très simples, il est Turing-complet. C'est un jeu de simulation au sens mathématique. Le Jeu de la vie est un « jeu à zéro joueur », puisqu'il ne nécessite aucune intervention du joueur lors de son déroulement. Il s’agit d’un automate cellulaire, un modèle où chaque état conduit mécaniquement à l’état suivant à partir de règles préétablies.
Rule 110The Rule 110 cellular automaton (often called simply Rule 110)is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect, it is similar to Conway's Game of Life. Like Life, Rule 110 with a particular repeating background pattern is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton. In an elementary cellular automaton, a one-dimensional pattern of 0s and 1s evolves according to a simple set of rules.
Stephen WolframStephen Wolfram (né le à Londres) est un scientifique britannique principalement connu pour son logiciel de calcul formel Mathematica, mais qui a également travaillé en physique des particules et sur les automates cellulaires. Stephen Wolfram est né le de parents réfugiés allemands, d'origine juive, émigrés en Angleterre en 1933. Son père, Hugo Wolfram, est romancier, et sa mère, , était professeur de philosophie à l'université d'Oxford. Il est le petit-fils de la psychanalyste Kate Friedlander.
A New Kind of ScienceA New Kind of Science (Un nouveau type de science), souvent référé par ses initiales NKS, est un livre best-seller, écrit par Stephen Wolfram, et publié par sa société Wolfram Research sous le nom de publication Wolfram Media, en 2002. Il contient une étude empirique et systématique des systèmes computationnels tels que les automates cellulaires. Wolfram appelle ces systèmes des programmes simples et soutient que la philosophie scientifique et les méthodes appropriées pour l'étude de programmes simples sont pertinentes dans d'autres domaines de la science.
OrdinateurUn ordinateur est un système de traitement de l'information programmable tel que défini par Alan Turing et qui fonctionne par la lecture séquentielle d'un ensemble d'instructions, organisées en programmes, qui lui font exécuter des opérations logiques et arithmétiques. Sa structure physique actuelle fait que toutes les opérations reposent sur la logique binaire et sur des nombres formés à partir de chiffres binaires.
Triangle de SierpińskiLe triangle de Sierpiński, ou tamis de Sierpińsky, également appelé par Mandelbrot le joint de culasse de Sierpiński, est une fractale, du nom de Wacław Sierpiński qui l'a décrit en 1915. Il peut s'obtenir à partir d'un triangle « plein », par une infinité de répétitions consistant à diviser par deux la taille du triangle puis à les accoler en trois exemplaires par leurs sommets pour former un nouveau triangle. À chaque répétition le triangle est donc de même taille, mais « de moins en moins plein ».
Wolfram codeWolfram code is a widely used numbering system for one-dimensional cellular automaton rules, introduced by Stephen Wolfram in a 1983 paper and popularized in his book A New Kind of Science. The code is based on the observation that a table specifying the new state of each cell in the automaton, as a function of the states in its neighborhood, may be interpreted as a k-digit number in the S-ary positional number system, where S is the number of states that each cell in the automaton may have, k = S2n + 1 is the number of neighborhood configurations, and n is the radius of the neighborhood.
Règle 30droite|vignette|Un Conus textile, présentant des motifs similaires à ceux de la règle 30. La règle 30 est un automate cellulaire élémentaire introduit par Stephen Wolfram en 1983. Il a la particularité de produire des motifs complexes, d'apparence aléatoire, à partir de règles simples et déterministes. La règle 30 est un automate cellulaire dit élémentaire : il consiste en une grille unidimensionnelle de cellules ne pouvant prendre que deux états, 0 et 1, avec un voisinage constitué, pour chaque cellule, d'elle-même et des deux cellules qui lui sont adjacentes.
John Horton ConwayJohn Horton Conway, né le à Liverpool et mort le à New Brunswick (New Jersey), est un mathématicien britannique. Il s'est intéressé aux théories des groupes finis, des nœuds, des nombres, des jeux et du codage. Né en 1937 en Angleterre, John Horton Conway s'intéresse très tôt aux mathématiques et décide de devenir mathématicien dès l'âge de 11 ans. Il étudie les mathématiques à Cambridge, au Gonville and Caius College, et obtient son Bachelor of Arts en 1959.
Théorie des automatesEn informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul.
Rule 184Rule 184 is a one-dimensional binary cellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different, particle systems: Rule 184 can be used as a simple model for traffic flow in a single lane of a highway, and forms the basis for many cellular automaton models of traffic flow with greater sophistication. In this model, particles (representing vehicles) move in a single direction, stopping and starting depending on the cars in front of them.
Rule 90In the mathematical study of cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value. In each time step all values are simultaneously replaced by the exclusive or of their two neighboring values. call it "the simplest non-trivial cellular automaton", and it is described extensively in Stephen Wolfram's 2002 book A New Kind of Science.
Elementary cellular automatonIn mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors. There is an elementary cellular automaton (rule 110, defined below) which is capable of universal computation, and as such it is one of the simplest possible models of computation.
Machine de Turing universellevignette|upright=1.5|Une machine de Turing quelconque M réalise un calcul à partir d'une entrée écrite sur son ruban. Une machine de Turing universelle U simule le calcul de M sur l'entrée de M à partir d'une description de M et de l'entrée de M écrits sur le ruban de U. En informatique, plus précisément en informatique théorique, une machine de Turing universelle est une machine de Turing qui peut simuler n'importe quelle machine de Turing sur n'importe quelle entrée.
Turing-completEn informatique et en logique, un système formel est dit complet au sens de Turing ou Turing-complet (par calque de l’anglais Turing-complete) s’il possède un pouvoir expressif au moins équivalent à celui des machines de Turing. Dans un tel système, il est donc possible de programmer n'importe quelle machine de Turing. Cette notion est rendue pertinente par la thèse de Church, qui postule l’existence d’une notion naturelle de calculabilité.
Vie artificielleLa vie artificielle est un champ de recherche interdisciplinaire alliant informatique et biologie, mais avec des applications dans des domaines variés tels que l'économie ou l'archéologie. Son objectif est de créer des systèmes artificiels s'inspirant des systèmes vivants, soit sous la forme de programmes informatiques, soit sous la forme de robots. La première manifestation de la vie artificielle date des années 1940.
Self-replicationSelf-replication is any behavior of a dynamical system that yields construction of an identical or similar copy of itself. Biological cells, given suitable environments, reproduce by cell division. During cell division, DNA is replicated and can be transmitted to offspring during reproduction. Biological viruses can replicate, but only by commandeering the reproductive machinery of cells through a process of infection. Harmful prion proteins can replicate by converting normal proteins into rogue forms.
Pavage du planthumb|Pavage constitué de triangles équilatéraux et d'hexagones, dit pavage trihexagonal. thumb|Pavage hexagonal de tomettes provençales en terre cuite. Un pavage du plan est un ensemble de portions du plan, par exemple des polygones, dont l'union est le plan tout entier, sans recouvrement. Plus précisément, c'est une partition du plan euclidien par des éléments d'un ensemble fini, appelés « carreaux » (plus précisément, ce sont des compacts d’intérieur non vide).
Model of computationIn computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized. The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology.
Automatevignette|Karakuri serveur de thé, avec mécanisme, . musée national de la nature et des sciences de Tokyo. Un automate est un dispositif reproduisant en autonomie une séquence d'actions prédéterminées sans l'intervention humaine, le système fait toujours la même chose. L'automate est un objet programmé. En automatisme le terme est réservé aux dispositifs électromécaniques pilotant le système. Il commande le registre des sorties (commande des actionneurs) en fonction du registre des entrées (états des signaux envoyés par les capteurs) et de l'étape du programme en cours.
