W automacie komórkowym komórka jest automatem.
Definicja formalna Jeżeli przez oznaczymy regularną, uporządkowaną siatkę złożoną z jednakowych komórek o budowie zależnej od rozmiaru przestrzeni i od kształtu pojedynczej komórki, natomiast przez – skończony zbiór stanów, jaki może przyjąć komórka oraz przez – skończony zbiór sąsiadów, spełniający warunek:
a funkcję przejścia definiującą reguły ewolucji automatu w kolejnych krokach oraz dynamikę tych przejść zapiszemy jako:
to automat komórkowy definiujemy jako czwórkę:
Aby opis automatu komórkowego był pełny, niezbędne jest określenie warunków brzegowych i początkowych.
Definicja Edwarda Fredkina Podstawą jego definicji jest dwuwymiarowa, kwadratowa siatka, w której każda komórka jest opisana przez wektor pozycji: gdzie są indeksami kolumn i wierszy siatki. Stan każdej komórki w iteracji jest opisywany przez i może przyjmować wartości binarne 0 i 1.