Совместные ограничения сверху зоны и времени для взаимного моделирования машин Тьюринга и алгоритмов Маркова-Поста

Авторы

  • Николай Кириллович Косовский Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7-9;
  • Татьяна Матвеевна Косовская Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7-9;
  • Николай Николаевич Косовский Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7-9;

Аннотация

Доказано, что использование совместно ограниченных сверху по времени и по зоне алгоритмов Маркова-Поста и многоленточных машин Тьюринга взаимозаменяемо с точностью до линейной функции по зоне и полинома по времени машины Тьюринга соответственно. При этом используются не более чем двухбуквенные расширения внешнего алфавита. Библиогр. 4 назв.

Ключевые слова:

машина Тьюринга, алгоритм Маркова-Поста, временная и зональная сложность алгоритмов, совместные верхние ограничения сложности

Скачивания

Данные скачивания пока недоступны.

Загрузки

Опубликован

01.05.2015

Как цитировать

Косовский, Н. К., Косовская, Т. М., & Косовский, Н. Н. (2015). Совместные ограничения сверху зоны и времени для взаимного моделирования машин Тьюринга и алгоритмов Маркова-Поста. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 2(2), 190–193. извлечено от https://math-mech-astr-journal.spbu.ru/article/view/11148

Выпуск

Том 2 № 2 (2015)

Раздел

Математика

Лицензия

Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.

Наиболее читаемые статьи этого автора (авторов)