Симметричная машина Тьюринга

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

Определение

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

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

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

SL=L

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

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

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

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

Ссылки

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