格仔自動機

一架格仔自動機：
{{Subst:生命棋

|0|0|0|0|0|0|0|0|0|1

|0|0|0|0|0|0|0|0|0|0

|1|0|0|0|1|0|0|0|0|0

|1|0|0|0|0|1|1|0|1|0

|1|0|0|0|1|1|0|0|0|1

|0|0|0|0|0|0|0|0|0|0

|1|0|0|0|0|0|0|0|1|0

|1|0|0|0|0|0|0|0|0|1

}}

格仔自動機（元胞自動機，cellular automaton，衆數係cellular automata，縮寫CA），又叫細胞自動機，係種離散模型，可算性理論（computability theory）、數學、理論生物學都有研究渠。渠由無限格有規律、硬掘掘嘅格仔（cells）組成，每格都處於有限種態之一。成個格仔網（grid）可以係任何有限維嘅。時（time）亦都係離散嘅。每格響t 時嘅態由 t-1時嘅一集有限格（呢集叫嗰格嘅鄰域，neighbourhood）嘅態決定。每一格嘅「鄰居」都係固定咗嘅（一格可以係自己嘅鄰居）。每次演進，每格都遵從同一規矩，一齊演進。

概覽

格仔自動機嘅一例係一張無限大嘅格仔紙，每格一係黑、一係白。每格有八格「鄰居」，總共2⁹ = 512 種可能嘅鄰域。格仔自動機嘅演變規律可用一張表來表示。由五百一十二種可能嘅鄰域，張表會講明下次呢格係黑定係白。呢樣就係二維CA嘅一例。Conway嘅生命棋就係其中最受歡迎者。

通常我哋會假設盤棋開始時，除咗有限咁多格，每格都屬同一態；而嗰有限咁多格就叫「位形」（configuration）。推而廣之，亦可假設，除咗有限咁多格，初始棋盤係週期性嘅－－呢種做法響一維CA 常見啲。

通常我哋會用個有限大（而唔用無限大）嘅格仔網來模擬一架格仔自動機。二維嘅自動機宇宙就會用長方形來模擬。咁當然會出問題：響條邊嘅格仔點算？做法嘅選擇會影響成個長方形嘅演變。一種做法係畀渠哋一個常值。另一種解係改「鄰域」嘅定義。例如，我哋可以拉畫面來整出一個錨環面（torus）。當一舊棋過咗上界，渠就會由下底同一位置出番來；過咗左界就會由右邊出番來（咁其實等同無限棋盤上嘅週期棋形。響偏微分方程學，呢種嘢會叫「週期性嘅邊界條件」periodic boundary conditions）。我哋可以睇渠做個長方形，左邊黏埋右邊，上邊黏埋下邊，成為一環面。第啲維度嘅宇宙都照做。咁做係為咗化解邊界鄰域嘅麻煩嘢。例如，響下面嘅一維自動機，嘅鄰域 of 格仔x_i^t— 其中 t 係步數（打棟）而 i 係 the index （打横）一代裏面—係 {x_i−1^t−1, x_i^t−1, x_i+1^t−1}。當左界一鄰域揾渠嘅左上格（唔係棋盤入面）做渠鄰居，就會出問題。

史

1940年代，Stanislaw Ulam（英文：Stanislaw Ulam）響洛斯阿拉莫斯國家實驗室做嗰時，用過一簡單嘅格仔網（lattice network）（英文：Lattice model (physics)）來研究晶體增長。同時，渠同事John von Neumann（英文：John von Neumann）就研究緊自我複製系統（英文：Self-replicating machine）。初頭 von Neumann 嘅設計原理係「一隻機械人砌另一隻機械人」－又叫做郁模型（kinetic model）。漸漸，von Neumann 明白砌隻自我複製嘅機械人有幾難，同埋要畀隻機械人海量嘅零件（"sea of parts"）來砌嘢有幾咁貴。Ulam 叫 von Neumann 試吓圍繞住種數學抽象來發展渠嘅設計，好似 Ulam 自己嘅結晶模型。咁樣就出咗第一架格仔自動機。好似 Ulam 嘅格仔網，von Neumann架格仔自動機係兩維嘅；隻自我複製機就用算法來實現（implemented algorithmically）。其結果就係架通用複製同埋砌機機（英文：Von Neumann universal constructor），活動響一架細鄰域嘅格仔自動機入面（只有掂住嘅格仔先至係鄰居；而 von Neumann's 架自動機入面，只有正交(orthogonal)嘅格仔至係鄰居），而每格有 29 態。von Neumann 證明咗有種棋形會響個格仔世界入面無止境咁砌自己嘅複製－叫做密鋪模型（tessellation model）。

1970年代，出現咗生命棋－一架兩態、兩維嘅自動機。生命棋出咗名，尤其響電算社羣入面。

生命棋由John Conway發明，由Martin Gardner 響Scientific American嘅一篇文推廣。渠嘅規則係：若果一黑格有兩或三格黑鄰，咁渠就繼續黑；若一白格有剛啱三黑鄰格，咁渠就變黑；其餘情況下，嗰格下次都白。就咁，一盤生命棋可以有咁複雜得咁複雜，響似乎混亂同埋秩序之間搖擺。一種常見嘅棋形係「滑翔機」（glider）－會響棋盤上打斜郁嘅幾格棋。我哋可以砌到令尐滑翔機互相影響，來模擬出計算，甚至模擬普適Turing機。

或者多數人覺得生命棋屬於玩，係咁意探下啲得意嘢、睇下第啲有關棋則以外，好少有跟進。

但1969年德國電算先驅Konrad Zuse出版咗本《計出空間》Calculating Space，提出宇宙嘅規律嘅本質係離散嘅，而成個宇宙係架巨格仔自動機嘅先決(?)(deterministic)嘅計算結果。

1983年，Stephen Wolfram出咗渠一系列文嘅第一篇，討論一種好基本、但之前無人惏過嘅自種機－渠叫其做「基本格仔自動機」（elementary cellular automata）－睇下面。出奇嘅係，呢尐簡單嘅法則，演變出來好複雜。咁Wolfram 就猜測大自然嘅複雜性都係類似機制生出來嘅。重有，呢段時間 Wolfram 發展咗內蘊偶然混亂性（intrinsic randomness）同埋計算可約性（computational irreducibility），提出rule 110可能係普適—後來Matthew Cook喺1990年代證咗。

1980年代尾，Wolfram 離開咗學院，專心砌Mathematica；跟住用其來推展渠嘅早期結果，到一廣泛系列嘅簡單抽象系統。2002年渠出咗本A New Kind of Science來講渠嘅格仔自動機嘅結果，重話呢啲發現唔係單丁嘅偶然事，而係硬淨（robust）嘅，重會影響每一門科學。呢本書無倡議用格仔自動機來砌基礎物理，但描述咗幾種基於CA 嘅物理模型，亦有畀基於性質完全唔同嘅抽象系統嘅模型。

Rudy Rucker喺渠2005年本書生命盒、海螺同埋靈魂（The Lifebox, The Seashell and The Soul）推展Wolfram嘅理論到「普遍自動性（Universal Automatism）」－用格仔自動機來模型來解釋簡單嘅規律點樣會產生複雜嘅結果。

最簡單

最簡單嘅格仔自動機得一維；每格得兩態；每格嘅鄰居就係渠左右嘅兩格。一格同渠左右夾埋組成一鄰域，總共有 2³=8 咁多種可能嘅棋形。咁總共有 2⁸=256種規律。呢啲自動機通常會用Wolfram 記號（en:Wolfram notation）來表示。一架自動機嘅名就係個十進制數，其相應二進制表示就畀出個演化規律表。例如三十號機（"rule 30 CA"）同埋一百一十號機（"rule 110 CA）嘅演化表就係 30_x=00011110_ii and 110_x=1101110_ii。咁，三十號機 00011110 最高位嘅 0 代表111-->0，次高位嘅0代表 110-->0，跟住 101-->0, 100-->1, 011-->1, 010-->1, 001-->1, 000-->0。若果我哋由單丁個1開始，三十號機同一百一十號機會整出：

