Универсальное моделирование машин Тьюринга

Пусть - фиксированная функция, построенная по времени.$f$

Классический универсальный результат моделирования для ТМ (Hennie and Stearns, 1966) гласит, что существует ТМ с двумя лентами , для которого$U$

• описание МТ , и$\langle M \rangle$
• входная строка ,$x$

работает для шагов и возвращает ответ M на x . А g можно принять за любую функцию из ω ( f ( n ) lg f ( n ) ) .$g(|x|)$$M$$x$$g$$\omega(f(n)\lg f(n))$

Мои вопросы:

1. Какой самый известный результат моделирования на одной ленте TM? Приведенный выше результат также остается в силе?

2. Есть ли улучшения в [HS66]? Можем ли мы смоделировать ТМ на двухмоточной ТМ для шагов быстрее? Можем ли мы взять g ( n ) в ω ( f ( n ) ) вместо ω ( f ( n ) lg f ( n ) ) ?$f(n)$$g(n)$$\omega(f(n))$$\omega(f(n)\lg f(n))$

Какой самый известный результат моделирования на одной ленте TM? Приведенный выше результат также остается в силе?

Мы можем смоделировать ТМ с несколькими лентами на ТМ с одной лентой с квадратичным увеличением времени. Время моделирования . Требуется квадратичное увеличение, поскольку существуют языки (например, палиндромы), которые требуют времени Ω ( n 2 ) для одноленточного DTM, но могут быть решены за время O ( n ) для двухленточного DTM.$O(n^2)$$\Omega(n^2)$$O(n)$

Короче говоря, приведенный выше результат не работает, когда симулятор представляет собой одноленточную ТМ.

Для моделирования однослойных ТМ на одноленточной ТМ (с произвольным конечным алфавитом) результат остается верным, т.е. моделирование может быть выполнено с увеличением коэффициента во времени. Смотрите (2) и (3). Ссылка, кажется, (6).$\lg$

Есть ли улучшения в [HS66]? Можем ли мы смоделировать ТМ на двухмоточной ТМ для шагов быстрее? Можем ли мы взять g ( n ) в ω ( f ( n ) ) вместо ω ( f ( n ) lg f ( n ) ) ?$f(n)$$g(n)$$\omega(f(n))$$\omega(f(n)\lg f(n))$

Кажется, что никаких улучшений не произошло, поскольку это означало бы лучшую теорему иерархии времени, чем известно в настоящее время.

Исправление: Обычные теоремы иерархии основаны на классах сложности времени, определенных с использованием одиночных ленточных ТМ. Для лентных ТМ жесткий результат, аналогичный теореме о пространственной иерархии, доказан Фюрером в 1982 году (5). Коэффициент lg не нужен. Также см. (4).$n$$\lg$

Ссылки:

1. Питер ван Эмде Боас, "Модели машин и моделирование", в Справочнике по теоретической информатике, 1990
   (в частности, стр. 18-21)

2. Майкл Сипсер, «Введение в теорию вычислений», 2006
   (классы сложности времени определяются с использованием ТМ с бесконечной одноленточной в обоих направлениях и произвольным конечным алфавитом, см. Стр. 140 и 341)

3. Одифредди, "Классическая теория рекурсии", вып. I & II, 1989 и 1999
   (определения аналогичны Sipser, см. Определение I.4.1 в томе I стр. 48, определение VII.4.1 в томе II стр. 67 и Thm. VII.4.15 в томе II стр. 83)

4. Пьерджорджо Одифредди, "Классическая теория рекурсии", вып. II, 1999
   (стр. 84)

5. Мартин Фюрер, « Жесткая детерминистическая иерархия времени », 1982

6. Юрис Хартманис, " Вычислительная сложность вычислений на одной ленточной машине Тьюринга ", 1968

7. ФК Хенни и Р. Э. Стеарнс, " Моделирование многоленточных машин Тьюринга с двумя лентами ", 1966

8. Другие связанные вопросы:

   1. Нижние границы и разделение классов ,
   2. $\lg f$
   3. Азбука одноленточной машины Тьюринга ,
   4. Для теоремы иерархии времени, как ввод эффективно переведен? ,
   5. комментарий Луки Тревизана.