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

q00 → ΛRq1  Состояния  Символ

q10 → 0Rq1  0  1  Λ

q11 → 1Rq2  q0  ΛRq1  1Sq5  0Sq5

q20 → 1Lq3  q1  0Rq1  1Rq2  -

q21 → 1Rq2  q2  1Lq3  1Rq2  ΛLq4 

q31 → 1Lq3  q3  0Lq3  1Lq3  ΛRq0

q30 → 0Lq3  q4  0Lq4  ΛLq4  0Sq5

q3Λ → ΛRq0  q5  -  ΛRq5  -

q2Λ → ΛLq4 *

q41 → ΛLq4  Таблица 1.  Программа  вычисления  функции  ⎮m - n⎮, 

q40 → 0Lq4  где  функция  переходов  задается  таблицей

q4Λ → 0Sq5

q01 → 1Sq5 *

q51 → ΛRq5

  Машина  Тьюринга  M  допускает (отвергает)  слово  ω∈ X*,  если  она  останавливается  на  нем,  придя  в  допускающее (заключительное)  состояние.  Машина  допускает  язык  L⊆ X*,  если  она  допускает  все  слова  языка  L. Машина  M  распознает  язык  L⊆ X*,  если  она  допускает  все  слова  из  L  и  останавливается  на  словах  из  X*  \ L,  не  находясь  в  заключитель ном  состоянии. Языки,  допускаемые  машиной  Тьюринга, назовем  рекурсивно перечислимым.

  Язык  L  допускается  (распознается)  за  полиномиальное  время, если  существует  машина  M, которая  допускает  (распознает)  язык  L, причем  всякое  слово  ω∈ L  допускается (распознается)  за  время  O(nk), где  n – длина слова  ω,  а  k – не зависящее  от  ω  число.

  Теперь  можно  определить  класс  P,  как  множество  языков  L⊆ {0,1}*, распознаваемых  за  полиномиальное  время. 

Теорема.  Класс P  есть множество языков, допускаемых  за  полиномиальное  время.

Доказательство. В  одну  сторону  тривиально, если  машина  M  распознает  язык  L, то она и допускает язык  L.  Обратно,  пусть  язык  L  допускается  машиной  M  за  время  O(nk),  т. е. существует  константа  c, что  любое  слово  из  L  длины  n  допускается  не  более, чем  за  T = c⋅nk  шагов. С  другой стороны, слова, не принадлежащие  L,  не  допускаются  ни  за  какое  время. Построим  машину  M *,  которая  на  слове  ω  моделирует  не более  Т = c⋅nk  шагов  машины  M и  останавливается, выдавая  1, если  M(ω)=1,  в  противном  случае - останавливается,  сделав  Т = c⋅nk  шагов,  выдавая  на  выход  0.  Таким  образом,  машина  M *  распознает  язык  L  и  сложностной  класс P  можно  рассматривать,  как  множество  языков,  допускаемых  за  полиномиальное  время.

Многоленточная  машина  Тьюринга.

Для  имитации  работы  компьютера  используются  многоленточные  машины  Тьюринга.  В  начальной  конфигурации  многоленточной  машины  на  первой  ленте  размещается  вход  (конечная последовательность символов, куда  не входит  Λ),  все  клетки  остальных  лент  содержат  символ  Λ,  считывающие  головки  всех  лент  находятся  в  начальном  состоянии. 

За  один  переход  осуществляются  следующие  действия:

управление  переходит  в  новое  состояние,  на  каждой  ленте  записывается  новый (или  тот  же) символ; считывающие  головки  каждой  из  лент  независимо  сдвигаются  на  одну  ячейку  (R, L,S). 

Языки,  допускаемые  одноленточными  машинами  Тьюринга,  рекурсивно  перечислимы.  Допустимы  ли  многоленточными  машинами  не  рекурсивно  перечислимые  языки?  Ответ  в следующей  теореме. 

Теорема.  Каждый  язык  L,  допускаемый  многоленточной  машиной  Тьюринга, рекурсивно  перечислим.

