元胞自動機（pl.cellularautomata，縮寫為CA）是在自動機理論中研究的離散計算模型。元胞自動機也稱為元胞空間、曲面細分自動機、同構結構、元胞結構、曲面細分結構和迭代陣列。元胞自動機在各個領域都有應用，包括物理學、理論生物學和微觀結構建模。

元胞自動機由規則的元胞網格組成，每個元胞都處于有限數量的狀態之一，例如開和關（與耦合地圖格子相反）。網格可以是任意有限維數。對于每個像元，相對于指定像元定義一組稱為其鄰域的像元。通過為每個單元分配一個狀態來選擇初始狀態（時間t=0）。根據一些固定規則（通常是數學函數），創建新的一代（t增加1）它根據單元格的當前狀態及其附近單元格的狀態確定每個單元格的新狀態。通常，更新單元格狀態的規則對于每個單元格都是相同的，不會隨時間變化，并且同時應用于整個網格，盡管已知例外，例如隨機元胞自動機和異步元胞自動機.

這個概念最初是由斯坦尼斯拉夫·烏拉姆和約翰·馮·諾依曼在1940年代發現的，當時他們在洛斯阿拉莫斯國家實驗室工作。雖然在1950年代和1960年代被一些人研究，但直到1970年代和康威的生命游戲，二維細胞自動機，對該主題的興趣才擴展到學術界之外。1980年代，StephenWolfram對一維元胞自動機或他所謂的基本元胞自動機進行了系統的研究；他的研究助理MatthewCook表明，這些規則之一是圖靈完備的。Wolfram發表2002年的ANewKindofScience，聲稱元胞自動機在許多科學領域都有應用。這些包括計算機處理器和密碼學。

Wolfram概述的元胞自動機的主要分類編號為一到四。它們依次是模式通常穩定為同質性的自動機，模式演變成大部分穩定或振蕩結構的自動機，模式以看似混亂的方式演變的自動機，以及模式變得極其復雜并可能持續一段時間的自動機。很長一段時間，具有穩定的局部結構。最后一類被認為是計算通用的，或者能夠模擬圖靈機。

模擬二維??元胞自動機的一種方法是使用一張無限大的方格紙以及一組細胞要遵循的規則。每個方塊稱為一個“單元格”，每個單元格都有兩種可能的狀態，黑色和白色。單元格的鄰域是附近的，通常是相鄰的單元格。兩種最常見的鄰域類型是馮諾依曼鄰域和摩爾鄰域。前者以元胞自動機理論創始人的名字命名，由四個正交相鄰的元胞組成。后者包括馮諾依曼鄰域以及四個對角相鄰的單元格。對于這樣的單元格及其摩爾鄰域，有512(=29)種可能的模式。對于512個可能的模式中的每一個，規則表將說明中心單元格在下一個時間間隔是黑色還是白色。Conway'sGameofLife是該模型的流行版本。另一種常見的鄰域類型是擴展的馮諾依曼鄰域，它包括每個正交方向上兩個最近的像元，總共八個。這種規則系統的一般方程是kks，其中k是單元格的可能狀態數，而s是用于確定單元格下一狀態的相鄰單元格（包括要計算的單元格本身）的數量。因此，在具有摩爾鄰域的二維系統中，可能的自動機總數為229，或1.34×10154。

通常假設宇宙中的每個細胞都以相同的狀態開始，除了有限數量的處于其他狀態的細胞；狀態值的分配稱為配置。更一般地說，有時假設宇宙開始時被一種周期性模式覆蓋，只有有限數量的細胞違反了這種模式。后一種假設在一維元胞自動機中很常見。

Wolfram在ANewKindofScience和1980年代中期的幾篇論文中定義了四類，元胞自動機和其他幾個簡單的計算模型可以根據它們的行為分為四類。雖然早期的元胞自動機研究傾向于嘗試識別特定規則的模式類型，但Wolfram的分類是對規則本身進行分類的xxx次嘗試。按照復雜性的順序，這些類是：

• 第1類：幾乎所有初始模式都迅速演變為穩定、同質的狀態。初始模式中的任何隨機性都會消失。
• 第2類：幾乎所有初始模式都會迅速演變為穩定或振蕩的結構。初始模式中的一些隨機性可能會被過濾掉，但一些仍然存在。初始模式的局部變化往往保持局部。
• 第3類：幾乎所有初始模式都以偽隨機或混沌方式演化。任何出現的穩定結構都會被周圍的噪音迅速破壞。初始模式的局部變化往往會無限擴散。
• 第4類：幾乎所有初始模式都演變成以復雜而有趣的方式相互作用的結構，形成能夠長期存活的局部結構。2類穩定或振蕩結構可能是最終結果，但達到這種狀態所需的步驟數量可能非常大，即使初始模式相對簡單。初始模式的局部變化可能會無限擴散。Wolfram推測許多第4類元胞自動機（如果不是全部）都能夠進行通用計算。規則110和康威的生命游戲已經證明了這一點。

這些定義本質上是定性的，有一些解釋的空間。根據Wolfram的說法，“……對于幾乎任何一般分類方案，都不可避免地存在根據一個定義分配給一個類而根據另一個定義分配給另一個類的情況。元胞自動機也是如此：偶爾有規則……顯示一個類的一些特征和另一個類的一些特征。”Wolfram的分類根據經驗與元胞自動機輸出的壓縮長度的聚類相匹配。

