Complexity-preserving simulations among three variants of accepting networks of evolutionary processors (Q537856): Difference between revisions

This paper considers three variants of accepting networks of evolutionary processors. Two of them are known to be equivalent to Turing machines. A direct simulation of one device by the other is introduced, where each computational step in one model is simulated in a constant number of computational steps in the other model, whereas a translation via Turing machines squares the time complexity. Moreover, simulations that do not only preserve complexity but also the shape of the considered network are discussed.