Computing by Swarm Networks
Though the regular and fixed structure of cellular automata greatly contributes to their simplicity, it imposes a strict limitation on the applications that can be modeled by them. This paper proposes swarm networks, a model in which cells, unlike in cell
- PDF / 466,336 Bytes
- 10 Pages / 430 x 660 pts Page_size
- 45 Downloads / 168 Views
5
Division of Computer Engineering, University of Hyogo, Japan [email protected] 2 Nano ICT Group, National Institute of Information and Communications Technology, Japan 3 Biological ICT Group, National Institute of Information and Communications Technology, Japan 4 Dept. of Information Engineering, Hiroshima University, Japan Dept. of Computer Science, Osaka Electro-Communication University, Japan
Abstract. Though the regular and fixed structure of cellular automata greatly contributes to their simplicity, it imposes a strict limitation on the applications that can be modeled by them. This paper proposes swarm networks, a model in which cells, unlike in cellular automata, have irregular neighborhoods. Timed asynchronously, a cell in this model acts like an agent that can dynamically interact with a varying set of other cells under the control of transition rules. The configurations in which cells are organized according to their neighborhoods can move around in space, following simple mechanical laws. We prove computational universality of this model by simulating a circuit consisting of asynchronously timed circuit modules. The proposed model may find applications in nanorobotic systems and artifical biological systems.
1
Introduction
Nanorobots, Artificial Cells, Smart Dust—all these models have in common a large number of distributed units that interact with each other to conduct certain tasks. Like in Cellular Automata (CA), the underlying units are relatively simple—usually being nothing more than Finite State Machines—but unlike in CA the units are more dynamic in the way they interact. They form swarms of agents that communicate with each other through dynamic networks of interconnections. How can we characterize the functionality of such swarms? Will their less-rigid communication structures cause a loss of functionality relative to CA models with comparable complexity? Or will swarm networks be more powerful through their more flexible way of interaction? A useful measure of power—useful at least in the world of computer scientists– is whether a model is computationally universal. This measure basically separates “interesting” models from the “uninteresting” ones, forming the major motivation in the last century to characterize models in terms of computability. Universal Turing Machines [1] are well-known in this context, but other models H. Umeo et al. (Eds): ACRI 2008, LNCS 5191, pp. 50–59, 2008. c Springer-Verlag Berlin Heidelberg 2008
Computing by Swarm Networks
51
have been proposed too [2]. In the context of CA, computational universality is often proved by embedding logic circuits on cellular space. This requires a CA to simulate a universal set of primitives, like the AND-gate and the NOT-gate, as well as to simulate signals being propagated between these primitives. Some well-known computationally universal CA are found in [3,4,5,6] when the timing model is synchronous—implying the simultaneous update of all cells at each step. In an asynchronous model, on the other hand, update of c
Data Loading...
