セルオートマトンと記号列上の行列

摘要

1次元セルオートマトンのグローバルな性質はローカルなルールを有向グラフで表現した記号列上の行列の固有値で決まり、数学的には記号列上の行列の固有値問題である。1次元セルオートマトンは直線上の格子点に配置される有限状態を持つ各素子が自分の周辺の素子の状態を見て同じルールで一斉に変換する並列システムである。このローカルなルールは有向グラブで表される。その状態遷移行列は記号列上の行列で、この非可換上の行列の固有値でセルオートマトンの性質が決まる。本論文では固有値によるセルオートマトンの分類と非可換上の行列のスペクトル分解について論じる。