Том 6, серия 1, номер 3, 1999 г., Стр. 42-70
УДК 519.7
А. В. Чашкин
Моделирование схем из функциональных элементов машинами Тьюринга
Аннотация:
Рассматривается моделирование схем из функциональных элементов универсальными многоленточными машинами Тьюринга. Информация о моделируемой схеме записана на одной из лент машины. Показано, что время моделирования произвольной схемы$S$ , состоящей из$L(S)$ элементов, на двухленточной универсальной машине Тьюринга при достаточно большом$L(S)$ не превосходит величины $L(S)^{1+\mathscr O\big(1/\sqrt{\log_2L(S)}\big)}$.
Библиогр. 11.
Чашкин А. В. 1
1. МГУ, мех.-мат. факультет
Воробьевы горы, 119899 Москва, Россия
е-mail: chash@glasnet.ru
Статья поступила 2 апреля 1998 г.
