Modeling circuits consisting of functional elements on a 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_2L(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.