Article ID Journal Published Year Pages File Type
4951237 Journal of Computer and System Sciences 2017 11 Pages PDF
Abstract
We propose a highly parallel and distributed multiset computing model having as its underlying structure an undirected graph whose nodes are processors, each endowed with a polarity and with a set of rules all of the same kind, one of increment, decrement or substitution. Processors communicate with each other via a protocol based on the compatibility between their polarization and the polarization of the data, as computed by a valuation mapping. We show that this model can simulate any multiset Turing machine. In its turn, the new model can be simulated by the most general variant of multiset Turing machine.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,