|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Моделирование схем из функциональных элементов на универсальной машине Тьюринга
А. В. Чашкин
Аннотация:
Рассматривается время моделирования булевых схем на машине Тьюринга с тремя лентами, одна из которых используется для хранения программы, управляющей работой машины. Установлено, что для любой схемы $S$ найдется такая программа $P$, что время моделирования $T(P)$ схемы $S$ удовлетворяет соотношению $T(P)=O(L(S)\log_2L(S))$, где $L(S)$ — сложность схемы $S$. Показано, что для некоторых схем данное соотношение является точным, то есть для них существуют нижние оценки $T(P)$ того же порядка.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 02–01–00985 и 00–15–96103.
Статья поступила: 21.04.2003
Образец цитирования:
А. В. Чашкин, “Моделирование схем из функциональных элементов на универсальной машине Тьюринга”, Дискрет. матем., 16:2 (2004), 98–103; Discrete Math. Appl., 14:3 (2004), 267–272
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm155https://doi.org/10.4213/dm155 https://www.mathnet.ru/rus/dm/v16/i2/p98
|
Статистика просмотров: |
Страница аннотации: | 654 | PDF полного текста: | 348 | Список литературы: | 25 | Первая страница: | 1 |
|