基本的なセルオートマトン

数学および計算可能性理論において、基本セルオートマトンとは、2つの可能な状態（0と1でラベル付けされる）を持ち、次世代のセルの状態を決定する規則が、セルの現在の状態とその2つの隣接セルのみに依存する1次元セルオートマトンである。普遍計算が可能な基本セルオートマトン（規則110、下記参照）が存在し、そのため、それは計算の最も単純なモデルの一つである。

セルとその2つの隣接セルには、 8 = 2 ³通りの構成が可能です。セルオートマトンを定義するルールは、これらの可能性それぞれについて結果の状態を指定しなければならないため、256 = 2 ^{2 3}通りの基本セルオートマトンが存在します。スティーブン・ウルフラムは、各ルールに0から255までの番号を割り当てる「ウルフラムコード」と呼ばれる方式を提案し、これが標準となっています。現在の構成は、111、110、...、001、000の順に記述され、これらの構成それぞれの結果の状態は同じ順序で記述され、整数の2進数表現として解釈されます。この番号がオートマトン規則番号となります。例えば、110 _d =01101110 ₂です。したがって、規則110は遷移規則によって定義されます。

可能なルールは256種類ありますが、その多くは、基となる形状を単純に変換するだけで互いに等価になります。最初の変換は垂直軸に関する鏡映であり、この変換を特定のルールに適用した結果を鏡像ルールと呼びます。これらのルールは垂直軸に関する鏡映を除いて同じ挙動を示すため、計算上は等価です。

例えば、規則110の定義を垂直線で反転すると、次の規則（規則124）が得られます。

鏡像規則と全く同じ規則は両性キラルであると呼ばれる。256個の基本セルオートマトンのうち、64個が両性キラルである。

2つ目の変換は、定義における0と1の役割を交換することです。この変換を与えられた規則に適用した結果を補完規則と呼びます。例えば、この変換を規則110に適用すると、次の規則が得られます。

そして、並べ替えた後、これがルール137であることがわかります。

補足ルールと同じルールが16個あります。

最後に、前述の2つの変換を規則に順次適用することで、鏡像となる補完規則を得ることができます。例えば、規則110の鏡像となる補完規則は規則193です。鏡像となる補完規則と同じ規則は16個あります。

256個の基本セルオートマトンのうち、これらの変換の下で等価でないものは88個ある。

反射と補元はどちらも合成を保存するため、一次元セルオートマトンモノイドの自己同型であることが判明した。 ^{[ 2 ]}

これらのオートマトンを研究するために使用される方法の1つは、1つのセルを除いてすべて0の初期状態からその履歴を追跡することです。ルール番号が偶数の場合（つまり、000の入力が1にならない場合）、各時刻tにおける状態を2進数で表現された整数として解釈し、整数のシーケンスa ( t )を生成することが理にかなっています。多くの場合、これらのシーケンスは単純な閉形式の式を持つか、単純な形式の生成関数を持ちます。次のルールは注目に値します。

これらの画像は時空間図を表しており、各ピクセル行は、時間が下に向かって増加する特定の時点におけるオートマトンの各セルを示しています。初期状態では、最上段のピクセル行の中央にある単一のセルが状態1にあり、他のすべてのセルは状態0となっています。

• 
  ルール0
• 
  ルール1
• 
  ルール2
• 
  ルール3
• 
  ルール4
• 
  ルール5
• 
  ルール6
• 
  ルール7
• 
  ルール8
• 
  ルール9
• 
  ルール10
• 
  ルール11
• 
  ルール12
• 
  ルール13
• 
  ルール14
• 
  ルール15
• 
  ルール16
• 
  ルール17
• 
  ルール18
• 
  ルール19
• 
  ルール20
• 
  ルール21
• 
  ルール22
• 
  ルール23
• 
  ルール24
• 
  ルール25
• 
  ルール26
• 
  ルール27
• 
  ルール28
• 
  ルール29
• 
  ルール30
• 
  ルール31
• 
  ルール32
• 
  ルール33
• 
  ルール34
• 
  ルール35
• 
  ルール36
• 
  ルール37
• 
  ルール38
• 
  ルール39
• 
  ルール40
• 
  ルール41
• 
  ルール42
• 
  ルール43
• 
  ルール44
• 
  ルール45
• 
  ルール46
• 
  ルール47
• 
  ルール48
• 
  ルール49
• 
  ルール50
• 
  ルール51
• 
  ルール52