三十號機（Rule 30）

而家個樣	111	110	101	100	011	010	001	000
中格嘅下一態	0	0	0	1	1	1	1	0

一百一十號機（Rule 110 cellular automaton）

而家棋形	111	110	101	100	011	010	001	000
中格嘅下一態	0	1	1	0	1	1	1	0

咁一張表就完全定義好一架格仔自動機。例如，30號機（rule 30）嘅表就話：若果有左中右三格係100，咁中間嗰格下次就會變做1。

有幾篇文分析同比較呢二百五十六架機。30號同一百一十號機就特別好頑。

30號由唔算混亂嘅初始值生出混亂（randomness）。Wolfram 提議用渠中間一棟來做架模擬亂值機（en:pseudorandom number generator (PRNG)）；呢項提議過咗好多種標準嘅測試都；Wolfram 就喺Mathematica 應用咗（尤其係，1990年代有本密碼學概覧書話30號機等價於linear feedback shift register (LFSR)，但其實呢項聲稱係90號機嘅。）。雖然30號機可由好多種輸入整出混亂，但亦有無限咁多種輸入會整出週期嘅結果。最基本嘅例係開頭全零。 Matthew Cook發現，任何有無限串'00001000111000'，之間隔住六格'1'，都得。

一百一十號機，好似生命棋，顯示出種Wolfram所謂嘅「第四類行為」（class IV behavior），既唔完全亂來（random），亦唔係完全週期性嘅。有好幾種局部嘅結構會出現同埋互相影響。1994年，本A New Kind of Science重寫緊時，Cook證明咗呢啲結構足夠支持普適性（universality）。咁樣就好頑：一百一十號機係架好簡單嘅一維系統，但要整到渠做特定嘅嘢就唔易。呢項結果好支持 Wolfram嘅觀點，第四類（class IV）嘅系統本內就好可能係普適（universal）嘅。Cook喺1998年Santa Fe Institute格仔自動機會報告咗渠份證明，但 Wolfram阻住唔畀會議紀錄登份證明，因渠唔想份證明早過渠本《A New Kind of Science》出。2004年，Wolfram 份雜誌 Complex Systems (Vol. 15, No. 1) 終於登咗Cook嘅證－足足等咗十年。

可逆

一架自動機叫可逆（reversible），若果渠上面每一種棋形都只得一幅前象（preimage）。若我地當架自動機係一支函數，由一形狀彈去另一形狀，咁即係話支函數係雙射（bijection）。

For one dimensional CA there are known algorithms for finding preimages, and any 1D rule can be proved either reversible or irreversible. For CA of two or more dimensions it has been proved that the reversibility is undecidable for arbitrary rules. The proof by Jarkko Kari is related to the tiling problem by Wang tiles.

Reversible CA are often used to simulate such physical phenomena as gas and fluid dynamics, since they obey the laws of thermodynamics. Such CA have rules specially constructed to be reversible. Such systems have been studied by Tommaso Toffoli, Norman Margolus and others.

For finite CAs that are not reversible, there must exist patterns for which there are no previous states. These patterns are called Garden of Eden patterns. In other words, no pattern exists which will develop into a Garden of Eden pattern.

Several techniques can be used to explicitly construct reversible CA with known inverses. Two common ones are the second order technique and the partitioning technique, both of which involve modifying the definition of a CA in some way. Although such automata do not strictly satisfy the definition given above, it can be shown that they can be emulated by conventional CAs with sufficiently large neighborhoods and numbers of states, and can therefore be considered a subset of conventional CA.

Totalistic

