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...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2017-04, Vol.253, p.371-380
Main Authors: Arroyo, Fernando, Canaval, Sandra Gómez, Mitrana, Victor, Popescu, Stefan
Format: Article
Language:English
Subjects:
2-tag system
Network of polarized evolutionary processors
Polarized evolutionary processor
Turing machine
Valuation mapping
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2016.06.004