Simulation of circuits of functional elements by the universal Turing machine
Александр Викторович Чашкин · Discrete Mathematics and Applications · 2004
We study the time of simulation of Boolean circuits by three-tape Turing machine which uses one of the tapes to store the control program. We find that for any circuit S there exists a program P such that the simulation time T(P) for the circuit S satisfies the relation T(P) = O(L(S) log 2 L(S)) , where L(S) is the complexity of the circuit S . We demonstrate that this estimate is sharp.