馮諾依曼型元胞自動機(jī)和自指語句

鄔舒雯 熊明

1 引言

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

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

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

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

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

2 初等元胞自動機(jī)和自指語句

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

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

本節(jié)主要解釋初等元胞自動機(jī)與自指語句如何發(fā)生關(guān)聯(lián)。初等元胞自動機(jī)中的元胞均勻地分布在一條兩段可無限延伸的帶子上，因此每個格子以由整數(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ū)分不同的元胞自動機(jī)。圖2-1 對應(yīng)的自動機(jī)被命名為ECA 452文[1]中使用“ECA n”（或“規(guī)則n”）來表示一個Wolfram 數(shù)為n 的初等元胞自動機(jī)。Wolfram 數(shù)是指根據(jù)Wolfram 給出的編碼規(guī)則對元胞自動機(jī)進(jìn)行編碼所得的數(shù)字，詳情參見[14]，第65 頁。。

每個演化規(guī)則本質(zhì)上是一個有三個變元的布爾函數(shù)。例如，圖2-1 實則是一個三變元的真值表，它正是ECA 45 的迭代函數(shù)f的表格表示。f(x,y,z)的布爾表達(dá)式為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)站給出了所有初等元胞自動機(jī)對應(yīng)的布爾表達(dá)式。確定。

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

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

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

3 馮諾依曼型元胞自動機(jī)的邏輯表達(dá)式

馮諾依曼型元胞自動機(jī)作為二維元胞自動機(jī)中常見的一種類型，是指元胞領(lǐng)域是包含目標(biāo)元胞周圍（上下左右）四個正交元胞的集合。我們可用矩陣形式表示馮諾依曼型元胞自動機(jī)，其中元胞是均勻排列的，并由整數(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 型元胞自動機(jī)規(guī)則進(jìn)行圖示化，如圖3-1 所示5所有此類規(guī)則圖示都由電腦軟件Wolfram Mathematica 12 繪制而成，不再進(jìn)行一一說明。的馮諾依曼型元胞自動機(jī)（下文簡稱T 型元胞自動機(jī)）。同時，根據(jù)Wolfram 提出的編碼規(guī)則，我們也可以對其進(jìn)行相應(yīng)的編碼t5·25+t4·24+…+t0·20，所得的編碼數(shù)也稱為Wolfram 數(shù)。因此，我們共有26個T 型元胞自動機(jī)，用“Rn”（或“規(guī)則n”）來表示一個Wolfram 數(shù)為n的自動機(jī)。

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

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

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

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

如表3-1 所示，我們對滿足Totalistic 規(guī)則的迭代函數(shù)的每種相應(yīng)可能情形進(jìn)行編碼，從而將其對應(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 型元胞自動機(jī)由每條子規(guī)則Tn共同決定，而每條Tn規(guī)則則能夠給上述真值表賦予相對應(yīng)的真值。因此，我們可以根據(jù)元胞自動機(jī)的演化規(guī)則所知道的A值，反解真值表，從而得到每個Totalistic 規(guī)則的邏輯表達(dá)式。

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

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

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

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

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

4 尋找不動點(diǎn)

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

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

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

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

根據(jù)圖4-2 所示的尋找不動點(diǎn)的樹狀圖，具體的情形分析同R31 相似，我們就不過多筆墨進(jìn)行一一分析。通過圖4-2，當(dāng)C0,0(k)=1 時，只有T1條件才能滿足，即周邊元胞狀態(tài)都為0 的情形，此時我們可以回到當(dāng)C0,0(k)=0 的情況進(jìn)行分析。當(dāng)C0,0(k)=0 時，雖然通過T4、T3和T2條件，我們都能得到該狀態(tài)，但在進(jìn)行下一階段時，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)成的不動點(diǎn)，即0、1 交替出現(xiàn)的元胞狀態(tài)；而一旦滿足該條件下的不動點(diǎn)，則其出現(xiàn)的情形必然是在全局狀態(tài)下都滿足該條件，也就是說在二維平面空間下都滿足這個條件的R3 自動機(jī)才能出現(xiàn)不動點(diǎn)。因此，在T1-T4全局條件下，我們可以得到如圖4-5（左）所示矩陣分布的不動點(diǎn)。同樣的，顯然同時滿足T1→1，T4→0 的元胞自動機(jī)要存在該全局條件下分布的不動點(diǎn)，具體見表4-1。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在前文中，我們已對不存在不動點(diǎn)的R1 的Totalistic 型馮諾依曼元胞自動機(jī)的悖論性質(zhì)進(jìn)行了探討。同時，我們在第4 節(jié)中，已經(jīng)證明了R31 的T 型元胞自動機(jī)也是沒有不動點(diǎn)的，換句話說，也具有某種悖論的性質(zhì)。在進(jìn)行探討之前，我們先引入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 元胞自動機(jī)的自指語句形式和Curry 悖論有著異曲同工之處。即，當(dāng)我們將Ci,j視為語句當(dāng)作A，那么可以發(fā)現(xiàn)它們有著相同的形式結(jié)構(gòu)。有趣的是，根據(jù)我們在第四節(jié)中已經(jīng)證明的，R31 元胞自動機(jī)不存在不動點(diǎn)，也就是悖論的。

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

6 結(jié)論

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

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

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

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

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

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