Ricerc@Sapienza

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.