{"id":2962,"date":"2021-11-09T06:24:27","date_gmt":"2021-11-09T06:24:27","guid":{"rendered":"https:\/\/alife.org\/?post_type=encyclopedia&p=2962"},"modified":"2022-12-13T14:58:23","modified_gmt":"2022-12-13T14:58:23","slug":"cellular-automata","status":"publish","type":"encyclopedia","link":"https:\/\/alife.org\/encyclopedia\/introduction\/cellular-automata\/","title":{"rendered":"Cellular Automata"},"content":{"rendered":"\n
A cellular automaton (plural: cellular automata) is composed of a grid of cells. Traditionally, cells can be in a finite number of discrete states, although some more modern variations on cellular automata have changed this rule. A set of global rules determine how cells transition from state to state as time advances. Often, these update rules depend on the state of nearby cells. Cellular automata are used to study a range of question in biology, physics, computer science, and complexity theory. <\/p>\n\n\n\n
Classically, all cellular automata are discrete systems with a finite number of states. Time steps are also discrete; at each time step, the next state for each cell is calculated. These state changes are then applied on the next time step. Cellular automata were first created by Stanislaw Ulam<\/a> and John von Neumann<\/a>, but did not become popular until John Conway created Conway’s Game of Life in the 1970’s. Conway’s Game of Life is still by far the most well known cellular automaton.<\/p>\n\n\n\n To facilitate their use in the study of complexity, Stephen Wolfram came up with a way of classifying them into different complexity classes <\/span>. These classes can be broadly described as follows:<\/p>\n\n\n\n Some class 4 cellular automata, including Conway’s Game of Life, have been shown to be capable of implementing a Turing machine. Thus, they are theoretically capable of performing any computation. That said, such behaviors generally must be built by hand as they are unlikely to emerge naturally.<\/p>\n\n\n\n Hybrid cellular automata pair a discrete grid with a continuous environment <\/span>. These models were originally developed (and are still primarily used) for studying cancer evolution. In this context, the discrete portion represents the cancer cells and the continuous portion represents a gradient of a relevant chemical. The cells in the discrete portion can affect the corresponding region of the continuous portion and vica versa. In most cases, there is a separation of time scales between the two portions of the model, with the continuous portion updating many times for every discrete time step in order to appropriately model diffusion.<\/p>\n\n\n\n\n
<\/span>Hybrid cellular automata<\/span><\/h1>\n\n\n\n
<\/span>Continuous cellular automata<\/span><\/h1>\n\n\n\n