Ein zellulärer Automat ist ein Kristall aus Zellen, deren diskrete Zustände sich zeitlich verändern. Der Zustand im nächsten Zeitschritt ergibt sich durch eine deterministische Regel aus dem alten Zustand und dem Zustand der nächsten (evtl. auch übernächsten) Nachbarzellen. Eine Zelle verkörpert einen mesoskopischen Bereich eines physikalischen Gebietes. Alle Zellen sind gleich, evtl. mit Ausnahme von Randzellen.
Nach Wolfram [Wol86] haben zelluläre Automaten folgende Eigenschaften:
Die ersten drei Eigenschaften sichern die Fehlerfreiheit bei der Simulation und sollten nicht aufgegeben werden. Manche Forschergruppen arbeiten mit sog. locally coupled maps, das sind zelluläre Automaten mit kontinuierlichen Zuständen, was dann sinnvoll sein kann, wenn Rundungsfehler keine Rolle spielen.
Die übrigen fünf Eigenschaften können gegebenenfalls aufgelockert werden, solange die Berechenbarkeit erhalten bleibt. Für die Lösung auf Parallelrechnern scheint jedenfalls noch die räumliche Lokalität nützlich.