カーティス・ヘドランド・リンドン定理

カーティス・ヘドランド・リンドン定理は、セルオートマトンを記号力学の観点から数学的に特徴づけた定理である。この定理は、モートン・L・カーティス、グスタフ・A・ヘドランド、ロジャー・リンドンにちなんで名付けられた。1969年に発表されたこの定理を記した論文の中で、ヘドランドはカーティスとリンドンを共同発見者として挙げている。^[1]この定理は「記号力学における基本的な成果の一つ」と呼ばれている。^[2]

この定理は、シフト空間からそれ自身への関数が1次元セルオートマトンへの遷移関数を表すための必要十分条件は、それが連続（カントール位相に関して）かつ同変（シフト写像に関して）である場合である、ということを述べている。より一般的には、任意の2つのシフト空間間の射（つまり、シフトと可換な連続写像）は、局所規則によって一様に定義できる写像と全く同じであることを主張している。

ヘドランドの論文における定理のバージョンは1次元有限オートマトンにのみ適用されたが、その後まもなくリチャードソン（1972）^{[3]によって高次元}整数格子への一般化が発表され、さらに格子から離散群へと一般化することができる。この定理の重要な帰結の一つは、可逆セルオートマトンの場合、オートマトン逆ダイナミクスもセルオートマトンによって記述できることである。

定義

アルファベットとは、セルオートマトンにおけるセルの状態を表す有限の記号集合です。構成とは、アルファベットの記号の双無限列です。

...、 x -2 、 x -1 、 x 0 、 x 1 、 x 2 、

...。

配置における位置は整数で、シーケンス内のシンボルの1つのインデックスを表します。位置はセルオートマトン（Cell-Automaton）のセルと考えることができます。パターンとは、有限個の位置の集合と、各位置へのシンボルの割り当てです。

シフト空間は、与えられたアルファベット上のすべての可能な構成の集合である。これは、カントール位相に従って位相空間の構造を持つことができる。この位相空間では、基本開集合は任意の単一のパターンに一致する構成の集合であり、開集合は基本開集合の任意の和集合である。この位相において、構成から構成への関数 $fが$ 連続であるとは、基本開集合 $Pを定義する任意の固定パターン$ $pに対して、$ $fによって$ $P$ にマッピングされる構成の集合 $f$ $-1$ $($ $P$ $)自体が、パターンの（おそらく無限の）集合$ $S$ によって記述でき、構成が $f$ $-1$ $($ $P$ $)に属するのは、それが$ $S$ 内のパターンに一致する場合のみであるという特性を持つときである。

シフトマップとは、シフト空間上の特定の連続関数 $s$ であり、構成 $x を$ 、各シンボルが前の位置から1つシフトした新しい構成 $y$ に変換するものです。つまり、すべての整数 $i$ について、 $y i = x i - 1$ が成り立ちます。関数 $fは、$ $f$ によって記述される構成の変換がシフトマップと可換である場合、シフトマップの下で同変です。つまり、すべての構成 $xについて、$ $f$ $($ $s$ $($ $x$ $)) =$ $s$ $($ $f$ $($ $x$ $))$ が成り立つ必要があります。直感的には、これは、構成のすべての位置が、他のすべての位置と同じ規則を使用して $fによって更新されることを意味します。$

セルオートマトンとは、ある構成の各位置の新しい値を、その位置を囲む事前に固定された有限近傍のセルの値のみに基づいて計算する規則によって定義され、構成のすべての位置は同じ更新規則に基づいて同時に更新されます。つまり、位置の新しい値は、より一般的には前の構成の無制限の数のセルによって決まるのではなく、近傍のセルの値のみの関数です。この規則を使用してセルオートマトンの構成を後続の構成にマッピングする関数 $f$ は、すべての位置が同じ更新規則を使用するという仮定により、シフトマップに関して必然的に同変です。また、カントール位相では必然的に連続です。つまり、 $p が基本開集合$ $P$ を定義する固定パターンである場合、 $f -1 (P)は、$ $p$ $を$ 生成する $p$ の近傍のセルへの割り当てである有限のパターン集合によって定義されます。カーティス・ヘドランド・リンドン定理は、次の 2 つの特性がセルオートマトンを定義するのに十分であると述べています。つまり、すべての連続同変関数はセルオートマトンの更新規則です。

