Cellular Automaton – CA
In the Novel CyberKill, Cole uses CA to fit his code into the tiny nano-dust.
A cellular automaton is a collection of “colored” cells on agrid of specified shape that evolves through a number of discrete time steps according to a set of rules based on the states of neighboring cells. The rules are then applied iteratively for as many time steps as desired. von Neumann was one of the first people to consider such a model, and incorporated a cellular model into his “universal constructor.” Cellular automata were studied in the early 1950s as a possible model for biological systems (Wolfram 2002, p. 48). Comprehensive studies of cellular automata have been performed by S. Wolfram starting in the 1980s, and Wolfram’s fundamental research in the field culminated in the publication of his book A New Kind of Science (Wolfram 2002) in which Wolfram presents a gigantic collection of results concerning automata, among which are a number of groundbreaking new discoveries.
The Season 2 episode “Bettor or Worse” (2006) of the television crime drama NUMB3RS mentions one-dimensional cellular automata.
A CA does just one thing: You give it an input, and it produces an output. Give that output back to the program as input, and you’ve got a new output. And so on. Cellular automata are typically simple enough to be implemented in a line or two of code; yet from these simple instructions, repeated thousands of times, they can produce drastically complex behavior. The best-known CA is John Conway’sGame of Life. Before you decide that “Life” is too grand a name for a two-line computer program, play with thisJava applet.A cellular automaton, or CA, is a computer program—but not one like VisiCalc or Quake, designed with a specific purpose in mind. A CA does just one thing: You give it an input, and it produces an output. Give that output back to the program as input, and you’ve got a new output. And so on. Cellular automata are typically simple enough to be implemented in a line or two of code; yet from these simple instructions, repeated thousands of times, they can produce drastically complex behavior. The best-known CA is John Conway’s Game of Life. Before you decide that “Life” is too grand a name for a two-line computer program, play with this Java applet.
As simple as CAs are, they come in a daunting variety of flavors. Some of the programs produce very simple, easy-to-predict output; some produce results that look, to the naked eye, completely random. And others, such as the Game of Life, are somewhere in between, producing results that display visible structure and yet are extremely difficult to predict.
The theory of cellular automata is immensely rich, with simple rules and structures being capable of producing a great variety of unexpected behaviors. For example, there exist universal cellular automata that are capable of simulating the behavior of any other cellular automaton orTuring machine. It has even been proved by Gacs (2001) that there exist fault-tolerant universal cellular automata, whose ability to simulate other cellular automata is not hindered by random perturbations provided that such perturbations are sufficiently sparse.
