このエントリーをはてなブックマークに追加
ID 34802
本文ファイル
著者
Lee, Jia
Zhu, Qing-sheng
キーワード
Cellular automaton
Number-conserving
Brownian motion
Asynchronous circuit
Petri net
Universal computation
NDC
情報科学
抄録(英)
A number-conserving cellular automaton (NCCA) is a cellular automaton in which the states of cells are denoted by integers, and the sum of all of the numbers in a configuration is conserved throughout its evolution. NCCAs have been widely used to model physical systems that are ruled by conservation laws of mass or energy. lmai et al. [13] showed that the local transition function of NCCA can be effectively translated into the sum of a binary flow function over pairs of neighboring cells. In this paper, we explore the computability of NCCAs in which the pairwise number flows are performed at fully asynchronous timings. Despite the randomness that is associated with asynchronous transitions, useful computation still can be accomplished efficiently in the cellular automata through the active exploitation of fluctuations [18]. Specifically, certain numbers may flow randomly fluctuating between forward and backward directions in the cellular space, as if they were subject to Brownian motion. Because random fluctuations promise a powerful resource for searching through a computational state space, the Brownian-like flow of the numbers allows for efficient embedding of logic circuits into our novel asynchronous NCCA.
掲載誌名
Information Sciences
187巻
開始ページ
266
終了ページ
276
出版年月日
2012
出版者
Elsevier Science Inc
ISSN
0020-0255
NCID
出版者DOI
言語
英語
NII資源タイプ
学術雑誌論文
広大資料タイプ
学術雑誌論文
DCMIタイプ
text
フォーマット
application/pdf
著者版フラグ
author
権利情報
This is a preprint of an article submitted for consideration in Information Sciences (c) 2012 Elsevier Inc. ; Information Sciences are available online at ScienceDirect with the open URL of your article;
関連情報URL
部局名
工学研究科