|
Дискретн. анализ и исслед. опер., сер. 1, 1999, том 6, номер 3, страницы 42–70
(Mi da321)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Моделирование схем из функциональных элементов машинами Тьюринга
А. В. Чашкин Московский государственный университет им. М. В. Ломоносова, механико-математический факультет
Аннотация:
Рассматривается моделирование схем из функциональных элементов универсальными многоленточными машинами Тьюринга. Информация о моделируемой схеме записана на одной из лент машины. Показано, что время моделирования произвольной схемы $S$, состоящей из $L(S)$ элементов, на двухленточной универсальной машине Тьюринга при достаточно большом $L(S)$ не превосходит величины $L(S)^{1+\mathscr O(1/\sqrt{\log_2L(S)})}$. Библиогр. 11.
Полный текст:
PDF файл (2909 kB)
Реферативные базы данных:
УДК:
519.7 Статья поступила: 02.04.1998
Образец цитирования:
А. В. Чашкин, “Моделирование схем из функциональных элементов машинами Тьюринга”, Дискретн. анализ и исслед. опер., сер. 1, 6:3 (1999), 42–70
Цитирование в формате AMSBIB
\RBibitem{Cha99}
\by А.~В.~Чашкин
\paper Моделирование схем из функциональных элементов машинами Тьюринга
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 1999
\vol 6
\issue 3
\pages 42--70
\mathnet{http://mi.mathnet.ru/da321}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1762286}
\zmath{https://zbmath.org/?q=an:0931.68041}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da321 http://mi.mathnet.ru/rus/da/v6/s1/i3/p42
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
А. В. Чашкин, “Моделирование схем из функциональных элементов на универсальной машине Тьюринга”, Дискрет. матем., 16:2 (2004), 98–103
; A. V. Chashkin, “Modeling circuits consisting of functional elements on a universal Turing machine”, Discrete Math. Appl., 14:3 (2004), 267–272 -
А. В. Чашкин, “Моделирование неветвящихся программ с условной остановкой на универсальной машине Тьюринга”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 14:1 (2007), 94–109
|
Просмотров: |
Эта страница: | 232 | Полный текст: | 94 |
|