Моделирование схем из функциональных элементов на универсальной машине Тьюринга

Рассматривается время моделирования булевых схем на машине Тьюринга с тремя лентами, одна из которых используется для хранения программы, управляющей работой машины. Установлено, что для любой схемы $S$ найдется такая программа $P$, что время моделирования $T(P)$ схемы $S$ удовлетворяет соотношению $T(P)=O(L(S)\log_2L(S))$, где $L(S)$ — сложность схемы $S$. Показано, что для некоторых схем данное соотношение является точным, то есть для них существуют нижние оценки $T(P)$ того же порядка.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 02–01–00985 и 00–15–96103.