In this paper we give a direct proof of the fact that the computational power of networks of evolutionary processors and that of networks of evolutionary processors with filtered connections is the same. It is known that both are equivalent to Turing machines. We propose here a direct simulation of one device by the other. Each computational step in one model is simulated in a constant number of computational steps in the other one while a translation via Turing machines squares the time complexity.
Filter Position in Networks of Evolutionary Processors Does Not Matter: A Direct Proof / Bottoni, Paolo Gaspare; Labella, Anna; F., Manea; V., Mitrana; J. M., Sempere. - STAMPA. - 5877:(2009), pp. 1-11. (Intervento presentato al convegno DNA Computing and Molecular Programming, 15th International Conference tenutosi a Fayetteville, Arkansas, USA nel June 8-11, 2009) [10.1007/978-3-642-10604-0_1].
Filter Position in Networks of Evolutionary Processors Does Not Matter: A Direct Proof
BOTTONI, Paolo Gaspare;LABELLA, Anna;
2009
Abstract
In this paper we give a direct proof of the fact that the computational power of networks of evolutionary processors and that of networks of evolutionary processors with filtered connections is the same. It is known that both are equivalent to Turing machines. We propose here a direct simulation of one device by the other. Each computational step in one model is simulated in a constant number of computational steps in the other one while a translation via Turing machines squares the time complexity.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
