鄔舒雯 熊明

1 引言

元胞自動機（Cellular Automata,CA）是一類時間和空間離散的數(shù)學(xué)系統(tǒng)，其特征是局部相互作用和內(nèi)在的并行演化形式。元胞自動機這一概念起源于馮諾依曼（von Neumann）在“自動機的一般邏輯理論”（The General and Logical Theory of Automata）中所提出的二維自復(fù)制自動機系統(tǒng)。（參見[12]）元胞自動機結(jié)構(gòu)、規(guī)則簡單，但能產(chǎn)生復(fù)雜的行為模式，因此作為一類復(fù)雜系統(tǒng)的最簡單數(shù)學(xué)表示，被廣泛應(yīng)用于交通運輸、計算機科學(xué)、人工智能、生物科學(xué)、物理學(xué)等眾多學(xué)科領(lǐng)域。

近年來，文[9]提出了能夠?qū)⒃詣訖C與自指語句相聯(lián)系的觀點。文中提出元胞自動機的演化過程與自指語句的修正過程這兩個動態(tài)過程在本質(zhì)上是相同的，這種相似性，使我們能夠?qū)⒃詣訖C和自指語句，一個屬于計算機科學(xué)和一個屬于邏輯學(xué)的兩個不同研究領(lǐng)域的理論概念相互聯(lián)系起來進行研究。文[9]主要研究了初等元胞自動機及其相關(guān)聯(lián)的自指語句，從初等元胞自動機誘導(dǎo)出若干類悖論，并根據(jù)自指語句的特征對初等元胞自動機給出了一個分類。

文[9]用來分析自指語句的一個關(guān)鍵概念是修正序列，這是來自于修正理論（參見[5,6]）的基本概念。在這個理論中，自指語句分階段按照修正規(guī)則與極限規(guī)則進行賦值，每個語句都可建立一個動態(tài)的賦值過程，這樣的過程即為修正過程。本文基于文[9]提出的理論，將目光投向到更為復(fù)雜的二維元胞自動機系統(tǒng)中，研究一類特殊的馮諾依曼型元胞自動機及其相關(guān)的自指語句。我們嘗試從前者給出一些悖論，并對此類馮諾依曼型元胞自動機在演化過程方面的特征進行邏輯學(xué)視角的分析。

本文采用文[9]中表達自指語句的形式語言，即帶有一元謂詞符號T的一階算術(shù)語言（LT）。對此語言中的語句的哥德爾數(shù)同時也表示對應(yīng)的數(shù)字符。因而，當(dāng)T表示真謂詞時的意思是C是真的。

本文結(jié)構(gòu)如下：第二節(jié)將介紹文[9]在初等元胞自動機與自指語句的主要思想，為本文的分析奠定理論依據(jù)；第三節(jié)引入馮諾依曼型元胞自動機的基本概念，并給出對應(yīng)的自指語句的表達方式；第四節(jié)根據(jù)[9]提出的方法，給出尋找此類元胞自動機演化過程中不動點的方法。然后，第五節(jié)將進一步對馮諾依曼型元胞自動機不動點的表現(xiàn)性質(zhì)進行分析，并通過引入說謊者悖論的相關(guān)性質(zhì)進行比較，最后一節(jié)將總結(jié)前面所做的相關(guān)內(nèi)容，并嘗試給出一種馮諾依曼型元胞自動機的分類。

2 初等元胞自動機和自指語句

元胞自動機是由無數(shù)個排列在網(wǎng)格結(jié)構(gòu)的具有自身狀態(tài)值的元胞構(gòu)成，每個元胞的狀態(tài)值都是根據(jù)一組明確的規(guī)則隨時間的變化確定性地演變，并且這些規(guī)則涉及相鄰元胞的狀態(tài)值。在數(shù)學(xué)上，常把元胞自動機表示為由元胞狀態(tài)、鄰域和演化規(guī)則構(gòu)成的三元組〈S,r,f〉，其中S是狀態(tài)的有限集，r是鄰域的半徑，f是迭代函數(shù)（也稱為局部函數(shù)）。