証拠

チェッケリーニ＝シルバーシュタインとコーナートはカーティス・ヘドランド・リンドン定理の次の証明を与えている。^[4]

$f$ はシフト空間上の連続シフト同変関数であるとする。各構成 $x$ について、 $f$ $($ $x$ $)$ のゼロの位置に現れる単一の記号からなるパターンを $p$ とする。 $f$ の連続性により、 q の外側の位置が任意に変更され、 q の内側の位置が x での値に固定されている場合、 f を適用した結果が位置ゼロで同じままになるような、 x 内の有限パターン $q$ が $存在$ する $必要$ が $ある$ 。同様に、 x が Q x に属し、 Q x 内のすべての構成 y について、 f ( x ) と f ( y ) が位置ゼロで同じ値を持つような基本開集合 $Q$ x $が$ $存在$ $する$ $必要$ がある $。$ $これら$ の $基本$ 開集合 $Q$ $x$ $($ $すべて$ の $可能$ $な$ $構成$ $x$ について) $は$ $、$ $シフト$ $空間$ の $開$ 被覆を形成する。ただし、シフト空間はコンパクト空間である。つまり、アルファベットを点とする有限位相空間の積であるため、コンパクト性はティコノフの定理から導かれる。コンパクト性により、すべての開被覆は有限部分被覆を持つ。この有限部分被覆に現れる位置の有限集合は、 $f を$ セルオートマトン規則として記述する際の位置零の近傍として用いることができる。

同じ証明は、より一般的に、整数位置の集合を任意の離散群 $G$ に置き換え、配置空間を $Gから有限アルファベットへの関数の集合に置き換え、シフト同変性を$ $G$ 自身への作用による同変性に置き換えた場合にも適用できる。特に、これは任意の次元の整数グリッド上に定義されたセルオートマトンのケースに適用される。

無限アルファベットの反例

整数の双無限列の空間を考え、 $f$ $($ $x$ $) =$ $y$ ならばすべての位置 $iについて$ $y$ $i$ = $x$ $i$ $+$ $x$ $i$ となる規則に従って、この空間からそれ自身への関数を定義する。この規則は各位置で同じであるため、シフト同変である。また、カントール位相幾何学によれば連続であることが示される。つまり、 y の各有限パターン p に対して $、$ $最大$ で $その$ 2 倍の位置を持つパターンが $xに存在し、$ $p を$ 生成することを強制する。p は $p$ 内のセルと、その値が $p$ にコピーされるセルから構成される。しかし、連続かつ同変であるにもかかわらず、セルオートマトン規則ではない。なぜなら、任意のセルの値は、事前に固定された有限近傍のセルのみに依存するのではなく、他の任意のセルの値に依存する可能性があるからである。^[4] $f$ $f$ $f$

可逆セルオートマトンへの応用

セルオートマトンが可逆的であるとは、オートマトンのあらゆる構成がちょうど1つの先行セルを持つ場合を言う。コンパクト性に関する議論から、各構成をその先行セルに写す関数自体がシフト空間において連続であり、また明らかにシフト不変であることが分かる。したがって、カーティス・ヘドランド・リンドン定理によれば、セルオートマトンの時間反転ダイナミクスは、異なるセルオートマトン規則を用いて生成される可能性がある。^[3]しかし、逆オートマトンにおけるセルの近傍は、順オートマトンにおける同じセルの近傍よりも大幅に大きくなる可能性がある。^[5]^[6]

一般化

セルオートマトンの定義を一般化すれば、ある配置における各位置の新しい値を、その位置を取り囲む有限だが可変の近傍セルの値に基づいて計算する規則によって定義されるマップへと拡張できる。この場合、古典的な定義と同様に、局所規則はすべてのセルに対して同一であるが、近傍セルは位置の周囲の配置の関数でもある。

