フォン・ノイマン型セルオートマトン

フォン・ノイマン・セル・オートマトンとは、セル・オートマトンの最初の表現であり、その開発は、ジョン・フォン・ノイマンの親友であり同僚の数学者でもあるスタニスワフ・ウラムからの提案によって促された。その本来の目的は、機械の自己複製の論理的要件についての洞察を提供することであり、フォン・ノイマンのユニバーサル・コンストラクタで使用された。

ノビリのセルオートマトンとは、フォン ノイマンのセルオートマトンの一種で、合流したセルが信号を交差させて情報を保存する機能が追加されています。前者では 3 つの状態が余分に必要となるため、ノビリのセルオートマトンの状態は 29 ではなく 32 になります。ハットンのセルオートマトンはさらに別のバリエーションで、ラングトンのループに類似したデータのループを複製できます。

一般的に、セルオートマトン (CA) は、互いに位置関係にある有限状態オートマトン(FSA)の配置で構成され、各 FSA は位置的に隣接する他の FSA と情報を交換します。フォン ノイマンのセルオートマトンでは、有限状態マシン (またはセル) は 2 次元の直交グリッドに配置され、周囲の 4 つのセルとインターフェイスします。フォン ノイマンのセルオートマトンがこの配置を使用した最初の例であったため、フォン ノイマン近傍として知られています。

FSA のセットは、無限サイズのセル空間を定義します。すべての FSA は、状態遷移関数またはルール セットの点では同一です。

近傍(グループ化関数)は状態遷移関数の一部であり、任意のセルに対して、そのセルの状態が依存する他のセルのセットを定義します。

すべてのセルは、同期デジタル回路のように、普遍的な「クロック」に合わせて同期して遷移します。

フォン・ノイマン細胞空間の各FSAは、ルールセットの29の状態のいずれかを受け入れることができます。ルールセットは5つの直交サブセットにグループ化されています。各状態には、セルオートマトンプログラムGollyのセルの色（赤、緑、青）が含まれます。

1. 基底状態U​   （48、48、48）
2. 遷移状態または感作状態（8つのサブ状態）
   1. S（新たに感作された）  (255, 0, 0)
   2. S ₀ – (感作、1サイクルの間入力を受けていない)  (255, 125, 0)
   3. S ₀₀ – (感作、2サイクルにわたって入力を受けていない)  （255、175、50）
   4. S ₀₀₀ – (感作、3サイクル入力を受けていない)  (251, 255, 0)
   5. S ₀₁ – (感作、1サイクル入力を受けず、その後1サイクル入力を受ける)  （255、200、75）
   6. S ₁ – (感作、1サイクルの入力を受けた)  （255、150、25）
   7. S ₁₀ – (感作、1サイクルの入力を受け、その後1サイクルの入力を受けない)  （255、255、100）
   8. S ₁₁ – (感作、2サイクルの入力を受けた)  （255、250、125）
3. 合流状態（4つの励起状態）
   1. C ₀₀ – 休止状態（次のサイクルでも休止状態になります）  (0, 255, 128)
   2. C ₀₁ – 次に励起される（現在は静止しているが、次のサイクルで励起される）  （33、215、215）
   3. C ₁₀ – 興奮状態（ただし次の周期では静止状態になります）  （255、255、128）
   4. C ₁₁ – 興奮、次回興奮（現在興奮しており、次のサイクルでも興奮する）  （255、128、64）
4. 通常の伝送状態（4方向、励起または静止、8つの状態）
   1. 北向き（興奮状態と静止状態）  （36、200、36）   （106、106、255）
   2. 南向き（興奮と静止）  （106、255、106）   （139、139、255）
   3. 西向き（興奮と静止）  （73、255、73）   （122、122、255）
   4. 東向き（興奮と静止）  （27、176、27）   （89、89、255）
5. 特殊な伝送状態（4方向、励起または静止、合計8つの状態）
   1. 北向き（興奮状態と静止状態）  （191、73、255）   （255、56、56）
   2. 南向き（興奮と静止）  （203、106、255）   （255、89、89）
   3. 西向き（興奮と静止）  （197、89、255）   （255、73、73）
   4. 東向き（興奮と静止）  （185、56、255）   （235、36、36）

「励起」状態は、状態遷移ステップごとに 1 ビットの速度でデータを伝送します。

合流状態には 1 サイクルの遅延という特性があるため、実質的には常に 2 ビットのデータが保持されることに注意してください。

セル間のビットの流れは、方向プロパティによって示されます。次のルールが適用されます。