作為元胞自動機的基本單位，元胞分布在一定維數(shù)的空間網(wǎng)格中，此網(wǎng)絡(luò)結(jié)構(gòu)可向各個維度無限延展而形成所謂的“元胞空間”。根據(jù)元胞空間的維數(shù)，元胞自動機可以劃分一維、二維及更高維的元胞自動機。如果把一維元胞自動機看作是元胞在一條帶子上進行演化的自動機，那么二維的元胞在一個平面上進行演化的自動機。在前一類中，領(lǐng)域半徑為1 且狀態(tài)集為{0,1}最為簡單且基本，被稱為初等元胞自動機，它與自指語句之關(guān)聯(lián)是本文研究之基礎(chǔ)。在后一類中，則有本文將詳加研究的Totalistic 的馮諾依曼型（von Neuman Neighborhoods）元胞自動機1除馮諾依曼型外，二維中典型者還有摩爾型（Moore Neighborhoods），廣為人知的康威（John Conway）生命游戲就是屬于摩爾型，詳情參見[4]。，其解釋見下一節(jié)。

本節(jié)主要解釋初等元胞自動機與自指語句如何發(fā)生關(guān)聯(lián)。初等元胞自動機中的元胞均勻地分布在一條兩段可無限延伸的帶子上，因此每個格子以由整數(shù)索引：Ci,i ∈Z。在每個離散時間階段‘t’，元胞Ci在t階段的狀態(tài)Ci(t)必為布爾值0和1（圖示用白格和黑格表示）之一。Ci的兩個最近的鄰居表示為Ci-1（左鄰居）和Ci+1（右鄰居）。Ci在t+1 階段的狀態(tài)由它與它的兩個鄰居在步長t的狀態(tài)決定。決定方式由演化規(guī)則（或迭代函數(shù)）來規(guī)定。例如，圖2-1 給出了一種演化規(guī)則。在一定的初始狀態(tài)下，每個格子的演化是唯一確定的。因此，可用不同的演化規(guī)則來區(qū)分不同的元胞自動機。圖2-1 對應(yīng)的自動機被命名為ECA 452文[1]中使用“ECA n”（或“規(guī)則n”）來表示一個Wolfram 數(shù)為n 的初等元胞自動機。Wolfram 數(shù)是指根據(jù)Wolfram 給出的編碼規(guī)則對元胞自動機進行編碼所得的數(shù)字，詳情參見[14]，第65 頁。。

每個演化規(guī)則本質(zhì)上是一個有三個變元的布爾函數(shù)。例如，圖2-1 實則是一個三變元的真值表，它正是ECA 45 的迭代函數(shù)f的表格表示。f(x,y,z)的布爾表達式為x⊕(y ∨?z)。由此，ECA 45 的演化可由公式Ci(t+1)=Ci-1(t)⊕(Ci(t)∨?Ci+1(t))3詳情可參見https://www.wolframalpha.com/input/?i=rule+45，該網(wǎng)站給出了所有初等元胞自動機對應(yīng)的布爾表達式。確定。

正如前文提到，文[9]把初等元胞自動機關(guān)聯(lián)到自指語句?；镜乃枷胧牵瑢τ诿總€初等元胞自動機，若其演化式為，則可定義自指語句的無限集{Ci|i ∈Z}，其中，這里每個Ci不再表示格子，而是一個語句，它所斷定者正是語句Ci-1,Ci,Ci+1按f組合的那種真值情況。例如，ECA 45 的對應(yīng)的自指語句中，每個都斷定要么語句Ci-1為真，要么或者語句Ci為真，或者語句Ci+1不為真。需要說明的是，元胞自動機的演化式可表達為布爾表達式對于當(dāng)前的研究頗為重要，因為當(dāng)前之研究與自指語句密不可分，而自指語句的表達必須借助布爾公式。布爾表達式對初等元胞機順理成章，但對其他卻未必，這一點在下一節(jié)將會顯現(xiàn)出來。

初等元胞自動機與對應(yīng)的自指語句的一個基本關(guān)聯(lián)是：前者的演化過程與后者的所謂修正過程本質(zhì)上是相同的。給定帶子中每個元胞的初始狀態(tài)，則每個初等元胞自動機在每個時間步長都唯一地給出每個元胞的狀態(tài)，各個時間步長的狀態(tài)演變就構(gòu)成了一個演化過程。而修正過程來自于一個稱為語義真理論的邏輯學(xué)領(lǐng)域，其中T預(yù)設(shè)的表示是真謂詞“是真的”，其外延也按照一定的過程來演化，過程中每個階段的外延都由上一階段為真的語句構(gòu)成。在此演化中，語句，尤其是上面提到的那些自指語句，因其表達式中含有T，其真值會隨著階段的改變而發(fā)生改變。這樣，在此過程中，自動機中每個元胞對應(yīng)的語句的真值也形成了一個演化過程，此演化過程被稱為修正過程。（參見[5,6]）