Доказательство. Одноленточную  машину  Тьюринга  можно  представить,  как  многодорожечную,  задавая  ее  аргументы  в  виде  кортежей. При  этом  одна  дорожка  хранит  данные,  а  другая  отметку. Смоделируем  k - ленточную  машину  M  как  многодорожечную  машину  N, содержащую  2k  дорожек,  где  каждая  вторая  содержит  маркер,  указывающий  позицию  головки  соответствующей  ленты.  Машина  N  должна  посетить  каждый  из  маркеров  головок k  лент  и  изменить  соответствующим  образом  символ, представляющий  соответствующую  ленту,  перемещая  маркер  в  том  направлении,  как  это  происходило  на  соответствующей  ленте.  Наконец,  N  изменяет  состояние  М, записанное  в  конечном  управлении  N.  В  качестве  допускающих  состояний  N  выбираются  все  те  состояния,  в  которых  запоминалось  допускающее  состояние  M. Таким  образом,  машина  M и  N одновременно  допускают  язык  L.  Но  все  языки,  допускаемые  одноленточной  машиной  N,  рекурсивно  перечислимы, поэтому  рекурсивно  перечислимы  все  языки, допускаемые  многоленточной машиной  M.

Теорема.  Время,  необходимое  одноленточной  машине  N  для  имитации  n  переходов  k-ленточной  машины  M,  есть  O(n2).

Доказательство.  После  n  переходов  машины  M маркеры  головок  разделены  не  более,  чем  2n  клетками,  так  что  и  машине  N  надо  сдвинуться  не  более,  чем  на  2n  клеток  вправо,  чтобы  найти  все  маркеры  головок.  Теперь  ей  надо  совершить  проход  влево,  изменяя  содержимое  M  лент  и  сдвигая  головочные  маркеры,  что  потребует  не  более  2n  сдвигов  влево  плюс  не  более  2k  переходов  для  изменения  направления  движения  и  записи  маркера  в  клетку.  Таким  образом,  число  переходов  N  для  имитации  одного  из  переходов  машины  M  не  более  4n+2k,  т. е.  O(n).  Для  n  переходов  требуется  времени  в  n  раз  больше,  т. е.  O(n2).

  Различие  во  времени  вычисления  на  машинах  с  разным  числом  лент  сохраняет  полиномиальную  сложность и для  одноленточной  машины  ограничено  с⋅T(n)2 ,  а  емкость - с⋅S(n) (для  входа  длины  n), где T(n), S(n) – параметры  k-ленточных  машин.  Зависимость  между  емкостью  и  временем  для  k-ленточных  машин  линейная:  S ≤ kT;  для  входа  ω  длины  n  T ≤  ks+n. 

Недетерминированные  машины  Тьюринга.

  По  причинам, которые  вскоре  будут понятны,  недетерминированные  машины  Тьюринга  являются  ключевым  понятием  в  теории  NP-полных  задач. Недетерминированная  машина  Тьюринга  отличается  от  обычной  (детерминированной)  машины  Тьюринга  тем,  что  может  иметь  более  одного  перехода  от  текущей  конфигурации  к следующей.  Недетерминированная  машина  допускает  слово  ω, если  существует  хотя  бы  одна  цепочка  конфигураций,  ведущая  от  начальной  конфигурации  в  заключительную.  Существование  других  последовательностей  конфигураций,  не  ведущих  в  заключительное (допускающее) состояние  не  имеет  значение.  Работу  недетерминированной  машины  на  входе ω  можно  представить  в  виде  дерева,  где  каждый  путь  из  корня  ω  в  лист  представляет  некоторую  последовательность  возможных  шагов  машины. Если  σω  кратчайшая  последовательность  возможных  шагов  работы  машины,  которая  оканчивается  допускающей  конфигурацией,  то  |σω| есть  время,  затраченное  машиной  на  обработку  входа  ω.  Если  на  входе  ω  никакая  последовательность  не  приводит  к  допускающей  конфигурации,  то  время,  затраченное  на  обработку  ω  не  определено.  Считается,  что  недетерминированная  машина  Тьюринга  на  входе  ω  параллельно  выполняет  все  возможные  последовательности  шагов,  пока  не  достигнет  допускающего  состояния  или  окажется,  что  ее  программа  не  применима  к  полученной  конфигурации.