1状態1ビット通信セルラ・オートマトンの数列生成能力について(光カオス,一般)

概要

論文の詳細を見る
セルラ・オートマトン(CA)は,John von Neumannによって考案された。自己複製機械の研究で考案されたセルラ・オートマトンであるが,現在では複雑系などの多くの分野で研究がなされている.これらの研究では,セル間の通信量については言及されていない.Umeoにより,セル間通信量を1ビットに制限されたモデルであるCA_<1-bit>が考案され,従来のCAモデル上で考察されている問題に対して、同一時間で解決できるCA_<1-bit>のアルゴリズムが存在することを明らかにした.Fibonacci数,{2^n|n=1,2,3...},{n^2|n=1,2,3...}などいくつかのnon-regularな数列が,CA_<1-bit>上で実時間で生成可能なことが知られている.本稿では,CA_<1-bit>上での数列生成問題を考察し,1状態CA_<1-bit>上で生成可能な数列並びに,1状態CA_<1-bit>の数列生成能力について明らかにする.
社団法人電子情報通信学会の論文
2007-07-31