關(guān)于初等元胞自動機的演化過程和對應(yīng)自指語句的修正過程以及這兩種過程如何對應(yīng)，具體細節(jié)可參見[9]。后面的討論將直接利用初等元胞自動機上已經(jīng)建立的一些事實，我們將把二維的元胞自動機的演化過程與對應(yīng)的自指語句的修正過程也視為等同的。因此，正如[1]已經(jīng)證明的那樣，對任意初等元胞自動機，其對應(yīng)的自指語句集是悖論的，當(dāng)且僅當(dāng)此自動機的演化過程沒有不動點。對于二維的自動機，當(dāng)知道其演化過程沒有不動點，我們將直接指出其所對應(yīng)的自指語句集也是悖論的4不動點之規(guī)定將在節(jié)5 針對二維情況給出規(guī)定，悖論語句的修正過程定義來自于[5,6]，可參見[9]。。

3 馮諾依曼型元胞自動機的邏輯表達式

馮諾依曼型元胞自動機作為二維元胞自動機中常見的一種類型，是指元胞領(lǐng)域是包含目標(biāo)元胞周圍（上下左右）四個正交元胞的集合。我們可用矩陣形式表示馮諾依曼型元胞自動機，其中元胞是均勻排列的，并由整數(shù)索引：Ci,j,i,j ∈Z。由Ci,j+1，Ci,j-1，Ci-1,j，Ci+1,j表示目標(biāo)元胞上下左右四個鄰居。在每個離散時間階段t，我們使用表示元胞Ci,j在階段t的狀態(tài)，由Ci,j表示的t階段的結(jié)構(gòu)是一個無限矩陣序列。本文研究狀態(tài)集為{1,0}（分別通過黑白格子表示），領(lǐng)域半徑為1 的最基礎(chǔ)的Totalistic 規(guī)則（總和型），其解釋形式可表示為：

目標(biāo)元胞的狀態(tài)是根據(jù)迭代規(guī)則和其鄰域元胞狀態(tài)隨時間變化的。我們用顏色的從淺到深來分別對應(yīng)f從0 到5 的值，用tn（tn ∈{0,1}）表示在時間‘t+1’下相應(yīng)的子規(guī)則Tn決定的目標(biāo)元胞的值，可將T 型元胞自動機規(guī)則進行圖示化，如圖3-1 所示5所有此類規(guī)則圖示都由電腦軟件Wolfram Mathematica 12 繪制而成，不再進行一一說明。的馮諾依曼型元胞自動機（下文簡稱T 型元胞自動機）。同時，根據(jù)Wolfram 提出的編碼規(guī)則，我們也可以對其進行相應(yīng)的編碼t5·25+t4·24+…+t0·20，所得的編碼數(shù)也稱為Wolfram 數(shù)。因此，我們共有26個T 型元胞自動機，用“Rn”（或“規(guī)則n”）來表示一個Wolfram 數(shù)為n的自動機。

為了更好地對T 型元胞自動機進行研究，我們需要將其演化規(guī)則進行形式化表達，代數(shù)表達式是其迭代函數(shù)最簡單的表現(xiàn)形式之一。例，R31 元胞自動機的代數(shù)表達式為：

圖3-1:馮諾依曼型元胞自動機的迭代規(guī)則

顯然，用代數(shù)表達式可以直接表示T 型元胞自動機的迭代函數(shù)，但在邏輯語言中不使用加法，因此這種形式化表達方式不能直接地與邏輯自指語句聯(lián)系起來。所以，需要進一步將其轉(zhuǎn)化為邏輯符號進行表示。由上文我們已經(jīng)知道對初等元胞自動機演化規(guī)則編寫對應(yīng)的布爾函數(shù)的值再進行簡單的合?。ɑ蛭鋈。?，就可以得到相應(yīng)的自指語句形式，如ECA 45 的邏輯表達式。因此，我們對每一條T 型元胞自動機的子規(guī)則Tn編寫相應(yīng)的布爾函數(shù)的值，從而試圖將自動機的迭代函數(shù)用邏輯表達式進行表達。

