Моделирование многоленточных машин Минского и Тьюринга трехленточными машинами Минскогостатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 4 августа 2021 г.
Аннотация:Показано, что k-ленточную машину Минского, работающую с временем T(n), можно промоделировать трехленточной машиной Минского за время, по порядку не превосходящее T(n)^k x log T(n). Установлено, что многоленточные машины Тьюринга можно промоделировать трехленточными машинами Минского при <<оптимальном>> кодировании слов, записанных на лентах.