On the computational power of networks of polarized evolutionary processors

摘要

We consider a new variant of networks of evolutionary processors which seems more suitable for a software and hardware implementation. Each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined, the data polarization is dynamically computed. Consequently, the protocol of communication is naturally defined by this polarization. We show that tag systems can be simulated by these networks with a constant number of nodes, while Turing machines can be efficiently simulated by these networks with a number of nodes depending linearly on the tape alphabet of the Turing machine. We also propose a simulation of Turing machines by networks with a constant number of nodes, which is reflected in an increase of the computation time. Finally, we show that every network can be simulated by a Turing machine and discuss the time complexity of this simulation.