Geodesic
Modeling circuits consisting of functional elements on a universal Turing machine
Diskretnaya Matematika, Tome 16 (2004) no. 2, pp. 98-103

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2004_16_2_a6,
     author = {A. V. Chashkin},
     title = {Modeling circuits consisting of functional elements on a universal {Turing} machine},
     journal = {Diskretnaya Matematika},
     pages = {98--103},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2004_16_2_a6/}
}
TY  - JOUR
AU  - A. V. Chashkin
TI  - Modeling circuits consisting of functional elements on a universal Turing machine
JO  - Diskretnaya Matematika
PY  - 2004
SP  - 98
EP  - 103
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2004_16_2_a6/
LA  - ru
ID  - DM_2004_16_2_a6
ER  - 
%0 Journal Article
%A A. V. Chashkin
%T Modeling circuits consisting of functional elements on a universal Turing machine
%J Diskretnaya Matematika
%D 2004
%P 98-103
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2004_16_2_a6/
%G ru
%F DM_2004_16_2_a6
A. V. Chashkin. Modeling circuits consisting of functional elements on a universal Turing machine. Diskretnaya Matematika, Tome 16 (2004) no. 2, pp. 98-103. http://geodesic.mathdoc.fr/item/DM_2004_16_2_a6/