A special class of CAs are totalistic CAs. The state of each cell in a totalistic CA is represented by a number (usually an integer value drawn from a finite set), and the value of a cell at time t depends only on the sum of the values of the cells in its neighborhood (possibly including the cell itself) at time t−1. If the state of the cell at time t does depend on its own state at time t−1 then the CA is properly called outer totalistic, although the distinction is not always made. Conway嘅生命棋 is an example of an outer totalistic CA with cell values 0 and 1.

A notation exists to describe rulesets of two-state totalistic CAs consisting of an initial indicating the neighbourhood of each cell and sums following the letters S (for survival) and B (for birth) for which those changes occur. In this notation Conway's Game of Life is M:S23/B3. This notation has been extended for non-totalistic CAs, where a letter or letters follow each sum indicating what patterns of neighbours cause survival or birth events.

密碼學用

Rule 30 was originally suggested as a possible stream cipher for use in cryptography.

Cellular automata have been proposed for public key cryptography. The one way function is the evolution of a finite CA whose inverse is believed to be hard to find. Given the rule, anyone can easily calculate future states, but it appears to be very difficult to calculate previous states. However, the designer of the rule can create it in such a way as to be able to easily invert it. Therefore, it is apparently a trapdoor function, and can be used as a public-key cryptosystem. The security of such systems is not currently known.

自然 biotic types

有啲生物會用上自然嘅格仔自動機。

有啲海螺，如Conus同Cymbiola 屬，嘅紋形係由自然嘅格仔自動機生出來嘅。色素細胞住喺沿住個殼條邊（lip）嘅一條窄帶上。每粒細胞依佢週圍細胞嘅活唔活躍，用一條數來決定分唔分泌色素^{[未記出處或冇根據]}。呢條細胞帶會慢慢生，將啲色圖案留喺個殼上。例如，分布好廣嘅Conus textile 就着住種好似上面三十號自動機嘅圖案。

Plants regulate their intake and loss of gases via a CA mechanism. Each stoma on the leaf acts as a cell.

化學 types

The Belousov-Zhabotinsky reaction is a spatio-temporal chemical oscillator which can be simulated by means of a cellular automaton. In the 1950s A. M. Zhabotinsky (extending the work of B. P. Belousov) discovered that when a thin, homogenous layer of a mixture of malonic acid, acidified bromate and a ceric salt were mixed together and left undisturbed, fascinating geometric patterns such as concentric circles and spirals propagate across the medium. In the "Computer Recreations" section of the August 1988 issue of Scientific American Professor A. K. Dewdney presented a cellular automaton whose behavior closely resembles the Belousov-Zhabotinsky reaction. Whether the Belousov-Zhabotinsky reaction actually occurs as the result of a cellular automaton at the molecular level is not yet known. So far, no naturally occurring chemical cellular automata have been observed. All such reactions are done in laboratory settings.

電算處理器Computer processors

CA processors are a physical, not software only, implementation of CA concepts, which can process information computationally. Processing elements are arranged in a regular grid of identical cells. The grid is usually a square tiling, or tessellation, of two or three dimensions; other tilings are possible, but not yet used. Cell states are determined only by interactions with the small number of adjoining cells. Cells interact, communicate, directly only with adjoining, adjacent, neighbor cells. No means exists to communicate directly with cells farther away. Cell interaction can be via electric charge, magnetism, vibration (phonons at quantum scales), or any other physically useful means. This can be done in several ways so no wires are needed between any elements.

This is very unlike processors used in most computers today, von Neumann designs, which are divided into sections with elements that can communicate with distant elements, over wires.

改錯碼 (Error Correction Coding)

有人用格仔自動機來設計改錯碼－睇下《Design of CAECC - Cellular Automata Based Error Correcting Code》，作者係 D. Roy Chowdhury, S. Basu , I. Sen Gupta , P. Pal Chaudhuri。呢篇文定義一種新計，用CA來砌 SEC-DED 碼，重幫呢套碼報告咗一架快嘅硬件解碼器。

睇埋

CA 嘅例

自我複製