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

перейти  к  выполнению  инструкции  по  адресу,  записанному  на  3-й  ленте,  для  чего  лента 3  копируется  на  ленту 2, и  цикл  инструкций  начинается  снова.

4. Выполнив  инструкцию (не  являющуюся переходом),  прибавляем  1  к  счетчику  на  ленте 2  и  вновь  начинаем  цикл  инструкции.

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

Время  работы  машины  Тьюринга, имитирующей  компьютер

Введем  следующие  ограничения  на  модель  компьютера:

  - Ни  одна  компьютерная  инструкция  не  должна  порождать  слово, длиннее,  чем  на  1 бит,  своих  операндов.

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

Назовем  такие  операции  допустимыми.

  Этим  условиям  удовлетворяют  сложение, сдвиг  на  1 бит, сравнение значений,  которые  выполняются  на  многоленточной  машине  Тьюринга  за  0(m)  шагов. А  также умножение  m-битовых целых, если  его  имитировать  с  помощью  m  последовательных  сложений  со  сдвигами  на  1 бит  влево.  Время  выполнения  операции  умножения  будет  пропорционально  квадрату  длины  сомножителей.  .

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

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

  После  выполнения  n  шагов  компьютер  не  может  породить  слово,  длиннее  c+n,  и  не  может  создать  или  использовать  адрес,  занимающий  больше  c+n  битов.  Каждая  инструкция  порождает  не  более  одного  нового  адреса,  получающего  значение,  поэтому  после  выполнения  n  инструкций  имеем  d+n  адресов.  Каждый  адрес-значение  занимает  не  более  2(c+n) +2  разрядов,  а  после  выполнения  n  инструкций  не  больше  2(d+n)(c+n+1),  или  0(n2)

  Для  просмотра  адресов  одной  инструкции  компьютера  требуется  времени  0(n2),  слова  имеют  длину  0(n),  а  инструкции  выполняются  машиной  Тьюринга  за  время  0(n2),  сдвиг  для  создания  пространства  для  нового  слова  включает  копирование  данных  объемом  0(n2)  с  ленты 1  на  рабочую  ленту  и  обратно.  Таким  образом, машина  Тьюринга  имитирует  один  шаг  компьютера  за 0(n2)  своих  шагов,  а  n  шагов  можно  проимитировать  за  0(n3)  шагов  машины  Тьюринга.

Теорема.  Выполнение  n  шагов  работы  компьютера  можно  проимитировать  на  одноленточной  машине  Тьюринга  не  более  чем  за  0(n6)  шагов.

  Таким  образом,  машина  Тьюринга  может  имитировать  память  и  управление  реального  компьютера,  используя  только  одну  ленту  для  записи  всех  элементов  памяти  и  их  содержимого – регистров,  основной  памяти,  дисков  и  других  запомиинающих  устройств.  Отсюда  можно  быть  уверенным,  что  все,  не  выполнимое  машиной  Тьюринга, не  может  быть  вычислено  и  компьютером.

Тема  2.  Неразрешимость.

§ 1.  Неперечислимый  язык.

§ 2.  Коды  машины  Тьюринга.

§ 3.  Язык  диагонализации  Ld.

§ 4.  Рекурсивные  языки.

§ 5.  Универсальный  язык  Lu.

§ 6.  Языки  Le  и  Lne.

§ 7.  Проблема  соответствий  Поста.

Самостоятельные занятия

[1], глава 9.

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

Допускает  ли  машина  Тьюринга  сама  себя  (свой  код)  в  качестве

входа?

Допускает  ли  данная  машина  данный  вход?

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

  Как  уже  было  сказано,  допустимые  машинами  Тьюринга  языки  называются  рекурсивно  перечислимыми.  Допускающие  язык  L  машины  M останавливаются  на  словах (цепочках)  ω∈L=L(M),  а  на  словах  ω∉L  могут  также  останавливаться,  не  допуская,  такие  языки  L  будем  называть  рекурсивными  (разрешимыми),  или  - работать  бесконечно,  назовем  такие  языки  нерекурсивными (неразрешимыми). К  неразрешимым  языкам  отнесем  и  не  рекурсивно  перечислимые (неперечислимые)  языки, существование  которых  нам  предстоит  доказать. 

Неперечислимый  язык.

  Перечислим  машины  Тьюринга  и  входы,  перечисляя  их  коды  в  алфавите  {0,1}.  Пустой  цепочке  припишем  номер  1,  цепочке  “0”  -  номер 2,  цепочке  “1” – номер 3,  цепочке  “00” – номер 4, цепочке  “01” – номер 5, остальное  перечисление  цепочек  становится  очевидным.  В  дальнейшем  цепочку  с  номером  i  будем  обозначать  через  ωi. 

Представим  код  машины  Тьюринга  M  как  двоичную  цепочку.  Состояние  qi  и  ленточный  символ  Xi  кодируются  в  виде  i  нулей,  отделяемых  1,  пустой  символ  кодируется  цепочкой  ω1.  Направления  R, L,S  представим  как  некоторые  цепочки  Dm  из  0. Переход  qi Xj  →  Xl R q k  закодируется  естественным  образом  цепочкой  0i10j10l10m10k  (где  i, j,l, m,k ≥1).  Если  C1,…,Cк  - коды  всех  переходов  машины  Тьюринга,  то  C111С211…11Cк  - код  самой  машины  M. 

  Коды  машин  Тьюринга  представлены  двоичными  цепочками,  которые  в  свою  очередь  являются  представлениями  натуральных  чисел  в  двоичной  системе.  Такое  натуральное  число  будем  считать  номером  машины  в  перечисление  машин  Тьюринга.  Иначе  машина  Mi,  или  i-ая  машина,  Тьюринга  имеет  своим  кодом  цепочку  ωi,  и  номер  i.  Очевидно,  что  не  все  двоичные  цепочки  ωi  являются  правильными  кодами  машин  Тьюринга,  в  этом  случае  будем  считать,  что  машина  Mi  имеет  одно  состояние  и  у  нее  нет  переходов,  т. е.  такая  машина  Mi  останавливается  сразу  на  любом  входе.  Также  для  нее  L(Mi) = ∅.