Симметричная машина Тьюринга
-
Определение и свойства симметричных машин Тьюринга
- Симметричная машина Тьюринга имеет неориентированный граф конфигурации, где переход возможен только в одном направлении.
- Машина может просматривать и изменять два символа одновременно, что упрощает определение.
- Впервые описаны в 1982 году Льюисом и Пападимитриу для решения задачи USTCON.
- Симметричные машины Тьюринга обладают ограниченной недетерминированной мощностью и сравнимы с детерминированными машинами.
-
Временная сложность и пространство
- Класс языков, принимаемых симметричной машиной Тьюринга во времени O(T(n)), называется STIME(T(n)).
- STIME(T) эквивалентен классу задач NTIME(T), если недетерминированность ограничена на начальном этапе.
- SL — класс языков, принимаемых симметричной машиной Тьюринга в пространстве O(S(n)) или O(log(n)).
- SL эквивалентен классу задач logspace, которые сводятся к USTCON.
-
Эквивалентность SL и L
- В 2004 году Омер Рейнгольд доказал, что SL = L, используя детерминированный алгоритм для USTCON.
- Доказательство основано на зигзагообразном продукте для эффективного построения расширяющих графов.
-
Дополнительные ресурсы
- Ссылки на конспекты лекций и алгоритмы связности детерминированных графов.
Полный текст статьи: