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

Результат исследований: Научные публикации в периодических изданияхстатья

Аннотация

В качестве сложностной характеристики алгоритма рассматривается его совместная ограниченность по времени и по зоне. Для совместно ограниченные сверху по времени и по зоне алгоритмов Маркова -- Поста и совместно ограниченные сверху по времени и по зоне многоленточных машин Тьюринга доказана их взаимозаменяемость с точностью до линейной функции по зоне и полинома по времени машины Тьюринга соответственно при доказательстве сложностных характеристик алгоритмов. При этом используются не более чем двухбуквенные расширения внешнего алфавита. Доказаны теоремы.
Язык оригиналарусский
Страницы (с-по)191-194
ЖурналВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ
Номер выпуска2
СостояниеОпубликовано - 2015
Опубликовано для внешнего пользованияДа

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

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

Цитировать