Методические указания к курсу ”Сложность вычислений” (стр. 15 )

Пример  машины  Тьюринга, использующей  рандомизацию. 

  Используем  многоленточную  машину  Тьюринга (рис. 11.6),  первая  лента  которой  содержит  вход; вторая (случайная  лента) – случайную  последовательность  из  0 и 1,  записываемых  в  пустые  ячейки  на  каждом  шаге  работы  машины;  третья  и  т. д.  ленты – рабочие.

  Реализуем  с  помощью  подобной  машины  версию быстрой сортировки. 

Список  на  первой  ленте  заключен  между  маркерами  и  имеет  длину  m;  используем  log2 m  случайных  битов  второй  ленты,  чтобы  выбрать  случайное  число  между  1  и  m. Помещаем  ведущий  элемент  на  ленту 3. Копируем  с  1-й  ленты  на  ленту  4  элементы,  которые  не  больше  ведущего. Копируем  с  1-й  ленты  на  ленту  5  элементы,  которые  больше  ведущего. Копируем  ленты 4 и 5  на  ленту 1  на  место  входа,  поместив  между  ними  маркер. Если  какой-то  из  подсписков  имеет  более  одного  элемента,  применить  к  нему  этот  же  алгоритм.

Как  и  при  реализации  на  компьютере,  вычисление  на  машине  Тьюринга с  использованием  случайных  битов  на  второй  ленте  требует  O(n log2 n)  времени.

Язык  рандомизированной  машины  Тьюринга.

  Обычная  машина  Тьюринга  всегда  допускает  некоторый  язык,  возможно  пустой.  Рандомизированная  машина  может  вообще  не  допускать  никакого  языка.  Дело  в  том,  что  каждый  вход  w  рандомизированной  машины  имеет  некоторую  вероятность  допускания,  зависящую  от  содержимого  случайной  ленты,  приводящего  к  допусканию. Поскольку  исполь зуется  лишь  конечная  часть  случайной  ленты,  вероятность  любой  случайной  последовательности  равна  2 - m,  где  m -  число  клеток  случайной  ленты,  когда-либо  просмотренных  и  повлиявших  на  переходы  машины  Тьюринга.  Два  примера  дают  представление  о  двух  классах  языков,  допускаемых  рандомизированными  машинами  Тьюринга.

Пример. Функция  переходов  рандомизированной  машины  M  представлена  на  рис.11.7.  Машина  M  не  меняет  символов  входной  ленты, а  только  сдвигает  головки  вправо (R)  или  остается  на  месте (S).  Все  возможные  комбинации  на  1-й  и  2-й  лентах  представлены  0-й  строкой  таблицы (B –пустой  символ);  0-й  столбец – состояний  машины  М.  Клетка  qUVDE  таблицы  означает,  что  МТ  M  переходит  в  состояние  q,  записывает  U  на  входной  ленте  и  V - на  случайной  ленте,  и  сдвигает  головку  на  входной  ленте  в  направлении  D,  а  на  случайной  ленте – в  направлении  E. 

  Можно  описать,  что  делает  машина  на  входной  цепочке,  состоящей  из  0  и  1.  В  начальном  состоянии  q0  машина  M  обозревает  первый  случайный  бит  и  в  зависимости  от  его  значения  делает  следующее:

1.  Если  первый  случайный  бит  равен  0,  то  M  проверяет - состоит  w  только  из  0  или  только  из  1,  в  этом  случае  M  не  изменяет  символы  на  2-й  ленте.

1.1.  Если  первый  бит  w  равен  0,  то  M  переходит  в  состояние  q1  и  движется  через  все  0  вправо  и  останавливается,  не  допуская,  если  встретит 1,  или  переходит  в  допускающее  состояние  q4,  если  встретит  B. 

1.2.  Если  первый  бит  w  равен  1  и  первый  случайный  бит  равен  0,  то  M  переходит  в  состояние  q2  и  допускает,  если  все  биты  w  равны  1. 

2.  Если  первый  случайный  бит  равен  1,  машина  M  сравнивает  w  со  вторым  и  последующими  случайными  битами,  допуская,  если  они  совпали.  Таким  образом,  в  состоянии  q0,  обозревая  1  на  второй  ленте,  M  переходит  в  состояние  q3,  сдвигая  головку  на  случайной  ленте  и  оставляя  на  месте  головку  на  входной.  В  состоянии  q3  проверяет  совпадение  содержания  обеих  лент,  сдвигая  обе  головки  вправо.  Если  обнаруживает  несовпадение,  останавливается,  не  допуская,  а  если  достигает  пробела  на  входной  ленте,  то  допускает. 

  Вычислим  вероятность  допускания  входов. Для  однородных  входов,  где  встречается  только  один  символ  0  или 1.  Если  вход  есть  0i  (i  ≥  1)

с  вероятностью  Ѕ  первый  случайный  бит  равен  0  и  0 i  допускается;  с  вероятностью  Ѕ  первый  случайный  бит  равен  1  и  0 i  допускается

тогда  и  только  тогда, когда  все  случайные  биты,  начиная  со  второго,  равны  0.  Это  возможно  с  вероятностью  2 –i.

Суммарная  вероятность  допускания  входа  0i  есть  1/2+1/2 ⋅2 –i = 1/2+2-( i+1).

  Для  неоднородного  входа  w,  содержащего  как  0,  так  и  1,  вход  не  допускается,  если  первый  случайный  бит  равен  0,  допускается  для  первого  случайного  бита  1  с  вероятность  2 –i,  где  i – длина  входа.  Общая  вероятность  допускания  неоднородных  цепочек  равна  2-( i+1).

  Далее  даны  два  разных  определения  допускания  языков  рандомизированными  машинами.

Класс RP

  Язык  L  класса  RP  допускается  радомизированной  машиной Тьюринга  M  в  следующем  смысле. 

Если  w  не  принадлежит  L,  то  вероятность  того,  что  M  допускает  w  равна  0. Если  w  принадлежит  L, то  вероятность  того,  что  M  допускает  w  не  меньше  Ѕ. Существует  полином  p(n),  для  которого,  если  w  имеет  длину  n,  то  все  вычисления  M,  независимо  от  содержимого  случайной  ленты,  останавливается  не  более,  чем  за  p(n)  шагов.

Пункты  1 и 2  определяют  рандомизированную  МТ  типа  Монте-Карло.

  Рассмотренная  выше  рандомизированная  МТ  (рис.11.13), удовлетворяет  условию 3,  но  не  допускает  никакого  языка  в  смысле  определения  RP.

  Опишем  рандомизированную  МТ,  удовлетворяющую  свойствам  1-3.

Ее  вход  интерпретируется  как  граф,  и  вопрос  состоит  в  том,  есть  ли  в  этом  графе  треугольник,  т. е.  три  узла,  попарно  соединенные  ребрами.  Графы  с  треугольниками  принадлежат  языку  L  из  RP,  без – не  принадлежат. 

  Алгоритм  выбирает  ребро  (x, y)  и  вершину  z,  отличную  от  x  и  y,  случайным  образом.  Каждый  выбор  определяется  просмотром  новых  битов  на  случайной  ленте.  Для  каждой  выбранной  тройки  x, y, z  МТ  проверяет,  входят  ли  ребра  (x, z)  и  (y, z)  в  граф,  тогда  вход  содержит  треугольник.

  Пусть  граф  имеет  n  узлов  и  m  ребер.  Если  граф  имеет  хотя  бы  один треугольник,  то  вероятность  того, что  три  его  узла  будут  выбраны  в  одном  эксперименте,  равна  (3/m)(1/(n-2)),  т. е.  три  из  m  ребер  находятся  в  треугольнике,  и  если  одно  из  них  выбрано,  то  вероятность  того,  что  будет  выбран  и  третий  узел,  равна  1/(n-2).  Если  эксперимент  повторялся  k  раз, то  вероятность  не  выбрать  треугольник  равна 1-(1-3/m(n-2))k.