Geodesic
Modeling circuits consisting of functional elements on a universal Turing machine
Diskretnaya Matematika, Tome 16 (2004) no. 2, pp. 98-103
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2004},
     volume = {16},
     number = {2},
     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
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
%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/

[1] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, Moskva, 1979 | MR | Zbl

[2] Maltsev A..I., Algoritmy i rekursivnye funktsii, Nauka, Moskva, 1986 | MR

[3] Sevidzh D..E., Slozhnost vychislenii, Mir, Moskva, 1998

[4] Khenni F..K., Stirnz R. E., “Modelirovanie mnogolentochnoi mashiny Tyuringa na dvulentochnoi”, Problemy matematicheskoi logiki, Mir, Moskva, 1970, 194–212

[5] Khenni F. K., “Vychisleniya na mashinakh Tyuringa so vkhodom”, Problemy matematicheskoi logiki, Mir, Moskva, 1970, 249–270

[6] Shtoss G. I., Slozhnost vychislenii i algoritmov, Mir, Moskva, 1974, 199–212

[7] Shtoss G. I., “$k$-lentochnoe modelirovanie $k$-golovochnykh mashin Tyuringa”, Slozhnost vychislenii i algoritmov, Mir, Moskva, 1974, 190–198

[8] Schnorr C. P., “The network complexity and the Turing machine complexity of finite functions”, Acta Inform., 7 (1976), 95–107 | DOI | MR | Zbl

[9] Chashkin A. V., “Modelirovanie skhem iz funktsionalnykh elementov mashinami Tyuringa”, Diskretnyi analiz i issledovanie operatsii, 1999 \vo l6, no. 3, 42–70 | MR | Zbl

[10] Lupanov O. B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem – printsipe lokalnogo kodirovaniya”, Probl. kibern., 14 (1965), 31–110 | MR | Zbl