能力の小さい1ビットセルオートマトンで生成可能な数列についての考察  [in Japanese] A Note on Sequences Generated by Small One-bit Cellular Automata  [in Japanese]

Access this Article

Search this Article

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

Codes

  • NII Article ID (NAID)
    170000148489
  • NII NACSIS-CAT ID (NCID)
    AA11464803
  • Text Lang
    JPN
  • Article Type
    article
  • ISSN
    1882-7780
  • Data Source
    IPSJ 
Page Top