Cellular automaton

A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling. A cellular automaton consists of a regular grid of cells, each in one of a finite number of states, such as on and off (in contrast to a coupled map lattice). The grid can be in any finite number of dimensions. For each cell, a set of cells called its neighborhood is defined relative to the specified cell. An initial state (time t = 0) is selected by assigning a state for each cell. A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood. Typically, the rule for updating the state of cells is the same for each cell and does not change over time, and is applied to the whole grid simultaneously, though exceptions are known, such as the stochastic cellular automaton and asynchronous cellular automaton. The concept was originally discovered in the 1940s by Stanislaw Ulam and John von Neumann while they were contemporaries at Los Alamos National Laboratory. While studied by some throughout the 1950s and 1960s, it was not until the 1970s and Conway's Game of Life, a two-dimensional cellular automaton, that interest in the subject expanded beyond academia. In the 1980s, Stephen Wolfram engaged in a systematic study of one-dimensional cellular automata, or what he calls elementary cellular automata; his research assistant Matthew Cook showed that one of these rules is Turing-complete. The primary classifications of cellular automata, as outlined by Wolfram, are numbered one to four.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (45)

Related people (14)

Related concepts (38)

Related courses (2)

Related lectures (23)

MATH-642: Artificial Life

We will study the emergence of life-like phenomena, such as locomotion, resilience,, reproduction, and evolution in mathematical models, in particular in discrete and continuous cellular automata, dev

BIOENG-455: Computational cell biology

Computer modelling is increasingly used to study dynamic phenomena in cell biology. This course shows how to identify common mathematical features in cell biological mechanisms, and become proficient

Real-time monitoring of single-cell secretion with a high-throughput nanoplasmonic microarray

Hatice Altug, Yen-Cheng Liu, Xiaokang Li, Saeid Ansaryan, Eduardo Romero Arvelo

Proteins secreted by cells play significant roles in mediating many physiological, developmental, and pathological processes due to their functions in intra/intercellular communication and signaling.

2022

Bio-Hybrid Systems for Ecosystem Level Effects

Francesco Mondada, Robert Matthew Mills, Rafael Botner Barmak, Martina Szopek, Jean-Louis Deneubourg

In a time marked by ecological decay and by the perspective of a severe backlash of this ecosystem decay and climate devastation onto human society, bold moves that employ novel technology to countera

MIT Press2021

Modeling biochemical reaction networks in complex intracellular environments

Daniel Robert Weilandt

Whether one aims to design treatments for diseases such as cancer or diabetes, engineer cells to produce valuable biochemicals sustainably, or to grasp the behavior of living organisms, it is essentia

EPFL2020

A New Kind of Science is a book by Stephen Wolfram, published by his company Wolfram Research under the imprint Wolfram Media in 2002. It contains an empirical and systematic study of computational systems such as cellular automata. Wolfram calls these systems simple programs and argues that the scientific philosophy and methods appropriate for the study of simple programs are relevant to other fields of science.

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves. It is Turing complete and can simulate a universal constructor or any other Turing machine.

The 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.

Covers file management in C++, including formatted sequential reading, input/output operations, and configuration files.

Explores the impact of thermal fluctuations at the cellular scale, emphasizing randomness in biological processes and the distribution of kinetic energy in gas molecules.

Covers the basics of Turing machines, including states, tape manipulation, and problem-solving capabilities.