Симметричная машина Тьюринга - Symmetric Turing machine

А симметричная машина Тьюринга это Машина Тьюринга который имеет граф конфигурации это неориентированное (то есть конфигурация i дает конфигурацию j тогда и только тогда, когда j дает i).

Определение симметричных машин Тьюринга

Формально мы определяем вариант машин Тьюринга с набором переходов вида (p, ab, D, cd, q), куда р, д государства, ab, cd пары символов и D это направление. Если D является оставили, то голова машины в состоянии п над символом ленты б перед символом а можно переключить, сдвинув голову влево, изменив состояние на q и заменив символ а, б к CD. Обратный переход (q, cd, -D, ab, p) всегда можно применить. Если D Правильно переход аналогичный. Возможность взглянуть на два символа и изменить оба одновременно несущественна, но упрощает определение.

Такие машины были впервые определены в 1982 г. Гарри Р. Льюис и Христос Пападимитриу,[1][2] кто искал класс для размещения USTCON, проблема, спрашивающая, существует ли путь между двумя заданными вершинами s, t в неориентированном графе. До этого времени его можно было разместить только в NL, несмотря на то, что не требует недетерминизм (асимметричный вариант STCON была известна как полная для NL). Симметричные машины Тьюринга - это разновидность машин Тьюринга с ограниченной недетерминированной мощностью, и было показано, что они не менее мощны, чем детерминированные машины Тьюринга, что дает интересный промежуточный случай.

STIME (T (n)) - это класс языков, принимаемых симметричной машиной Тьюринга, работающей за время O (T (n)). Можно легко доказать, что STIME (T) = NTIME (T), ограничив недетерминизм любой машины в NTIME (T) до начальной стадии, когда строка символов записывается недетерминированно, после чего следуют детерминированные вычисления.

SL = L

Основная статья: SL (сложность)

SSPACE (S (n)) - это класс языков, принятых симметричной машиной Тьюринга, работающей в пространстве O (S (n)) и SL = SSPACE (журнал (n)).

SL эквивалентно можно определить как класс задач пространство журнала сводится к USTCON. Льюис и Пападимитриу по своему определению показали это, построив недетерминированную машину для USTCON со свойствами, которые, как они показали, достаточны для создания эквивалентной симметричной машины Тьюринга. Затем они заметили, что любой язык в SL представляет собой лог-пространство, сводимое к USTCON, поскольку из свойств симметричного вычисления мы можем рассматривать специальную конфигурацию как неориентированные ребра графа.

В 2004 г. Омер Рейнгольд доказал, что SL = L, показав детерминированный алгоритм для USTCON, работающий в логарифмическом пространстве,[3] за что он получил 2005 Премия Грейс Мюррей Хоппер и (вместе с Ави Вигдерсон и Салил Вадхан ) 2009 год Премия Гёделя. Доказательство использует зигзагообразный продукт эффективно построить графики расширения.

Примечания

  1. ^ Йеспер Янссон. Детерминированные алгоритмы связности графов с ограниченным пространством. Рукопись. 1998 г.
  2. ^ Гарри Р. Льюис и Христос Х. Пападимитриу. Симметричные вычисления в ограниченном пространстве. Теоретическая информатика. С. 161-187. 1982 г.
  3. ^ Рейнгольд, Омер (2008), «Ненаправленное подключение в лог-пространстве», Журнал ACM, 55 (4): 1–24, Дои:10.1145/1391289.1391291, МИСТЕР  2445014, ECCC  TR04-094

Рекомендации

  • Лекция: CS369E: Расширения в компьютерных науках Синтия Дворк и Прахлад Харша
  • Конспект лекций
  • Конспект лекции Шэрон Брукнер
  • Детерминированные пространственно-ограниченные алгоритмы связности графов Джеспер Янсон