caa a22 4500 378896792 CHVBK 20180305123508.0 cr unu---uuuuu 161128e20040701xx s 000 0 eng 10.1515/1569392031905557 doi (NATIONALLICENCE)gruyter-10.1515/1569392031905557 Chashkin A. V. Simulation of circuits of functional elements by the universal Turing machine [Elektronische Daten] [A. V. Chashkin] 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) log2 L(S)), where L(S) is the complexity of the circuit S. We demonstrate that this estimate is sharp. Copyright 2004, Walter de Gruyter Discrete Mathematics and Applications Walter de Gruyter 14/3(2004-07-01), 267-272 0924-9265 14:3<267 2004 14 dma https://doi.org/10.1515/1569392031905557 text/html Onlinezugriff via DOI 1 research article jats NATIONALLICENCE 856 40 https://doi.org/10.1515/1569392031905557 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Chashkin A. V. NATIONALLICENCE 773 0- Discrete Mathematics and Applications Walter de Gruyter 14/3(2004-07-01), 267-272 0924-9265 14:3<267 2004 14 dma CC0 http://creativecommons.org/publicdomain/zero/1.0 nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-gruyter