能力の小さい1ビットセルオートマトンで生成可能な数列についての考察

• 上川, 直紀

• 梅尾, 博司

Bibliographic Information

Other Title

• A Note on Sequences Generated by Small One-bit Cellular Automata

Abstract

セルオートマトン（CA）はvon Neumannにより考案された並列計算モデルの1つであり，現在では，複雑系などの多くの分野で研究がなされている．CAはセルと呼ばれる有限状態オートマトンにより構成され，セルは自らと，隣接するセルの内部状態という局所的な情報をもとに，自らの内部状態を遷移させる機能しか持たない．しかしながら，この局所的な相互作用がモデル全体に影響を及ぼし，CAは巨大で複雑な事象をシミュレートすることができるという特徴を持つ．本稿では，セル間通信量を1ビットに制限されたモデルCA1-bit上で数列生成問題を考察し，内部状態が少ないCA1-bitで生成可能な数列について言及する．

A model of cellular automata (CA) is considered to be a well-studied non-linear model of complex systems in which an infinite one-dimensional array of finite state machines (cells) updates itself in a synchronous manner according to a uniform local rule. In this paper, we study a sequence generation problem on a special restricted class of cellular automata having 1-bit inter-cell communications (CA1-bit) and show that sequences can be generated in real-time by the CA1-bit with small internal states.

Journal

• 情報処理学会論文誌数理モデル化と応用（TOM）

  情報処理学会論文誌数理モデル化と応用（TOM） 10 (1), 1-13, 2017-03-20

Keywords

• [オリジナル論文] セルオートマトン，セル間通信量，複雑系，並列アルゴリズム，数列生成問題

Details

• CRID: 1050001337908349184
• NII Article ID: 170000148489
• NII Book ID: AA11464803
• ISSN: 18827780
• Web Site: http://id.nii.ac.jp/1001/00178501/
• Text Lang: ja
• Article Type: article
• Data Source:
  • IRDB
  • CiNii Articles