1ビット通信セルラ・オートマトン上での非正則数列生成アルゴリズムについて(セッション2)

概要

論文の詳細を見る
セルラ・オートマトンは,John von Neumannによって考案された.自己複製機械の研究で考案されたセルラ・オートマトンであるが,現在では複雑系などの多くの分野で研究がなされている.これらの研究では,セル間の通信量については言及されていない.Mazoyer,Umeoらにより,セル間通信量を1ビットに制限されたモデルであるCA_<1-bit>が考案され,従来のモデルで考察されている問題に対して,同一時間で解決できるCA_<1-bit>のアルゴリズムが存在することを明らかにした.{2^n|n=1,2,3...},Fibonacciなどいくつかのnon-regularな数列が,CA_<1-bit>上で実時間で生成可能なことが知られている.本稿では,数列{n^2|n=1,2,3...},数列{3^n|n=1,2,3...}の生成アルゴリズムをCA_<1-bit>上に実装し,それぞれ内部状態が3,3,遷移規則数が7,8のCA_<1-bit>で実現可能なことを示す.また,パーソナルコンピュータを使用して, これらのアルゴリズムが内部状態数についての最適解であることを示す.
一般社団法人情報処理学会の論文
2007-05-17