非同期セル・オートマトン
非同期セル・オートマトン(ひどうきセル・オートマトン、英: Asynchronous cellular automaton)はセル・オートマトンの一種であり、それを構成する各セルの状態が他のセルと非同期に更新されるものをいう。
セル・オートマトンは他のマルチエージェント・システムのモデルと同様に、通常は時間を離散的に、そして状態更新が同期的に起こるように扱う。モデルにおける各セルの状態が同時に更新され、他のセルの新しい状態からの影響が及ぶ前に決められる。それに対して非同期セル・オートマトンは各セルが独立に更新され、セルの新しい状態が近傍のセルの状態の計算に影響を与える。
同期的な更新は 2 つのフェーズに分けられる。第 1 のフェーズは相互作用であり、近傍のセルと更新規則に基づいて各セルの新しい状態が計算される。状態値は一時記憶に保持される。第 2 のフェーズにおいては、新しい状態をセルにコピーすることによって状態値を更新する。
それとはちがって、非同期の更新はこのようにフェーズを分離することがなく、状態変化がただちに実現される。この違いを次のように要約することができる。
ここで σ ( t ) {\displaystyle \sigma ^{(t)}} は時刻 t における要素状態のベクトルであり、 τ ^ ( t ) {\displaystyle {\hat {\tau }}^{(t)}} は更新に使用される一時的なコピーであり i は個々の要素のインデクスであり、N はこのモデルにおける総要素数であり、f() は集合 Ki の要素の現在の状態要素の新しい状態を計算する関数である ( | K i | ≤ N {\displaystyle |K_{i}|\leq N} )。
同期アプローチは大域的なクロック同期信号が存在して全セルの同時更新が保証されることを仮定する。これはコンピュータ・システムにおいては便利な仮定だが、そのような機構の存在が示せないときには、たとえば生物システムにおいては、非現実的な仮定である。