Simulation of circuits of functional elements by the universal Turing machine

摘要

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. This research was supported by the Russian Foundation for Basic Research, grants 02-01-00985 and 00-15-96103.