由(1)式已知，每個目標(biāo)元胞的“t+1”狀態(tài)值是由“t”狀態(tài)下包括目標(biāo)元胞在內(nèi)的周邊共五個元胞的值共同決定的。因為本文研究的是狀態(tài)值為{0,1}布爾值的T 型元胞自動機且f ∈[0,5]，因此可得決定元胞狀況的子規(guī)則的情形由25種情形構(gòu)成。由圖3-1 可知，T1規(guī)則下包含5 種情形，而每一個Tn規(guī)則將分別有其相對應(yīng)的情形。對此，我們假設(shè)所求迭代函數(shù)的邏輯表達式為A（表3-1 中A為R31 對應(yīng)下的取值，后文中將進一步說明），對決定A所有可能值的情況如表3-1 所列。

如表3-1 所示，我們對滿足Totalistic 規(guī)則的迭代函數(shù)的每種相應(yīng)可能情形進行編碼，從而將其對應(yīng)到每一條Tn規(guī)則下：顯然，T0規(guī)則只對應(yīng)著1 情形；T1規(guī)則分別對應(yīng)著2、3、5、9、17 情形；T2規(guī)則對應(yīng)4、6、7、10、11、13、18、19、21、25 情形；T3規(guī)則對應(yīng)8、12、14、15、20、22、23、26、27、29；T4規(guī)則對應(yīng)16、24、28、30、31 情形；T5規(guī)則對應(yīng)32 情形。每個T 型元胞自動機由每條子規(guī)則Tn共同決定，而每條Tn規(guī)則則能夠給上述真值表賦予相對應(yīng)的真值。因此，我們可以根據(jù)元胞自動機的演化規(guī)則所知道的A值，反解真值表，從而得到每個Totalistic 規(guī)則的邏輯表達式。

表3-1:決定邏輯表達式A 的所有真值表達形式

圖3-2:馮諾依曼型元胞自動機R31 的迭代規(guī)則

讓我們以R31 元胞自動機為例，說明根據(jù)真值表3-1 如何求得其邏輯表達式。R31 的T 型元胞自動機演化規(guī)則如圖3-2 所示，有且僅有t5=0，因此我們可得A的取值如表3-1 所示。由表可得，僅有在32 情形下，A的值為0，因此根據(jù)該真值表求解可得A的邏輯表達式如下：

因為在R32 規(guī)則下A的值為0 的情形較少，為了簡潔，我們可采取對A值為0 的情形先析取再合取的方式；同理，當(dāng)A的值為1 的情形較少時，我們可采取先合取再析取的方式。顯然，(3)式就是T 型元胞自動機R31 的迭代函數(shù)表示式，即：

并且，無論是任意一個Rn元胞自動機，我們都可以通過這樣的方法求得其邏輯表達式。那么，根據(jù)R31 的邏輯表達式，我們可以得到由其導(dǎo)出的自指語句集{Ci,j|i,j ∈Z}，Ci,j的定義是由下列語句得到：

4 尋找不動點

我們將[9]已證明的命題（[9]，命題3.2）進行擴展可得，如果T 型元胞自動機的任意演化序列沒有不動點，那么{Cx,y|x ∈Z,y ∈Z}是悖論的。那么，如何判斷T 型元胞自動機是否有不動點，如果有的話，它的表現(xiàn)形式又是怎樣的？T 型元胞自動機的不動點應(yīng)該如何確立？文[9]為確定初等元胞自動機的不動點提出了一種樹狀圖方法，下面把這種方法進行推廣以便能夠處理馮諾依曼型元胞自動機的不動點。在此，我們以R31 為例來介紹這種方法。在上一節(jié)，我們已知R31迭代規(guī)則的邏輯表達式為：

結(jié)合兩種情形，為了直觀，做T 型元胞自動機R31 不動點規(guī)律的樹狀圖，如圖4-1 所示。因此，綜上所述，我們可以得出在以R31 為例的情況下，發(fā)現(xiàn)該自動機沒有不動點。同理可證，在剩下的63 個T 型元胞自動機下，R1 元胞自動機也沒有不動點，后續(xù)也將進一步驗證。