連続かつシフト同変な写像に対する上記反例は、古典的なセルオートマトンではないが、一般化セルオートマトンの例である。アルファベットが有限である場合、シフト空間のコンパクトさにより、一般化セルオートマトンの定義は古典的なセルオートマトンの定義と一致する。

^{一般化セルオートマトンがSobottka & Gonçalves (2017) [7]}によって提案され、連続シフト等変マップに対応することが証明されました。

参照

接続詞群

参考文献

^ ヘドランド、グスタフ A. (1969)、「シフト力学系の準同型と自己同型」、数学システム理論、3 (4): 320– 375、doi :10.1007/BF01691062、S2CID 21803927。
^ Šunić, Zoran (2014)、「セルラーオートマトンと群、Tullio Ceccherini-SilbersteinとMichel Coornaert著（書評）」、アメリカ数学会報、51 (2): 361– 366、doi : 10.1090/S0273-0979-2013-01425-3。
^ ab リチャードソン、ダニエル (1972)、「局所変換によるテッセレーション」、コンピュータとシステム科学ジャーナル、6 (5): 373– 388、doi : 10.1016/S0022-0000(72)80009-6、MR 0319678。
^ ab Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010)、「定理1.8.1（Curtis–Hedlund定理）」、Cellular Automata and Groups、Springer Monographs in Mathematics、Springer-Verlag、p. 20、ISBN 978-3-642-14033-4。
^ マーゲンシュテルン、モーリス（2007年）、双曲空間におけるセルオートマトン - 巻I、第1巻、Archives contemporaines、p. 134、ISBN 978-2-84703-033-4。
^ Kari, Jarkko (2005)、「可逆セルラーオートマトン」（PDF）、言語理論の発展、コンピュータサイエンスの講義ノート、第3572巻、Springer-Verlag、pp. 2– 23、doi :10.1007/11505877_5、ISBN 978-3-540-26546-7。
^ Sobottka, Marcelo; Gonçalves, Daniel (2017)、「スライディングブロック符号の定義とCurtis-Hedlund-Lyndon定理に関する注記」、Journal of Cellular Automata、12 ( 3–4 ): 209– 215、arXiv : 1507.02180

[1] ヘドランド、グスタフ A. (1969)、「シフト力学系の準同型と自己同型」、数学システム理論、3 (4): 320– 375、doi :10.1007/BF01691062、S2CID 21803927。

[2] Šunić, Zoran (2014)、「セルラーオートマトンと群、Tullio Ceccherini-SilbersteinとMichel Coornaert著（書評）」、アメリカ数学会報、51 (2): 361– 366、doi : 10.1090/S0273-0979-2013-01425-3。

[r72-3] リチャードソン、ダニエル (1972)、「局所変換によるテッセレーション」、コンピュータとシステム科学ジャーナル、6 (5): 373– 388、doi : 10.1016/S0022-0000(72)80009-6、MR 0319678。

[csc-4] Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010)、「定理1.8.1（Curtis–Hedlund定理）」、Cellular Automata and Groups、Springer Monographs in Mathematics、Springer-Verlag、p. 20、ISBN 978-3-642-14033-4。

[5] マーゲンシュテルン、モーリス（2007年）、双曲空間におけるセルオートマトン - 巻I、第1巻、Archives contemporaines、p. 134、ISBN 978-2-84703-033-4。

[6] Kari, Jarkko (2005)、「可逆セルラーオートマトン」（PDF）、言語理論の発展、コンピュータサイエンスの講義ノート、第3572巻、Springer-Verlag、pp. 2– 23、doi :10.1007/11505877_5、ISBN 978-3-540-26546-7。

[SoboGon-7] Sobottka, Marcelo; Gonçalves, Daniel (2017)、「スライディングブロック符号の定義とCurtis-Hedlund-Lyndon定理に関する注記」、Journal of Cellular Automata、12 ( 3–4 ): 209– 215、arXiv : 1507.02180