• 伝達状態は入力にOR演算子を適用します。つまり、伝達状態（通常または特殊）のセルは、それを指す入力のいずれかが時刻tで励起されている場合、時刻t+1で励起されます。
• データは、 Aの方向プロパティに従って、通常の伝送状態のセルAから、通常の伝送状態の隣接セルBに渡されます( BもAに向けられている場合を除き、その場合はデータは消えます)。
• データは、通常の伝送状態と同じルールに従って、特殊な伝送状態のセルAから特殊な伝送状態の隣接セルBに渡されます。
• 伝送状態の 2 つのサブセット (通常と特殊) は相互に拮抗しています。
  • 時刻tにおける励起された通常の透過状態にある細胞Aが与えられると、
  • 特別な伝送状態にあるセルBを指す
  • 時刻t+1にセルB は基底状態になります。特別な透過セルは「破壊」されています。
  • 特別な伝送状態のセルが通常の伝送状態のセルを「指している」場合にも同様のシーケンスが発生します。

合流状態には次の特定のルールが適用されます。

• 合流状態は相互にデータを渡しません。
• 合流状態は、1 つ以上の通常の伝送状態から入力を受け取り、合流状態に向けられていない通常の伝送状態と特別な伝送状態に出力を送信します。
• 送信状態方向プロパティに反してデータは送信されません。
• 合流状態によって保持されるデータは、その状態に、合流状態を指し示していない隣接する伝送状態がない場合には失われます。
• したがって、合流状態セルは、通常伝送状態セルの伝送ラインから特殊伝送状態セルへの「ブリッジ」として使用されます。
• 合流状態では、AND 演算子が入力に適用され、すべての潜在的な入力が同時に励起される場合にのみ励起された入力が「保存」されます。
• 合流セルは、OTS セルよりも 1 世代多く信号を遅延させます。これは、パリティ制約のために必要なことです。

最初は、セル空間、つまりセルオートマトンの世界の大部分は「空白」で、基底状態Uのセルから構成されています。隣接する通常または特殊な伝送状態からの入力励起が与えられると、基底状態のセルは「感作」され、一連の状態を経て最終的に静止伝送状態または合流状態で「休止」します。

細胞がどの目的状態に到達するかは、入力信号のシーケンスによって決まります。したがって、遷移/感作状態は、基底状態から静止伝達状態と合流状態のそれぞれにつながる 分岐ツリーのノードと考えることができます。

次のツリーでは、入力のシーケンスが各ステップの後にバイナリ文字列として表示されます。

• 基底状態Uの細胞に入力を与えると、次のサイクルでS （新しく感作された）状態に遷移する（1）
• S状態の細胞は、入力が与えられなければS ₀状態に遷移する（10）
  • S ₀状態のセルは、入力が与えられない場合、 S ₀₀状態（100） に遷移します。
    • S00状態のセルは_、入力が与えられない場合、 S000状態（1000） に遷移します _。
      • S000状態のセルは_、入力が与えられない場合、東向きの通常の伝送状態（10000）に遷移します。
      • S000状態のセルに入力を与えると、北向きの通常の透過状態（10001）に遷移する_。
    • S00状態のセルに入力を与えると、西向きの通常の伝達状態（1001）に遷移する_。
  • S ₀状態のセルに入力を与えると、S ₀₁状態 (101) に遷移します。
    • S ₀₁状態のセルは、入力が与えられない場合、南向きの通常の透過状態（1010）に遷移します。
    • S ₀₁状態のセルに入力を与えると、東向きの特殊伝達状態（1011）に遷移する。
• S状態の細胞に_入力を与えると、S1状態に遷移する（11）
  • S ₁状態のセルは、入力が与えられない場合、 S ₁₀状態 (110) に遷移します。
    • S ₁₀状態のセルは、入力が与えられない場合、北向きの特殊伝達状態（1100）に遷移する。
    • S ₁₀状態のセルに入力があると、西向きの特殊伝送状態（1101）に遷移する。
  • S ₁状態のセルに入力を与えると、S ₁₁状態 (111) に遷移します。
    • S ₁₁状態のセルは、入力が与えられない場合、南向きの特殊伝達状態（1110）に遷移する。
    • S ₁₁状態の細胞は、入力を受けると静止合流状態C ₀₀（1111）に遷移する。

ご了承ください：

• 東向きまたは北向きの通常の透過状態を構築するには、他の状態（最初の感作後3サイクルの入力が必要）よりも1サイクル多い入力（最初の感作後4サイクル）が必要である。
• 構築の結果生じる「デフォルト」の静止状態は、東向きの通常の透過状態です。これには、最初の感作入力と、その後の 4 サイクルの入力なしが必要です。

• 特殊伝達状態セルから合流状態セルへの入力により、合流状態セルは基底状態に戻ります。
• 同様に、特殊透過状態セルから通常透過状態セルへの入力により、通常透過状態セルは基底状態に戻ります。
• 逆に、通常の透過状態セルから特殊な透過状態セルに入力すると、特殊な透過状態セルは基底状態に戻ります。

• コッドのセルオートマトン
• ラングトンループ
• フォン・ノイマンの万能構築子
• ワイヤーワールド

• フォン・ノイマン、J.およびAWバークス（1966年）。自己増殖オートマトン理論。アーバナ、イリノイ大学出版局。[1]

• Golly - フォン・ノイマンの CA とライフゲーム、およびその他のルールセットをサポートします。