• 
  ルール53
• 
  ルール54
• 
  ルール55
• 
  ルール56
• 
  ルール57
• 
  ルール58
• 
  ルール59
• 
  ルール60
• 
  ルール61
• 
  ルール62
• 
  ルール63
• 
  ルール64
• 
  ルール65
• 
  ルール66
• 
  ルール67
• 
  ルール68
• 
  ルール69
• 
  ルール70
• 
  ルール71
• 
  ルール72
• 
  ルール73
• 
  ルール74
• 
  ルール75
• 
  ルール76
• 
  ルール77
• 
  ルール78
• 
  ルール79
• 
  ルール80
• 
  ルール81
• 
  ルール82
• 
  ルール83
• 
  ルール84
• 
  ルール85
• 
  ルール86
• 
  ルール87
• 
  ルール88
• 
  ルール89
• 
  ルール90
• 
  ルール91
• 
  ルール92
• 
  ルール93
• 
  ルール94
• 
  ルール95
• 
  ルール96
• 
  ルール97
• 
  ルール98
• 
  ルール99

これらのオートマタの挙動を調査する2つ目の方法は、ランダムな状態から始まる履歴を調べることです。この挙動は、Wolframクラスの観点からよりよく理解できます。Wolframは、各クラスの典型的なルールとして次の例を示しています。^{[ 4 ]}

• クラス1：均一な状態に急速に収束するセルオートマトン。例としては、ルール0、32、160、232などがある。
• クラス2：反復状態または安定状態に急速に収束するセルオートマトン。例としては、ルール4、108、218、250などがある。
• クラス3：ランダムな状態を維持しているように見えるセルオートマトン。例としては、ルール22、30、126、150、182などがある。
• クラス4：反復的または安定した状態の領域を形成するだけでなく、複雑な方法で互いに相互作用する構造も形成するセルオートマトン。ルール110はその例である。ルール110は普遍計算が可能であることが実証されている。^{[ 5 ]}

計算された各結果は、その結果のソースの下に配置され、システムの進化を二次元的に表現する。

次のギャラリーでは、88 個の異なるルールそれぞれについて、ランダムな初期条件からのこの進化が示されています。各画像の下には、その画像を生成するために使用されたルール番号があり、括弧内には、反射または補完によって生成された同等のルールのルール番号が存在する場合は含まれています。^{[ 6 ]} 前述のように、反射ルールは反射された画像を生成し、補完ルールは白と黒が入れ替わった画像を生成します。

• 
  ルール0（255）
• 
  ルール1（127）
• 
  規則2（16、191、247）
• 
  ルール3（17、63、119）
• 
  規則4（223）
• 
  ルール5（95）
• 
  規則6（20、159、215）
• 
  ルール7（21、31、87）
• 
  規則8（64、239、253）
• 
  ルール9（65、111、125）
• 
  ルール10（80、175、245）
• 
  ルール11（47、81、117）
• 
  規則12（68、207、221）
• 
  ルール13（69、79、93）
• 
  規則14（84、143、213）
• 
  ルール15（85）
• 
  規則18（183）
• 
  規則19（55）
• 
  規則22（151）
• 
  ルール23
• 
  規則24（66、189、231）
• 
  規則25（61、67、103）
• 
  規則26（82、167、181）
• 
  ルール27（39、53、83）
• 
  規則28（70、157、199）
• 
  規則29（71）
• 
  規則30（86、135、149）
• 
  規則32（251）
• 
  規則33（123）
• 
  規則34（48、187、243）
• 
  ルール35（49、59、115）
• 
  規則36（219）
• 
  規則37（91）
• 
  規則38（52、155、211）
• 
  規則40（96、235、249）
• 
  規則41（97、107、121）
• 
  規則42（112、171、241）
• 
  規則43（113）
• 
  規則44（100、203、217）
• 
  規則45（75、89、101）
• 
  規則46（116、139、209）
• 
  規則50（179）
• 
  ルール51
• 
  規則54（147）
• 
  規則56（98、185、227）
• 
  規則57（99）
• 
  規則58（114、163、177）
• 
  規則60（102、153、195）
• 
  規則62（118、131、145）
• 
  規則72（237）
• 
  規則73（109）
• 
  規則74（88、173、229）
• 
  規則76（205）
• 
  ルール77
• 
  規則78（92、141、197）
• 
  規則90（165）
• 
  規則94（133）
• 
  規則104（233）
