ムーア近傍とノイマン近傍のセルオートマトンの相互変換

いわゆる二次元セルオートマトンで用いられる格子として、4つの近傍を持つノイマン近傍と8つの近傍を持つムーア近傍が有名ですが、状態や遷移関数を操作して、同じ「振る舞い」を維持しつつそれらを互いに変換できるか考えてみました。

ノイマン近傍からムーア近傍へ

これは単純に斜めに接している点の情報を無視すればよいだけで、状態に変更を加えること無く実現できます。

ムーア近傍からノイマン近傍へ

なんとかして斜めの点の情報を持ってくる必要があるので、ステップを拡散と適用の二種類に分けます。

まず拡散ステップでは、ある点の状態を周囲の点のテンポラリな状態に保存しておきます。
これで、次のステップではマンハッタン距離2以下の点の情報は全て手に入れられるようになります。

次に、適用ステップではそれらのデータをもとの遷移関数に適用します。このとき、参照の仕方にはある程度任意性があって、例えば図の赤色のセルが青色の代わりに使えたりします。

そしてこれらの2ステップを交互に実行するため、状態に1bitの時間に関する情報を追加します。つまり元の状態がだとすると、になります。

しかし

どうもこれらの変換には無駄があるような気がしますし、特にムーア近傍からノイマン近傍への変換で、遷移関数をうまく分解出来ると、テンポラリ領域の容量を小さくできるかもしれません。

追記 (2011/7/11)

ムーア近傍からノイマン近傍への変換で、適用ステップでの中心のセルの状態を、周囲の点から参照すれば、二種類のステップは同時に実行できても不要になります。