B104 1ビットセルオートマトン上での数列生成問題(ロジック,アルゴリズム)

概要

論文の詳細を見る
Cellularr automata (CA) are considered to be a nice model of complex systems in which an infinite one-dimensional array of finite state machines (cells) updates itself in synchronous manner according to a uniform local rule. In the long history of the study of CA, generally speaking, the number of internal states of each cell is finite and the local state transition rule is defined in such a way that the state of each cell depends on the previous states of itself and its neighboring cells. Thus, in the finite state description of the CA, the amount of communication bits exchanged at one step between neighboring cells is assumed to be O(1)-bit, however, such a bit-information exchanged between inter-cell has been hidden behind the definition of conventional automata-theoretic finite state description. In this paper, we focus our attention to the communication bits exchanged between neighboring cells and introduce a new class of cellular automata, CA_<1-bit>, whose inter-cell communication is restricted to 1-bit. We call the model 1-bit CA in short. The number of internal states in CA_<1-bit>, is assumed to be finite in a usual way. However, the next state of each cell is determined by the present state of itself and two binary 1-bit inputs from its left and right neighbor cells. Thus the 1-bit CA can be thought to be one of the most powerless and simplest models in a variety of CAs. On the 1-bit CA model we consider a sequence generation problem that was extensively studied on the conventional CA model and propose several real-time infinite non-regular sequence generation algorithms. We not only present those generation algorithms but also give their implementations on a computer. The implementations have been made on 1-bit CAs with a relatively small number of internal states. In spite of its simplicity and communication-restriction of the model, we show that the 1-bit CA is a rich and interesting computational model and it is worthy to be studied further. There have been a great deal of works on conventional cellular automata, however, those works focusing on the amounts of bit-information exchanged in inter-cell communications are very few. As far as the authors know, Mazoyer [5, 6] first studied this model under the name of channel and proposed a time-optimum firing squad synchronization algorithm with only one bit information exchanged. Arisawa [1], Fisher [2], and Korec [4] have considered the sequence generation problem on conventional cellular automata model. Umeo and Inada [12] first defined the sequence generation problem the 1-bit CA model and developed some time-optimal generation algorithms. Kamikawa and Umeo studied the sequence generation problem again on 1-bit CA and developed newly several efficient generation algorithms operating in linear and real-time [15, 16]. First, we introduce the cellular automaton with 1-bit inter-cell communication and define the sequence generation problem on CA_<1-bit>. In section 3 we give a real-time prime generation algorithm on CA_<1-bit>. The algorithm is based on the classical and famous sieve of Eratosthenes and its implementation on a computer will be made on a CA_<1-bit> with 34 internal states and 71 transition rules. In addition, it is shown that infinite non-regular sequences such as {2"│n=1, 2, 3,..}, { n^2│n=1, 2, 3,..} and Fibonacci sequences can be generated in real-time by cellular automata with 1-bit inter-cell communication. Those sequence generation algorithms will be realized on the 1-bit CAs with relatively small number of internal states. For example, a real-time generator of the sequence {2"│n=1, 2, 3,..} is implemented on a CA_<1-bit> with only three states.
2001-11-14

B104 1ビットセルオートマトン上での数列生成問題(ロジック,アルゴリズム)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク