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

Поскольку  по  теореме  машины  M ’  не  существует,  получено  противоречие,  следовательно,  язык Lu  не является  рекурсивным. 

Неразрешимые  проблемы,  связанные  с  машинами  Тьюринга. 

  В  математической  логике  рассматриваются  разные  типы  сведений,  образующие  целую  ветвь  математической  логики,  теорию  степеней  неразрешимости.  В  общем  виде,  проблема  P1  сводима  к  проблеме  P2 

(P1  < f  P2 ),  если  существует  вычислимая  функция  f  такая,  что 

x∈P1  ↔  f(x)∈P2  (x∉P1  ↔  f(x)∉P2).

В  этом  случае говорят, что проблема P2  не  менее трудна,  чем  проблема  P1. 

Теорема.  Если  P1  < f  P2 ,  то 

если  P1  не  является  рекурсивной,  то  P2  также  не  рекурсивна (не-Р); если  P1  не  является  рекурсивно  перечислимой,  то  P2  не  рекурсивно  перечислима  (не-РП).

Доказательство. a)  Допустим,  что P1  не  рекурсивно,  а  P2  рекурсивно.

На  входе  ω∈P1 , так  как P1  < f  P2 ,  то  f(ω)∈P2.  Так  как  P2  рекурсивно,  существует  алгоритм  A:

A(x)=0, если  x∈ P2,  где  x = f(ω), тогда и только тогда,  когда  ω∈ P1;

A(x)=1, если  x∉ P2,  где  x = f(ω),  тогда  и  только  тогда,  когда  ω∉ P1.

Откуда  следует,  что  P1  рекурсивно,  по противоречию  P2 – не  рекурсивно.

Пусть  P1  не-РП,  а  P2 – рекурсивно  перечислимо.  Тогда  P2  имеет  до-

пускающую  ее  машину  M2.  Если  на  входе  x∈ P2  машина  M2  допускает, тогда  ω∈P1 ,  где  x=f(ω);  в  противном  случае  машина  M2  работает  бесконечно,  следовательно,  и  ω∉P1 .  Таким  образом,  машина,  языком  котором  является  P1 ,  допускает  или  не  допускает  свой  вход  одновременно  с  машиной  M2 , и,  следовательно,  допускает  язык  P1,  что противоречит  условию.

  Наряду  с  введенными  выше  языками  Ld  и  Lu  в  теории  сложности  представляют  интерес  взаимо  дополняющие  друг  друга  в  {0,1}* языки:

  Le  =  {M:  L(M) = ∅} (кодов мащин, допускающих  пустой  язык)  и 

  Lne  =  {M: L(M) ≠ ∅}, над  алфавитом  {0,1},  представленные  кодами  машин  Тьюринга.

Теорема.  Язык  Lne  рекурсивно  перечислим. 

Доказательство. Для  доказательства  достаточно  построить  допускающую  язык  Lne  машину  Тьюринга.  Пусть  это  недетерминированная  машина  M,

изображенная  на  рис. 

Рис.  9.8. Конструкция  НМТ, допускающей язык Lne

  Работа  машины  M  состоит  в  следующем:

1)  получив  на  вход  код  машины  Mi  ,  используя  способность  недетерминированной  машины  угадывать  вход  ω,  на  котором  машина  Mi,  воможно,  допускает,

2)  машина  M  проверяет,  допускает  ли  машина  Mi  на  входе  ω,  моделируя  работу  машины  U;

если  (Mi, ω)∈ Lu,  т. е.  машина  Mi  допускает  на  входе  ω,  то  машина

M  также  допускает  на  своем  входе  Mi,  в  противном  случае  работает  бесконечно.

Таким  образом,  L(M) = Lne.

Теорема.  Язык  Lne  не  является  рекурсивным. 

Доказательство.  Построим  функцию (алгоритм),  сводящий  универсальный  язык  Lu  к  языку  Lne,  т. е.  вход  (M,ω)  машины  U  преобразуем  во  вход  машины  M ’,  допускающей  язык  Lne.  Машина  M ’  моделирует  машину  M  на  входе  ω  и  если  (M, ω) ∈ Lu,  то  (M ’, x) ∈ Lu, где  x  произвольный  вход  машины  M ’.  В  этом  случае  машина  M’  допускает  хотя  бы  одну  цепочку,  т. е.  L(M’) ≠∅  и  M ’∈ Lne. Аналогично, в случае,  если  (M,ω) ∉ Lu,  L(M ’ ) = ∅  и  M’  ∈ Lne. Схема  машины  M ’,  построенной  по  (M,ω)  приведена  на  рис.

Машина  M ’  по  построению  выполняет  следующие  действия:

Машина  M ’  строится  по  конкретной  паре  (M,ω),  имеюшей  длину  n,

тогда  q0 ,…,qn  состояния  M ’  (где  q0  - начальное  состояние).

  a)  В  состоянии  qi  (i=0,..,n-1)  машина  M ’  записывает  (i+1)-й  бит  кода 

  (M,ω)  и  переходит  в  состояние qi+1 ,  сдвигаясь  вправо.

  b)  В  состоянии  q n,  в  случае  необходимости,  M ’  сдвигается  вправо  и  заполняет  все  непустые  клетки  (хвост  x,  если  длина  цепочки  x  боль - ше  n)  пробелами.

Когда  M ’  достигает  пробела  с  состоянии qn  ,  она,  используя  похожий  набор  состояний,  перемещает  головку  в  левый  конец  ленты. Используя  дополнительные  состояния  M ’  моделирует  универсальную  машину  U. Если  U  допускает,  то  M ’  допускает.  Если  U  никогда  не  допускает,  то  M ’  никогда  не  допускает.

Из  схемы  работы  машины  видно,  что  если  M  допускает  вход  ω,  то  M ’  допускает  свой  вход  x,  который  первоначально  был  записан  на  ленте,  следовательно, M ’ ∈ Lne.  В  противном  случае, если  M  не  допускает  вход  ω,  то  M ’  не  допускает  любой  свой  вход  x,  записанный  на  ленте,  тогда  M ’ ∉ Lne.  Таким  образом,  Lu  сводимо  к  Lne  с  помощью  алгоритма,  который  строит  M’  по  данным  M  и  ω.  Поскольку, Lu  не  является  рекурсивным, то Lne  также  не  рекурсивен.

  Теперь  известен  и  статус  языка Le. Если  бы  Le  был  бы  рекурсивно  перечислимым,  то  по  теореме  и  он,  и  его  дополнение Lne  были  бы  рекурсивными.  Однако  было  доказано,  что  язык  Lne  не  рекурсивен.

Теорема.  Язык  Le  не  является  рекусивно  перечислимым.

Теорема  Райса  и  свойства  РП-языков

  Неразрешимость  языков  Le  и  Lne  есть  только  частный  случай  более  общей  теоремы  о  неразрешимости  любого  нетривиального  свойства  РП-языков. 

  Свойством  РП-языков  называют  множество  РП-языков.  Например,  свойства  “быть  контексно-свободным  языком”  или  “быть  регулярным  языком”  представлены  соответственно  множествами  контекстно-свободных  и  регулярных  языков.  Тривиальным  свойством  называют  множество  из  одного  пустого  языка  или  из  всех  РП-языков.  В  противном  случае  свойство  называют  нетривиальным.

  Пусть  ℘ - свойство  РП-языков,  а  L℘  - множество  кодов  машин  Mi

таких,  что  L(Mi) ∈℘.

Теорема (Райса).  Всякое  нетривиальное  свойство  РП-языков  неразрешимо.

Доказательство. Пусть  ℘ - свойство  РП-языков  и  (∅∉℘) ∨  (∅∈℘).

a) Допустим,  что  ∅∉℘,  тогда  существует  непустой  язык  L∉℘, пусть  x∈L.  Построим  алгоритм,  сводящий  Lu  к  L℘ . По  паре  (M,ω)  строится  машина  M ’  такая,  что  (M,ω)∈ Lu  ↔ M ’ ∈ L℘: