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

Симметрична машина Тьюринга является машиной Тьюринга , которая имеет конфигурацию граф , который неориентированный (то есть, конфигурация даю конфигурации я J тогда и только тогда , когда J выходов I).

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

Формально мы определяем вариант машин Тьюринга с набором переходов вида , где p, q - состояния, ab, cd - пары символов, а D - направление. Если D является влево , то голова машины в государственном р над символом ленты Ь предшествует символ а может быть переведена с помощью перемещения головки влево, изменяя состояние к ц и замене символов а, Ь с помощью C, D . Всегда можно применить противоположный переход . Если D прав, переход аналогичен. Возможность взглянуть на два символа и изменить оба одновременно несущественна, но упрощает определение. ${\ displaystyle (p, ab, D, cd, q)}$${\ displaystyle (q, cd, -D, ab, p)}$

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

${\ Displaystyle {\ mathsf {STIME}} (Т (п))}$- это класс языков, принимаемых симметричной машиной Тьюринга, работающей во времени . Это можно легко доказать, ограничив недетерминизм любой машины до начальной стадии, когда строка символов записывается недетерминированно, а затем следуют детерминированные вычисления. ${\ Displaystyle О (Т (п))}$${\ displaystyle {\ mathsf {STIME}} (T) = {\ mathsf {NTIME}} (T)}$${\ displaystyle {\ mathsf {NTIME}} (T)}$

SL = L

SSPACE (S ( n )) - это класс языков, принимаемых симметричной машиной Тьюринга, работающей в пространстве, и SL = SSPACE (log ( n )). ${\ Displaystyle О (S (п))}$

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

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

Примечания

использованная литература

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