圖4-1:馮諾依曼型元胞自動機R31 的不動點規(guī)律

上述以R31 為例簡單地介紹了對于T 型元胞自動機的不動點，應(yīng)該通過怎樣的一種方法去尋找。對于沒有不動點的元胞自動機，我們應(yīng)用上述的方法，可以很清晰地進行相應(yīng)的判斷。而當(dāng)對存在不動點的元胞自動機應(yīng)用上述方法時，我們會發(fā)現(xiàn)，因為T 型元胞自動機二維空間的性質(zhì)，情形復(fù)雜多變。通過筆者對T型元胞自動機的研究發(fā)現(xiàn)，對于滿足出現(xiàn)不動點的情形可以通過相應(yīng)的子規(guī)則進行組合構(gòu)成形成不動點的全局條件。為了讓讀者們更加清晰的理解，以R3 元胞自動機為例，并試圖通過這種方式得到獲得R3 元胞自動機不動點的規(guī)律性的元胞狀態(tài)。

根據(jù)圖4-2 所示的尋找不動點的樹狀圖，具體的情形分析同R31 相似，我們就不過多筆墨進行一一分析。通過圖4-2，當(dāng)C0,0(k)=1 時，只有T1條件才能滿足，即周邊元胞狀態(tài)都為0 的情形，此時我們可以回到當(dāng)C0,0(k)=0 的情況進行分析。當(dāng)C0,0(k)=0 時，雖然通過T4、T3和T2條件，我們都能得到該狀態(tài)，但在進行下一階段時，T3和T2條件（兩種分布下的其中一種情形）下，狀態(tài)為0 的元胞就找不到能滿足當(dāng)前狀態(tài)的條件，因為由圖4-2 我們知道當(dāng)狀態(tài)為1 的元胞出現(xiàn)時，其周邊狀態(tài)必然為0，所以這兩個路徑下的情況時不成立的。此時在狀態(tài)為0 的目標(biāo)元胞下，僅有T2條件和T4條件的路徑滿足。而當(dāng)在T4條件下時，目標(biāo)元胞周邊狀態(tài)都變?yōu)?，此時就能全部落回C0,0(k)=1 的情形下，那么就可以得到由條件…T1-T4-T1-T4…的循環(huán)路徑構(gòu)成的不動點，即0、1 交替出現(xiàn)的元胞狀態(tài)；而一旦滿足該條件下的不動點，則其出現(xiàn)的情形必然是在全局狀態(tài)下都滿足該條件，也就是說在二維平面空間下都滿足這個條件的R3 自動機才能出現(xiàn)不動點。因此，在T1-T4全局條件下，我們可以得到如圖4-5（左）所示矩陣分布的不動點。同樣的，顯然同時滿足T1→1，T4→0 的元胞自動機要存在該全局條件下分布的不動點，具體見表4-1。

圖4-2:馮諾依曼型元胞自動機R3 的不動點規(guī)律

圖4-3:滿足馮諾依曼型元胞自動機的全局條件

根據(jù)上述方法，我們發(fā)現(xiàn)當(dāng)存在能構(gòu)成從0-1 的狀態(tài)變化條件循環(huán)時，我們就可以獲得一個由全局條件決定下的不動點，而滿足這樣要求的條件除了上面已經(jīng)說明的，還有T2→1 和T3→0，其循環(huán)條件如圖4-3 所示。因此，在T2→1和T3→0 組合條件下，有24個馮諾依曼型元胞自動機具有滿足該全局條件下的不動點，具體見表4-1。

在前文中，我們已經(jīng)通過采用確定不動點的方法，發(fā)現(xiàn)了在能夠構(gòu)成從1 到0 下的循環(huán)狀態(tài)的情況下，可以得到形成不動點的全局條件。而除此之外，還有一種滿足嵌套關(guān)系的全局條件能夠構(gòu)造不動點的全局狀態(tài)，接下來將以R8 為例進行介紹。具體的不動點樹狀圖展開方法同上述相同，如圖4-4 所示。

圖4-4:馮諾依曼型元胞自動機R8 的不動點規(guī)律

