In this paper we consider three variants of accepting networks of evolutionary processors. It is known that two of them 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. We also discuss the possibility of constructing simulations that preserve not only complexity, but also the shape of the simulated network.
Complexity-preserving simulations among three variants of accepting networks of evolutionary processors / Bottoni, Paolo Gaspare; Labella, Anna; Florin, Manea; Victor, Mitrana; Ion, Petre; Jose M., Sempere. - In: NATURAL COMPUTING. - ISSN 1567-7818. - STAMPA. - 10:1(2011), pp. 429-445. [10.1007/s11047-010-9238-5]
Complexity-preserving simulations among three variants of accepting networks of evolutionary processors
BOTTONI, Paolo Gaspare;LABELLA, Anna;
2011
Abstract
In this paper we consider three variants of accepting networks of evolutionary processors. It is known that two of them 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. We also discuss the possibility of constructing simulations that preserve not only complexity, but also the shape of the simulated network.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.