Editing Cellular automaton (section)

===Computer science, coding, and communication===
Cellular automaton processors are physical implementations of CA concepts, which can process information computationally. Processing elements are arranged in a regular grid of identical cells. The grid is usually a square tiling, or [[tessellation]], of two or three dimensions; other tilings are possible, but not yet used. Cell states are determined only by interactions with adjacent neighbor cells. No means exists to communicate directly with cells farther away.<ref>{{cite book | author=Muhtaroglu, Ali | title=Cellular Automaton Processor Based Systems for Genetic Sequence Comparison/Database Searching | chapter=4.1 Cellular Automaton Processor (CAP) | pages=62–74 | publisher=Cornell University |date=August 1996}}</ref> One such cellular automaton processor array configuration is the [[systolic array]]. Cell interaction can be via electric charge, magnetism, vibration ([[phonons]] at quantum scales), or any other physically useful means. This can be done in several ways so that no wires are needed between any elements. This is very unlike processors used in most computers today ([[Von Neumann architecture|von Neumann designs]]) which are divided into sections with elements that can communicate with distant elements over wires.

[[Rule 30]] was originally suggested as a possible [[block cipher]] for use in [[cryptography]]. Two-dimensional cellular automata can be used for constructing a [[pseudorandom number generator]].<ref>{{cite journal | first1=M. | last1=Tomassini | first2=M. | last2=Sipper | first3=M. | last3=Perrenoud | title=On the generation of high-quality random numbers by two-dimensional cellular automata | journal=IEEE Transactions on Computers | volume=49 | issue=10 | pages=1146–1151 | year=2000 | doi=10.1109/12.888056| s2cid=10139169 }}</ref>

Cellular automata have been proposed for [[public-key cryptography]]. The [[one-way function]] is the evolution of a finite CA whose inverse is believed to be hard to find. Given the rule, anyone can easily calculate future states, but it appears to be very difficult to calculate previous states. <!-- However, the designer of the rule can create it in such a way as to easily invert it.  Therefore, it is apparently a [[trapdoor function]], and can be used as a public-key cryptosystem.  The security of such systems is not currently known. --> Cellular automata have also been applied to design [[ECC memory|error correction codes]].<ref>{{cite journal | title=Design of CAECC - cellular automata based error correcting code | first1=D. Roy | last1=Chowdhury | first2=S. | last2=Basu | first3=I. Sen | last3=Gupta | first4=P. Pal | last4=Chaudhuri | journal=[[IEEE Transactions on Computers]] | volume=43 | issue=6 | date=June 1994 | doi=10.1109/12.286310 | pages=759–764}}</ref>

Other problems that can be solved with cellular automata include:

* [[Firing squad synchronization problem]]
* [[Majority problem (cellular automaton)|Majority problem]]