在T3→1 和T1→0 條件下，可以發(fā)現(xiàn)其元胞狀態(tài)形式具有重疊部分，我們可以通過相應(yīng)的嵌套，根據(jù)其重疊部分出現(xiàn)的規(guī)律排列，即若干個的一列（行）1 和兩列（行）0 自由組合，從而形成不動點的全局狀態(tài)，同樣的在T3→1 和T2→0 條件下也能形成該自動機不動點的相應(yīng)全局狀態(tài)，即若干個的一列（行）1 和一列（行）0 自由組合。根據(jù)這兩個全局條件，我們可以構(gòu)造出R8 自動機的不動點,圖4-5（右）為其中一種隨機組合情況，根據(jù)該條件，R8 自動機有無數(shù)個不動點。

圖4-5:滿足馮諾依曼型元胞自動機R3（左）和R8（右）的不動點分布矩陣

同樣的，在T3→1 和T1→0、T3→1 和T2→0，也分別有24個T 型元胞自動機具有滿足該全局條件下的不動點，具體由下表3-9 所列。同理所得，T4→1和T1→0 以及T4→1 和T2→0 這兩組組合，也能通過嵌套關(guān)系，得到相應(yīng)T型元胞自動機不動點出現(xiàn)的組合規(guī)律，分別為若干個的兩列（行）1 和兩列（行）0 的自由組合及若干個的一列（行）1、一列（行）0 和一列（行）1 的自由組合，滿足相對應(yīng)條件的元胞自動機也由下表4-1 所列。

表4-1:出現(xiàn)不動點性質(zhì)的組合規(guī)律

5 馮諾依曼型元胞自動機、說謊者悖論和Curry 悖論

由前文可知，文[9]已經(jīng)證明沒有不動點的元胞自動機演化序列誘導(dǎo)的自指集{Ci|i ∈Z}是悖論的。那么，R1 和R31 馮諾依曼型元胞自動機誘導(dǎo)的自指集肯定也是悖論的。在對這些沒有不動點的馮諾依曼型元胞自動機進一步的分析前，我們先來看看最簡單的一種語義悖論——說謊者悖論。（[7]）一般下列形式的語句，通常被稱為說謊者悖論:

當(dāng)我們對語句(7)賦值為真時，那么其表達的內(nèi)容是假的，而當(dāng)我們賦值為假時，其表達的內(nèi)容又是真的；簡而言之，無論對語句(7)賦予哪個值，都會造成自身的相互矛盾，因此這樣形式的悖論，我們稱之為說謊者悖論，也是廣為人知的悖論之一。

當(dāng)我們用γ表示語句(7)時，那么說謊者悖論可形式化為：根據(jù)古納塔和貝爾納普的修正理論，其修正序列不存在不動點；同時，赫茲伯格證明了這樣的悖論性語句雖然不能保證收斂或具有不動點，但在修正過程穩(wěn)定后會有穩(wěn)定和被認為是“固定間隔”的無休止重復(fù)。（[8]）所以像包含說謊者悖論這樣的悖論性語句，其修正序列雖然不會出現(xiàn)不動點，但它會出現(xiàn)周期型循環(huán)的變化規(guī)律，從而可以得到說謊者悖論的動態(tài)修正過程。

圖5-1:馮諾依曼型元胞自動機R1 的不動點規(guī)律

同上所述，我們從假設(shè)X0開始，來對所有n ≥0 的Xn進行歸納定義：首先，我們以空集X0作為修正序列的起始值，有因此我們可以得到VX0(γ)=1。所以，有γ ∈X1。此時，我們可得顯然又有VX1(γ)=0，那么，以此類推，用數(shù)學(xué)歸納法我們可以證明：當(dāng)n為偶數(shù)時，VXn(γ)=1；當(dāng)n為奇數(shù)時，VXn(γ)=0。將所得的說謊者悖論修正過程如下表5-1 所示：

此時，我們把目光轉(zhuǎn)回沒有不動點的馮諾依曼型元胞自動機，試圖分析其誘導(dǎo)所得的自指集具備的悖論性質(zhì)。讓我們以R1 馮諾依曼型元胞自動機為例進行分析，獲得不動點規(guī)律樹狀圖的分析過程與第三節(jié)R31 馮諾依曼型元胞自動機相似，就不過多闡述。如圖5-1 所示，顯然R1 自動機沒有不動點。

表5-1:說謊者悖論的修正過程

圖5-2:馮諾依曼型元胞自動機R1 演化規(guī)則