受到Wolfram分類的啟發，已經有幾次嘗試將元胞自動機分類為形式嚴格的類。例如，Culik和Yu提出了三個明確定義的類（第四個類用于與這些中的任何一個都不匹配的自動機），它們有時被稱為Culik-Yu類；事實證明，這些成員的身份無法確定。Wolfram的第2類可以分為穩定（定點）和振蕩（周期）規則的兩個子組。

有4類動力系統的想法最初來自諾貝爾獎獲得者化學家IlyaPrigogine，他確定了這4類熱動力系統-(1)熱力學平衡系統，(2)空間/時間均勻系統，(3)混沌系統，以及(4)具有耗散結構的遠離平衡的復雜系統（參見Nicolis論文中的圖1（Prigogine的學生））。

如果對于元胞自動機的每個當前配置，都只有一個過去的配置（原像），那么元胞自動機是可逆的。如果將元胞自動機視為將配置映射到配置的函數，則可逆性意味著該函數是雙射的。如果元胞自動機是可逆的，那么它的時間反轉行為也可以描述為元胞自動機；這一事實是Curtis-Hedlund-Lyndon定理的結果，該定理是元胞自動機的拓撲特征。對于并非每個配置都有原像的元胞自動機，沒有原像的配置稱為伊甸園模式。

對于一維元胞自動機，存在用于確定規則是可逆還是不可逆的已知算法。然而，對于二維或多維元胞自動機，可逆性是不可判定的；也就是說，不存在將自動機規則作為輸入并保證正確確定自動機是否可逆的算法。JarkkoKari的證明與王瓦的平鋪問題有關。

可逆元胞自動機通常用于模擬氣體和流體動力學等物理現象，因為它們遵守熱力學定律。這種元胞自動機具有專門構造為可逆的規則。TommasoToffoli、NormanMargolus和其他人已經研究過這樣的系統。有幾種技術可用于顯式構建具有已知逆元的可逆元胞自動機。兩種常見的是二階元胞自動機和塊元胞自動機，兩者都涉及以某種方式修改元胞自動機的定義。雖然這樣的自動機不嚴格滿足上面給出的定義，但可以證明它們可以被具有足夠大的鄰域和狀態數量的傳統元胞自動機模擬，因此可以被認為是傳統元胞自動機的子集。相反，已經表明每個可逆元胞自動機都可以由塊元胞自動機模擬。

一種方法是使用矩形（立方體等）網格以外的其他東西。例如，如果平面平鋪有規則六邊形，這些六邊形可以用作單元格。在許多情況下，生成的元胞自動機等效于具有特殊設計的鄰域和規則的矩形網格的元胞自動機。另一種變化是使網格本身不規則，例如Penrose瓷磚。

此外，規則可以是概率性的，而不是確定性的。這種元胞自動機稱為概率元胞自動機。對于時間t的每個模式，概率規則給出了中央單元在時間t+1轉換到每個可能狀態的概率。有時使用更簡單的規則；例如：“規則是生命游戲，但在每個時間步上，每個單元格有0.001%的概率會轉換為相反的顏色。”

鄰里或規則可能會隨著時間或空間而改變。例如，最初單元格的新狀態可以由水平相鄰的單元格確定，但對于下一代，將使用垂直單元格。

在元胞自動機中，一個元胞的新狀態不受其他元胞的新狀態影響。這可以改變，例如，一個2x2的單元格可以由它自己和與其相鄰的單元格確定。

連續空間自動機具有連續的位置。位置的狀態是有限數量的實數。時間也是連續的，狀態按照微分方程演化。一個重要的例子是反應擴散紋理，這是艾倫圖靈提出的微分方程，用于解釋化學反應如何在斑馬上產生條紋和豹子上的斑點。當這些被元胞自動機逼近時，它們通常會產生相似的模式。MacLennan將連續空間自動機視為計算模型。

有一些已知的連續空間自動機的例子，它們表現出類似于生命游戲中的滑翔機的傳播現象。

圖重寫自動機是基于圖重寫系統的元胞自動機的擴展。

組合自動機功能通過檢查奇數/偶數索引對是否等于排列X。如果是，則返回規則字符串的X（例如：“120012101”）。這些CA與磚墻社區合作。這些CA類型也像邏輯門一樣。例如，當初始狀態是單個居中單元時，組合中XOR門的等效項會生成謝爾賓斯基三角形。

最簡單的非平凡元胞自動機是一維的，每個元胞有兩種可能的狀態，元胞的鄰居定義為它兩側的相鄰元胞。一個單元和它的兩個鄰居形成了一個由3個單元組成的鄰域，因此一個鄰域有23=8種可能的模式。規則包括為每個模式決定單元格在下一代中是1還是0。那么有28=256條可能的規則。

一維元胞自動機的規則決定下一代的方式的動畫。

這256個元胞自動機一般用它們的Wolfram代碼來指代，這是Wolfram發明的一種標準命名約定，它為每個規則賦予一個從0到255的數字。多篇論文對這256個元胞自動機進行了分析和比較。在第30條和第110元胞自動機是特別有趣。下圖顯示了當起始配置由1（在每個圖像的頂部）和0包圍時的歷史記錄。每一行像素代表自動機歷史中的一代，t=0是最上面一行。每個像素為0為白色，1為黑色。