模式隨處可見。從藝術到數學，從音樂到生物學，模式幾乎涵蓋了我們生活和文化的方方面面。這並非巧合，因為人類的思想在模式的創造和認識方面表現出色。Cellular Automata由Stephen Wolfram博士（Mathematica和Wolfram Alpha的創建者）推廣，元胞自動機（CA）是由一組定義明確的規則生成的模式，但能夠表現出複雜的，有時甚至是隨機的行為。
起初，我看到這些模式只是看起來有趣的圖像。CA不僅僅能產生漂亮的圖片,還提供了對許多類型的複雜系統進行建模的方法，而這一事實本身可能對AI的未來以及包括區塊鏈在內的許多其他類型的技術產生重大影響。
這篇文章是關於CA及其應用的思考和實驗的大雜燴，所以在閱讀了這些模式的以下介紹之後，以及關於Rule 30的一些內容。
1.背景：什麼是元胞自動機？
元胞自動機的一個簡單示例是根據一組生成模式的規則隨時間演變的cells網格（http://mathworld.wolfram.com/CellularAutomaton.html）。以下是“Rule 1”創建的CA的簡單示例：
Cellular Automaton Generated by Rule 1
在第一行，我們從一排白色cells開始，中間有一個黑色cell。這是我們的初始條件。我們可以提出各種各樣的起始條件，但現在讓我們保持簡單。為了生成後續行，我們應用一個簡單的規則：對於我們生成的行中的每個cell，查看它上面的三個cells（即左上角，頂部中間和右上角）。如果所有三個都是白色的，那麼當前的單元格應該是黑色的。否則，下一個單元格應為白色。也許可以通過圖形更好地理解這條規則：
Rule 1
每個方形窗口中的前三個cells包含我們可能在包含三個cells的子行中觀察到的可能模式。如果我們找到那個模式，我們直接在三個下面繪製相應的單元格。
我們可以繼續按照我們的意願為後續行應用此規則。這個CA包含一個明顯的模式，並不是太有趣，但還有許多其他規則供我們探索！實際上，由於binary cells依賴於它上面的三個binary cells，因此在該系統中有2 ^（2³）=2⁸= 256個規則。
一個稍微有趣的CA是“Rule 50”：
Cellular Automaton Generated by Rule 50
Rule 50
雖然稍微複雜一些，但Rule 50仍然包含一種無聊，可預測的模式。讓我們看看幾個例子，看看其他CA有哪些能力：
Cellular Automaton Generated by Rule 54
Cellular Automaton Generated by Rule 62
Cellular Automaton Generated by Rule 90
Rule 90
Rule 90非常吸引人。注意它的遞歸結構 - 整個模式類似於一個三角形，但是這個結構可以分解成更小但相似的三角形。現在，這些較小的三角形可以分解成更小的三角形，依此類推，直到我們到達一個無法進一步分割的cell。令我感到驚訝的是，這樣一個簡單的生成規則可以創造出如此美麗的模式。然而Rule 90仍然是可預測的，因為如果我們繼續根據生成規則生成越來越多的行，我們就能很清楚模式會是什麼樣子。但是所有CA都可以預測嗎？
令人驚訝的是，答案是否定的。
2.Rule 30的不合理隨機性
Cellular Automaton Generated by Rule 30
Rule 30
注意CA圖中的兩種不同行為 - 而左側看似相當有序，右側看起來很混亂！由於似乎沒有任何明確的模式，接下來的幾行看起來很明顯。事實上，數學家表明，這種結構符合許多嚴格的偽隨機性測試（數學隨機性，而不是在自然界觀察到的真實隨機性）。這種偽隨機性是如此強大，以至於Wolfram的計算語言Mathematica使用Rule 30作為其隨機數生成器！
真正令人著迷的是這種混亂是如何從一個簡單的起始條件和一套簡單的規則中產生的。這可能會提醒一種“蝴蝶效應”，這是一種假設現象，其中蝴蝶拍打它的翅膀，從而引起空氣中的輕微干擾，這會引起微風的干擾，從而導致風模式的干擾，這會導致颶風。這個事件雖然相當荒謬，但在自然界中無疑是可以想象的。Rule 30的有趣之處在於它發生在計算世界中，即程序世界。
淺談計算機程序的行為
計算機程序本質上是為機器編寫的一組清晰，明確的指令。程序員編寫指令併為機器提供輸入數據。機器通過操縱電路執行輸入指令，並返回計算結果。機器雖然在當今世界是數字的，但最終是機械設備，它們將數字加在一起並在存儲器中移動這些數字。因此，我們希望機器的運行與我們告訴他們完全相同。如果我們告訴機器計算2 + 2，我們希望答案為4，如果我們告訴它刪除存儲在內存中特定位置的數字，那麼我們就是這麼想的。如果不是這樣，機器將不會非常有用！重點是，機器做我們告訴他們要做的事情，僅此而已。
CA實際上是程序：它們具有輸入（cells的起始行），用於操縱輸入的一組規則，並且它們具有輸出（觀察到的模式）。但就CA而言，我們真的知道我們告訴他們的是什麼嗎？我們已經看到了簡單的CA程序如何表現出複雜，不可預測的行為。即使程序完全按照我們的要求執行，我們也不知道輸出是什麼。從某種意義上說，這個程序已經脫離了我們的理解。
雖然大多數CA表現出可預測的行為，但我們對Rule 30的行為的直覺完全崩潰了。上圖模式的下一行可能是什麼？瞭解模式的下一部分的唯一方法是計算它。這引導我們進行下一次討論，即計算不可約性。
3.計算不可約性和區塊鏈
對於那些仍然對這個流行詞的含義感到好奇的人來說，Blockchain只是計算機之間的信任系統。該信託的應用範圍從金融交易到安全投票系統。為了在任何兩方之間存在信任，必須首先確定某種基礎。黃金支持金融交易和貨幣，情緒穩定在人與人之間建立信任，數學知識使我們信任計算機程序的正確性。在區塊鏈中，通過以安全的方式將信息塊鏈接在一起來創建信任，因此得名。
簡單討論量子計算機如何打破區塊鏈
在過去的幾年裡，大多數情況下都是理論上的練習，但是像IBM這樣的幾家公司現在正在開發基本的量子計算機。這種即將到來的技術可能會徹底破壞質數分解，從而給世界密碼系統帶來壓力。量子計算機的內部工作原理超出了本文的範圍，但我們的想法是,他們可以利用量子力學和各種屬性的素數執行某些類型的計算,包括質因數分解,指數增長速度比經典計算機。當這些類型的機器變得普遍時，許多現代的POW問題可能會失去它們的有效性。我們應該注意到，並不是所有的問題都能被量子計算機更有效地解決。到目前為止，數學家們只知道少數幾個問題可以通過量子物理和數字理論之間的特殊關係來加速，這些關係可以創建計算捷徑。當在量子機器上運行時，許多問題都不能加速。
元胞自動機為工作問題提供了一個潛在的證據，它可能不那麼容易受到量子革命的影響。我們之前討論過一些CAs(即Rule 30)如何具有這樣的質量，即沒有快捷方式來確定模式的行為——確定模式中的下一行的唯一方法是實際花費時間來計算它。這種沒有計算快捷方式的屬性被恰當地稱為計算不可約性。CA模式中的每一行必須按順序計算，每一行的計算依賴於前一行計算的完成。因此，CAs需要花費大量的時間來執行計算，這使它們成為工作問題的有力證據。
我提出的一個問題可以用於這種機制:給定來自CA模式的第n行，什麼規則/初始條件組合可以創建它?
某些CA的第n行的可能示例
假設上圖是某些CA模式的第100行。那麼問題是回溯創建該行的未知計算。解決這個問題聽起來很難！想象一下必須考慮的所有可能的規則和初始條件。但是，一旦問題得到解決，並且我們知道在第100行生成此特定模式的規則和起始條件，驗證解決方案非常簡單。我們只是採用起始條件並應用規則來生成後續行，然後確保最後一行與我們在問題陳述中提供的行相同。
計算困難，容易驗證，計算上不可約，涉及元胞自動機的計算可能提供必要的機制，以確保區塊鏈在整個量子時代的完整性。
4.元胞自動機和神經網絡實驗
我們之前已經討論過在Rule 30中預測模式的難度，至少在抽象層面上是如此。人類的直覺無法預測Rule 30中看不見的行序列，但計算機在這方面的表現如何呢？為了回答這個問題，我進行了一系列涉及神經網絡的實驗。我嘗試創建一個簡單的前饋網絡，以預測給定前一行的CA模式中的下一行。換句話說，神經網絡的目標是發現管理幾種CA模式創建的潛規則。
對於那些有深度學習經驗的人，我展示了我用於下面所有實驗的網絡架構。我使用了具有1000個神經元的3個隱藏層，具有LeakyReLU激活，ADAM優化和sigmoid 輸出層。為了阻止過度擬合，我包括了幾個dropout層。
輸入是n×m矩陣X，其包含n個CA行的示例，每行具有m個單元，並且輸出是包含n個CA行的矩陣y，其直接對應於X中的那些CA行之後的CA行。
# data contains observed rows from the automata pattern
X = np.array(data[0:-2])
y = np.array(data[1:-1]) # offset by 1
X_train, X_test, y_train, y_test = train_test_split(X,
y, train_size=0.8)
model = Sequential()
model.add(Dense(1000, activation="linear", input_dim = X_train.shape[1]))
model.add(LeakyReLU())
model.add(Dense(1000, activation="linear") )
model.add(LeakyReLU())
model.add(Dropout(0.5))
model.add(Dense(1000, activation="linear") )
model.add(LeakyReLU())
model.add(Dense(1000, activation="linear") )
model.add(LeakyReLU())
model.add(Dropout(0.5))
model.add(Dense(y.shape[1], activation="sigmoid") )
optim = keras.optimizers.Adam(lr=0.0001)
model.compile(loss='mse',
optimizer=optim )
history = model.fit(X_train, y_train, validation_split=0.2, epochs=100)
對於第一個實驗，我使用簡單的Rule 1生成行。下面是測試數據的ROC曲線。
在某種意義上，該模型似乎正確地確定了Rule 1的生成機制。也就是說，給定一行單元格，神經網絡能夠像Rule 1那樣計算下一行。讓我們嘗試一個最複雜的例子，比如Rule 54
同樣，神經網絡在這裡做得很好。藍色線條在左上方略微圓潤，表明性能不佳，但仍然相當不錯。現在讓我們預測一個我最喜歡的CA的行，Rule 90（回想一下這個CA的模式包含一個有趣的遞歸結構）。
神經網絡做得很糟糕。請記住，Rule 90只是生成模式的函數，而且非常簡單。從ROC曲線看，網絡似乎正在進行隨機猜測。一個人可以看兩個連續的行，並且有一點工作推斷出所使用的模式。然而，神經網絡似乎在這項任務中失敗了。為了更好地衡量，讓我們看看當我們使用Rule 30時會發生什麼。
在這種情況下，網絡在大多數情況下都傾向於做出積極的預測。雖然ROC曲線表明Rule 30具有更好的預測能力，但這並不是說Rule 30很容易預測，而是說管理這個CA的規則比使用Rule 90的實驗更容易確定。
我在實驗中觀察到的一個有趣現象是測試損失曲線。在所有實驗中，除了Rule 30，損失收斂。然而，在Rule 30情況下，隨著更多的訓練，損失開始增加。這通常表明模型過擬合。我不知道Rule 30規則的混亂和這種不收斂之間是否有聯繫，但這很有趣。
這是各種實驗的測試損失曲線。
5.元胞自動機和人工智能的未來
由於元胞自動機是圖靈完成的，它們能夠計算任何可以計算和建模幾乎任何類型系統的東西。他們有一天會被用來模擬智力嗎?過去對智能建模的嘗試，以及人們可能認為人工神經網絡的嘗試，都遇到了同樣的問題:我們並不真正知道什麼是智能。然而，這可能不是必要的。我們之前討論過程序如何顯示行為，在某種意義上，超越了程序員的意圖。理解程序的行為在其創建過程中並不重要。此外，程序的行為會隨著時間的推移而改變和適應，產生混亂和隨機性。也許有一天，我們將創造一個CA，它以一種進化的方式進化，最終成為智能的模型。當然，這可能涉及到更先進的CAs，它們不需要在簡單的黑白網格上操作，但這並不意味著這些系統可能包含把人工智能提升到下一個級別的能力。
閱讀更多 不靠譜的貓 的文章