我們根據(jù)R1 元胞自動機的圖示化規(guī)則（如圖5-2 所示），可求得其演化規(guī)則的邏輯表達式為：

由式(8)可得，當(dāng)我們對公式右邊x賦值為1 時，f(x)的值為0；當(dāng)我們對公式左邊f(xié)(x)賦值為1 時，公式左邊x的值必然為0。根據(jù)元胞自動機不動點的表達式所以有f(x)=x，與上述分析相矛盾。同時，我們可以發(fā)現(xiàn)這樣的一個矛盾性質(zhì)的R1 元胞自動機同我們說謊者悖論的性質(zhì)具有同樣迭代周期。無論其初始狀態(tài)的分布規(guī)律如何，在經(jīng)歷有窮步的迭代后，總會落入0-1 的迭代周期中，而這種迭代周期恰恰也是對應(yīng)著說謊者悖論的一個修正過程。這樣的情況下，我們可以說R1 元胞自動機與我們的說謊者悖論的修正序列保持著一致的動態(tài)變化過程。因此，我們也可將其稱作具有說謊者悖論性質(zhì)的馮諾依曼型元胞自動機。

在前文中，我們已對不存在不動點的R1 的Totalistic 型馮諾依曼元胞自動機的悖論性質(zhì)進行了探討。同時，我們在第4 節(jié)中，已經(jīng)證明了R31 的T 型元胞自動機也是沒有不動點的，換句話說，也具有某種悖論的性質(zhì)。在進行探討之前，我們先引入Curry 悖論。

Curry 悖論首次出現(xiàn)在H.B.Curry 在“組合邏輯”中的悖論式組合的討論中（[1,2]），隨后被Fitch 作為一種集合論悖論在其文章中出現(xiàn)。（[3]，第107-108 頁）隨后，L?b 根據(jù)Curry 悖論的性質(zhì)，構(gòu)建了其勒布定理證明的關(guān)鍵自指語句。（[10]）

Curry 悖論的語句形式，可被視為如下：

如果將B 視作語句(9)，可將其形式化為：

等式左邊的B僅在等式右邊中B為真，A為假的條件下為假，此時，就產(chǎn)生了矛盾。與此同時，當(dāng)?shù)仁阶筮厼檎鏁r，無論A是什么，A都為真，這就是L?b 定理證明的關(guān)鍵，在此我們只關(guān)注B語句產(chǎn)生矛盾的情況。因此，語句B形式的悖論被稱為Curry 悖論。

對于Curry 悖論，我們由公式（10）可以發(fā)現(xiàn)，當(dāng)A為假命題時，語句B的結(jié)構(gòu)等價于說謊者悖論。因此，同說謊者悖論一樣，根據(jù)修正理論，我們也可以得到相應(yīng)的修正序列，如表5-1 所示。

表5-1:Curry 悖論的修正過程

由第3 節(jié)，我們可得由其R31 誘導(dǎo)所得的自指語句集{Ci,j|i,j ∈Z}，如下所示：

由邏輯等價替換，可得：

由公式(12)可以發(fā)現(xiàn)，R31 元胞自動機的自指語句形式和Curry 悖論有著異曲同工之處。即，當(dāng)我們將Ci,j視為語句當(dāng)作A，那么可以發(fā)現(xiàn)它們有著相同的形式結(jié)構(gòu)。有趣的是，根據(jù)我們在第四節(jié)中已經(jīng)證明的，R31 元胞自動機不存在不動點，也就是悖論的。

根據(jù)Curry 悖論的修正過程和R31 的迭代規(guī)則，我們可以發(fā)現(xiàn)R31 元胞自動機也有著與Curry 悖論相同的迭代周期。因此，我們可以把這樣子的元胞自動機稱作，具有Curry 悖論性質(zhì)的元胞自動機。

6 結(jié)論

