通用細胞自動機

通用細胞自動機是一種細胞自動機，它像圖靈機一樣，展現出通用性。馮·諾依曼證明，由具有四個正交鄰居和 29 種可能狀態的單元格組成的自動機，能夠模擬圖靈機，對於大約 個單元格的某種配置 (Gardner 1983, p. 227)。

關於二維生命遊戲外全域細胞自動機是通用的證明概要由 Berlekamp、Conway 和 Guy (1982) 以及 Gosper (Gardner 1983, pp. 250-253) 獨立給出。大約在 2000 年，P. Rendell (Rendell, Adamatzky 2001) 在生命遊戲中顯式地實現了圖靈機。雖然 Rendell 的機器可以透過簡單地使其磁帶無限長而變成“真正”的通用計算機，但他既沒有注意到這一事實，也沒有提供通用圖靈機的實際構造。隨後，在 2002 年 11 月 11 日，P. Chapman 構建了一個生命遊戲模式，該模式實現了通用暫存器機的動作，從而明確證明了生命遊戲是通用的。

更令人驚訝的是，即使是一維細胞自動機也可以是通用的。Wolfram (2002, pp. 644-656) 給出了一個 19 色通用一維次近鄰細胞自動機的例子，其中使用 20 個單元格的塊來表示被模擬的細胞自動機中的每個單元格。上面的例子分別展示了 19 色通用自動機模擬規則 90 和規則 30 的前幾個步驟 (Wolfram 2002, pp. 646-647)。

Smith (1971) 表明，18 種顏色和最近鄰一維規則可以是通用的，Lindgren 和 Nordahl (1990) 構建了一個 7 色最近鄰通用細胞自動機。最令人驚奇的是，正如 Wolfram (2002, pp. 675-691) 所展示的那樣，兩種顏色和最近鄰規則足以在一維細胞自動機中產生通用性。特別是，雖然證明過程絕非易事，但規則 110基本細胞自動機是通用的 (Cook 2004)。

Gacs (2001) 已經證明，存在容錯通用細胞自動機，只要這些擾動足夠稀疏，它們模擬其他細胞自動機的能力就不會受到隨機擾動的阻礙。