• 
  ルール105
• 
  規則106（120、169、225）
• 
  規則108（201）
• 
  規則110（124、137、193）
• 
  規則122（161）
• 
  規則126（129）
• 
  規則128（254）
• 
  規則130（144、190、246）
• 
  規則132（222）
• 
  規則134（148、158、214）
• 
  規則136（192、238、252）
• 
  規則138（174、208、244）
• 
  規則140（196、206、220）
• 
  規則142（212）
• 
  規則146（182）
• 
  ルール150
• 
  規則152（188、194、230）
• 
  規則154（166、180、210）
• 
  規則156（198）
• 
  規則160（250）
• 
  規則162（176、186、242）
• 
  規則164（218）
• 
  規則168（224、234、248）
• 
  規則170（240）
• 
  規則172（202、216、228）
• 
  規則178
• 
  規則184（226）
• 
  規則200（236）
• 
  規則204
• 
  規則232

多くの基本的なセルオートマトンでは決定論的に解くことができ、つまり、与えられたセルの状態を次のように表現することができます。 ${\displaystyle n}$初期設定から始まる反復処理${\displaystyle x\in \{0,1\}^{\mathbb {Z} }}$明示的な式によって。^{[ 11 ]}

させて${\displaystyle [F^{n}(x)]_{j}}$細胞の状態を表す${\displaystyle j}$後${\displaystyle n}$反復またはルール${\displaystyle F}$初期条件は次のように表されます。${\displaystyle x}$、 となることによって ${\displaystyle x_{i}}$細胞の状態 ${\displaystyle i}$初期構成では、${\displaystyle x_{i}\in \{0,1\}}$以下に代表的な3つの例を示します。

ルール90：

${\displaystyle [F^{n}(x)]_{j}=\sum _{i=0}^{n}{\binom {n}{i}}x_{2\,i-n+j}\mod 2}$

ルール50：

${\displaystyle [F^{n}(x)]_{j}={\frac {1}{2}}+{\frac {1}{2}}\left(-1\right)^{n}+\sum _{i=1}^{n-1}\left(\left(-1\right)^{i+n}\prod _{p=-i}^{i}x_{p+j}\right)+\sum _{i=0}^{n}\left(\left(-1\right)^{i+n+1}\prod _{p=-i}^{i}{\overline {x}}_{p+j}\right)}$

規則172：

${\displaystyle [F^{n}(x)]_{j}={\bar {x}}_{j-2}{\bar {x}}_{j-1}x_{j}+\left({\bar {x}}_{j+n-2}x_{j+n-1}+x_{j+n-2}x_{j+n}\right)\prod _{i=j-2}^{j+n-3}(1-{\bar {x}}_{i}{\bar {x}}_{i+1})}$

上記において、${\displaystyle {\bar {x}}_{j}=1-x_{j}}$。

H. Fukś は、次の最小基本ルールに対して決定論的解公式を導出しました: ^{[ 12 ]} 0, 1, 2, 3, 4, 5, 8, 10, 11, 12, 13, 14, 15, 19, 23, 24, 27, 28, 29, 32, 34, 36, 38, 40, 42, 43, 44, 46, 50, 51, 56, 60, 72, 76, 77, 78, 90, 105, 108, 128, 130, 132, 136, 138, 140, 142, 150, 156, 160, 162, 164, 168, 170、172、178、184、200、204、および232。これらの式を用いることで、小さな記号ブロックの出現確率を導き出すことができます。規則184または規則90の項目には、そのような確率を表す式の例が示されています。

• ワイススタイン、エリック W. 「初等セルオートマトン」 . MathWorld .
• ワイススタイン、エリック・W. 「ルール30」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 50」 . MathWorld .
• ワイススタイン、エリック・W. 「ルール54」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 60」 . MathWorld .
• ワイススタイン、エリック・W. 「ルール62」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 90」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 94」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 102」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 110」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 126」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 150」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 158」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 182」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 188」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 190」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 220」 . MathWorld .
• ワイススタイン、エリック W. 「ルール 222」 . MathWorld .

• Wolfram Atlas of Simple Programsの「Elementary Cellular Automata」
• セルオートマトンによる描画を行う、長さ32バイトのMS-DOS実行ファイル（デフォルトはルール110）
• ランダムに選ばれたすべてのルールのショーケース
• Wolframルールパーサーを使用した最小限のセルオートマトンエミュレーション（プレーンなJavaScriptでオンライン）