現(xiàn)在讓我們對26個T 型元胞自動機誘導(dǎo)的自指語句相應(yīng)的不動點形式進行分析。首先，我們已經(jīng)證明了R1 和R31 元胞自動機是沒有不動點的，那么現(xiàn)在我們就剩下62 個T 型元胞自動機。同時，我們已經(jīng)知道在具有T1→1 和T4→0、T2→1 和T3→0、T3→1 和T1→0、T3→1 和T2→0、T4→1 和T1→0 以及T4→1 和T2→0 這六種組合情形之一的T 型元胞自動機可以具有無數(shù)個不動點，那么在剩下的62 個自動機中排除這六種組合的情形，就只剩下6 個T 型元胞自動機，分別為R0、R30、R32、R33、R62、R63。顯然，其中R0 和R63 有且僅有唯一的不動點，且其不動點分別是0 和1。如果迭代函數(shù)具有“T5→1”或“T0→0”的元胞自動機，顯然至少有一個不動點，那么R30 和R33 至少存在一個不動點；如果迭代函數(shù)具有“T5→1”和“T0→0”的元胞自動機，顯然R32和R62 至少有兩個不動點。通過尋找不動點的樹狀圖方法驗證可得，R30 和R33有且僅有一個不動點，而R32 和R62 有且僅有兩個不動點。

根據(jù)前面對T 型元胞自動機的分析，在這我們可以根據(jù)由形式化馮諾依曼型元胞自動機的演化序列得到的不動點的特征，對26個馮諾依曼型元胞自動機進行分類，并列表如下：

表6-1:馮諾依曼型元胞自動機的分類

第一類T 型元胞自動機是沒有不動點的，在其任意的初始狀態(tài)下，這些元胞自動機的演化序列都不會出現(xiàn)不動點，這樣子的T 型元胞自動機我們也可以稱作悖論性的元胞自動機，其中R1 元胞自動機呈現(xiàn)說謊者悖論性質(zhì)，而R31 與邏輯上的Curry 悖論有著相類似的結(jié)構(gòu)；第二類T 型元胞自動機是有且僅有一個不動點的，即全局狀態(tài)值全為0，除此之外的任意狀態(tài)下該自動機都不能達到不動點的狀態(tài)，例如，R0 只具有不動點0；同理，第三類T 型元胞自動機是有且僅有一個不動點的，即全局狀態(tài)值全為1，除此之外的任意狀態(tài)下該自動機都不能達到不動點的狀態(tài)；第四類是有且僅有兩個不動點的，即全局狀態(tài)值全為0（或1），除此之外的任意狀態(tài)下該自動機都不能達到不動點的狀態(tài)；而最后一類是具有無數(shù)個不動點的馮諾依曼型元胞自動機，只要其滿足上文所給出的全局條件生成的全局狀態(tài)，都能形成相應(yīng)的不動點。

在元胞自動機的研究中，對元胞自動機進行有規(guī)律性的分類是元胞自動機領(lǐng)域研究的一個重要方向，長期以來都是各領(lǐng)域?qū)W者的在元胞自動機研究中的熱門話題。根據(jù)不同學(xué)者的研究背景，產(chǎn)生了許多基于不同元胞自動機性質(zhì)的分類方式，其中大部分還是基于計算機科學(xué)的分類方式。例如，Wolfram 根據(jù)計算機模擬圖的演化規(guī)律對元胞自動機進行分類，將所有的初等元胞自動機分成了四種類型：穩(wěn)定型、周期型、混沌型和復(fù)雜型。（[13]）而本文主要承續(xù)了文[9]中所提出的理論思想，通過應(yīng)用修正理論，從邏輯學(xué)的角度出發(fā)對總和型馮諾依曼型元胞自動機進行了分類。

本文主要從邏輯的視角出發(fā)，將Totalistic 規(guī)則的馮諾依曼型元胞自動機進行邏輯自指語句形式的表達，從而對其不動點形式以及所存在的悖論特征進行了一個相應(yīng)的分類。相對于論文[9]中的初等元胞自動機，將初等元胞自動機系統(tǒng)擴展到二維不僅僅是因為這種擴展帶來了許多涉及二維模式邊界和界面行為的新現(xiàn)象；而更重要的是，二維元胞自動機系統(tǒng)作為一種平面模型，更容易用來比較現(xiàn)實物理系統(tǒng)。通過本文的研究，從邏輯的視角出發(fā)對元胞自動機進行分類，希望能夠在一個更大的范圍建立起元胞自動機與自指語句內(nèi)在的邏輯聯(lián)系，使人們能夠進一步看到元胞自動機和自指語句所具有的結(jié)構(gòu)相似性，從而進一步推動人們對自指語句、乃至邏輯學(xué)領(lǐng)域的相關(guān)的跨學(xué)科研究。