[1], глава 8.

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

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

M = (X, Q, q ₀, F, I), где

X - внешний алфавит символов (букв на ленте), включающий символ ;

Q - конечный алфавит внутренних состояний;

q₀ - инициальное состояние (начало работы), q₀ Q;

F- множество заключительных состояний, F Q;

I - множество инструкций, или машинных команд, каждая из которых принадлежит множеству

(Q \ F) X {} Q X {R,L,S}.

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

Можно определить функцию переходов

: (Q \ F) X* Q X* {R,L,S}, где X* -слова в алфавите X.

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

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

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

В качестве примера рассмотрим работу детерминированной машины Тьюринга, вычисляющей функцию m - n. Упорядоченную пару натуральных чисел (m,n) представляем как слово 0^m10ⁿ в алфавите X \ {} = {0,1}, ячейки слева и справа от которого содержат символ .

q₀0 Rq₁ Состояния Символ

q₁0 0Rq₁ 0 1

q₁1 1Rq₂ q₀ Rq₁ 1Sq₅ 0Sq₅

q₂0 1Lq₃ q₁ 0Rq₁ 1Rq₂

q₂1 1Rq₂ q₂ 1Lq₃ 1Rq₂ Lq₄

q₃1 1Lq₃ q₃ 0Lq₃ 1Lq₃ Rq₀

q₃0 0Lq₃ q₄ 0Lq₄ Lq₄ 0Sq₅

q₃ Rq₀ q₅ Rq₅

q₂ Lq₄ *

q₄1 Lq₄

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

q₄0 0Lq₄ где функция переходов задается таблицей

q₄ 0Sq₅

q₀1 1Sq₅ *

q₅1 Rq₅

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

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

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

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

Доказательство. В одну сторону тривиально, если машина M распознает язык L, то она и допускает язык L. Обратно, пусть язык L допускается машиной M за время O(n^k), т.е. существует константа c, что любое слово из L длины n допускается не более, чем за T = cn^k шагов. С другой стороны, слова, не принадлежащие L, не допускаются ни за какое время. Построим машину M , которая на слове моделирует не более Т = cn^k шагов машины M и останавливается, выдавая 1, если M()=1, в противном случае - останавливается, сделав Т = cn^k шагов, выдавая на выход 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(n²).

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

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

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

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

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

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

Обозначим через L(M) множество всех слов X*, допускаемых машиной M, L(M) называют языком машины M.

Теорема. Если M недетерминированная машина с полиномиальной временной сложностью T(n), то существует детерминированная машина M ', с L(M ' ) = L(M) и временной сложностью O(c^T(n)).

Доказательство. Доказательство основывается на том, что для любой недетерминированной машины Тьюринга M строится детерминированная машина M ', которая исследует последовательности конфигураций (пути в дереве недетерминированной машины) и если находит хотя бы одну с допускаемым состоянием, то сама переходит в допускаемое состояние. Обследованные конфигурации помещаются в очередь, длины k (k=1,2…) Построим детерминированную многоленточную машину M ', моделирующую недетерминированную машину M. Первая лента машины M ' хранит последовательность конфигураций машины M и метку на текущее состояние последней. Записи слева от метки предполагаются исследованными и их в дальнейшем игнорируют. Конфигурации справа рассматриваются в порядке очереди. Программа машины M хранится в конечном управлении M '. Обработка текущей конфигурации на первой ленте состоит в следующем:

- Машина M ' проверяет состояние и обозреваемый символ и, если состояние допускающее, также переходит в допускающее состояние.

- Если состояние не допускающее и из данной конфигурации есть k переходов, то M ' использует вторую ленту для создания k копий, которые записываются в конце очереди на ленте 1.

- M ' изменяет k конфигураций в соответствии с программой машины M.

- M ' перемещает отметку текущей конфигурации на следующую справа и цикл повторяется с шага 1.

Допустим, что m есть максимальное число выборов машины M в любой конфигурации. Тогда существует одно начальное состояние M, не более m конфигураций, достижимых за 1 шаг, не более m² конфигураций, достижимых за 2 шага и т.д. Таким образом, после n переходов машина M может достичь не более 1+ m +m² +…+mⁿ nmⁿ конфигураций. Порядок, в котором машина M ' исследует конфигурации, называется “поиском в ширину”, т.е. M ' исследует все достижимые конфигурации машины M за 0 шагов, достижимые за 1 шаг и т.д.

Допускающая конфигурация машины M будет рассмотрена машиной M ' в числе первых nmⁿ конфигураций. Таким образом, если машина M допускает, то машина M ' также допускает, т.е. L(M) = L(M ' ).

Отметим, что работа построенной детерминированной машины M' может потребовать экспоненциально большего времени, чем время работы недетерминированной машины M, которую она моделирует. Разница между полиномиальным и экспоненциальным временем - это граница того, что можно решить с помощью компьютера, а что практически нерешаемо.

Теорема. Если M недетерминированная машина Тьюринга с емкостной сложностью S(n), то найдется детерминированная машина Тьюринга M' с емкостной сложностью O(S²(n)) и L(M' ) = L(M).

Доказательство. Пусть M недетерминированная машина Тьюринга (возможно k-ленточная) с емкостной сложностью S(n). Тогда число различных конфигураций, в которые машина M может попасть из начальной с входом длины n, не превосходит некоторого числа c^S(n), точнее Q(X+1)^{k S(n)} (S(n))^k, где k - число лент. Тогда число переходов от конфигурации C₁ к конфигурации C₂ (С₁+ С₂) на любой из лент не превосходит c^S(n) . Можно выяснить, существует ли переход С₁+ С₂ за 2i шагов, проверив для всех C₃ существует ли переход С₁+ С₃ и С ₃+ С₂ за i шагов. После каждого обращения к процедуре число i уменьшается вдвое.

Идея моделирования машиной M' работы машины M приведена в доказательстве предыдущей теоремы. Стратегия работы машины M' - установить приведет ли начальная конфигурация C₀ к какой-нибудь допускающей конфигурации C_f . Чтобы найти верхнюю емкостную границу для машины M', расположим конфигурации (длины O(S(n))) на стеках того же размера. В каждый момент времени число фрагментов стека не превосходит 1+ log c^S(n) , т.е. O(S(n)). Для всего стека машины M потребуется O(S² (n)) ячеек.

Теорема. Если язык L допускается k-ленточной недетерминированной машиной Тьюринга M = (X, Q, q₀, F, I) с временной сложностью T(n), то он допускается одноленточной недетерминированной машиной с временной сложностью O(T²(n)).

Доказательство. Пусть M₁ одноленточная недетерминированная машина Тьюринга, имеющая на ленте 2k дорожек, т.е. ленточные символы машины M₁ представляются 2k-членными кортежами, в которых на нечетных местах стоят символы алфавита X, а на четных - либо символ , либо маркер #. Дорожки с нечетными номерами соответствуют k лентам машины M, а каждая дорожка с четным номером 2j содержит символ во всех ячейках, кроме одной, где стоит маркер #, отмечающий положение головки машины M на ленте j, которой соответствует дорожка 2j-1. Машина M₁ моделирует один шаг работы машины M следующим образом. Допустим, что вначале головка машины M₁ обозревает клетку, содержащую самую левую головку машины M.

Головка машины M₁ движется вправо, пока не минует все k маркеров положений головок на дорожках с четными номерами. При этом M₁ запоминает в своем состоянии символы, обозреваемые каждой из головок машины M. Теперь M₁ делает недетерминированное развлетвление, исходя из состояния машины M, которое машина M₁ запомнила в своем состоянии, и обозреваемых машиной M на лентах символов, которые машина M₁ также нашла.

Выбрав для моделирования шаг машины M, машина M₁ изменяет в соответствии с ним состояние машины M, которое она помнит в своем состоянии. Затем M₁ сдвигает свою головку влево и проходит все маркеры, изменяя ленточный символ на дорожке над маркером и сдвигая маркер не более чем на одну клетку (L,R,S).

Машина M₁ промоделировала один шаг работы машины M. Действия машины M₁ на этом шаге детерминированы. Ее головка находится правее левого маркера не более чем на две ячейки. Начиная с этого маркера цикл можно повторить.

Если машина M допускает цепочку длины n, то совершает при этом не более T(n) переходов. Очевидно, что в последовательности из T(n) шагов головки мащины M могут разойтись не более чем на T(n) клеток, и, значит, M₁ может смоделировать один шаг этой последовательности не более чем за O(T(n)) своих шагов. Таким образом, M₁ допускает цепочку , выполняя не более чем O(T² (n)) переходов.

Следствие 1. Если язык допускается k-ленточной детерминированной машиной Тьюринга с временной сложностью T(n), то он допускается одноленточной детерминированной машиной Тьюринга с временной сложностью O(T²(n)).

Следствие 2. Если язык L допускается k-ленточной недетерминированной машиной Тьюринга с емкостной сложностью S(n), то он допускается одноленточной недетерминированной машиной Тьюринга с емкостной сложностью S(n).

Следствие 3. Если язык допускается k-ленточной детерминированной машиной Тьюринга с емкостной сложностью S(n), то он допускается одноленточной детерминированной машиной Тьюринга с емкостной сложностью S(n).

Имитация машины Тьюринга на компьютере и компьютера на машине Тьюринга

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

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

Процессор состоит из устройства управления (УУ) и арифметического устройство (АУ). Устройство управления содержит счетчик тактов, команд и т.д., вырабатывает управляющие сигналы для выполнения команд, передачи данных и т.д. Процессор содержит регистры операндов, линии связи и линии задержки для непосредственной реализации процессов вычислений.

Наряду с процессором и памятью компьютеру необходимы еще устройства ввода/вывода.

Имитация машины Тьюринга на компьютере. Пусть M - машина Тьюринга, одним из составляющих которой является ее конечное управление. Поскольку M имеет конечное число состояний и конечное число правил перехода, программа компьютера может закодировать состояния в виде цепочек символов, как и символы ее внешнего алфавита, и использовать таблицу переходов машины M для преобразования цепочек. Бесконечную ленту машины Тьюринга можно имитировать сменными дисками, размещаемыми в двух магазинах, соответственно для данных, расположенных слева и справа от считывающей головки на ленте. Чем дальше в магазине расположены данные, тем дальше они от головки на ленте.

Для имитации компьютера на машине Тьюринга существенны две вещи:

существуют ли инструкции, выполняемые компьютером, и недоступные для машины Тьюринга;

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

Неформальная модель реального компьютера:

- память, состоящая из последовательности слов и их адресов. В качестве адресов будут использоваться натуральные числа 0,1, …;

- программа компьютера, записанная в слова памяти, каждое из которых представляет простую инструкцию. Допускается “непрямая адресация” по указателям;

- каждая инструкция использует конечное число слов и изменяет значение не более одного слова;

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

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

Рис

Машина имеет несколько лент. Первая лента представляет всю память компьютера - адреса и значения (в двоичной системе). Адреса заканчиваются маркером *, значения - маркером #. Начало и конец записей 1-й ленты обозначаются маркером $. Вторая лента - “счетчик инструкций”, содержит одно двоичное целое, представляющее одну из позиций считываюшей головки на первой ленте, адрес инструкции, которая должна быть выполнена следующей. Третья лента содержит адрес и значение по нему после того, как этот адрес устанавливается на первой ленте. Для выполнения инструкции машина Тьюринга должна найти значение по одному или нескольким адресам памяти, где хранятся данные, участвующие в вычислении. Нужный адрес копируется на ленту 3 и сравнивается с адресами на ленте 1 до совпадения. Значение по этому адресу копируется на третью ленту и перемещается на нужное место, как правило, по одному из начальных адресов, представляющих регистры компьютера. Четвертая лента имитирует входной файл. Пятая лента - рабочая память, служит для выполнения вычислений. Допускающая инструкция машины Тьюринга соответствует выводу на печать в выходном файле.

Функционирование такой имитирующей машины:

1.Найдя на 1-й ленте адрес, совпадающий с номером инструкции на 2-й ленте, исследуем значение по нему и копируем на 3-ю ленту. Первые биты инструкции задают действие (копировать, вставить, ветвиться и т.д.), оставщиеся биты - адрес или адреса, используемые в этом действии.

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

3. Далее инструкция выполняется. С новым значением можно сделать следующее:

скопировать по другому адресу;

Второй адрес извлекается из инструкции, помещается на 3-ю ленту, находится на 1-й ленте и значение по нему копируется в зарезервированное для него пространство. Если для нового значения надо больше (меньше) памяти, чем для старого, пространство изменяется путем сдвига, а именно,

на рабочую ленту копируется часть ленты справа от того места, куда надо поместить новое значение;

новое значение записывается на 1-ю ленту;

рабочая часть копируется обратно на 1-ю ленту справа от нового значения.

прибавить найденное значение по другому адресу;

Ищем второй адрес на первой ленте, выполняем сложение значения по этому адресу и записанному на 3-й ленте.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

§6. Языки L_e и L_ne

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

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

[1], глава 9.

Рекурсивные языки. Неразрешимая РП - проблема

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

1) если L, то M допускает вход , следовательно, останавливается;

2) если L, то M в конце концов остановится, не допуская.

Если мы рассматриваем язык L как проблему, то проблема называется разрешимой, если язык L рекурсивный. В противном случае проблема называется неразрешимой.

Можно ввести разделение языков и проблем на следующие три класса:

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

Рекурсивно перечислимые (РП), не являющиеся рекурсивными.

Неперечислимые (не - РП) языки.

Теорема. Если L - рекурсивный язык, то язык L , дополнение языка L , также рекурсивный.

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

Теорема (Поста). Если язык L и его дополнение рекурсивно перечислимы, то L рекурсивен.

Доказательство. Пусть L=L(M₁) и L =L(M₂). Возьмем машину Тьюринга M с двумя лентами, имитирующими соответственно машины M₁ и M₂.

Пусть вход L, тогда M₁ допускает , а машина M допускает и останавливается; в противном случае машина M останавливается, не допуская. Таким образом, машина M останавливается на любом входе и L= L(M), т.е. L рекурсивный язык.

Следствие. Из девяти способов соотношений языков L и L' возможны следующие четыре:

1. Оба языка L и L' рекурсивны.

2. Ни L, ни L' не являются рекурсивно перечислимыми.

L является рекурсивно перечислимым, а L' не рекурсивно перечислим.

L' является рекурсивно перечислимым, а L не рекурсивно перечислим.

Универсальный язык L_u определяется как множество цепочек в алфавите {0,1}, являющихся кодами упорядоченных пар (M, ), где M - машина Тьюринга с входным алфавитом {0,1} и - цепочка из {0,1}*, принадлежащая L(M). Код упорядоченной пары (M,) представляется кодом машины M, отделенным 111 от кода цепочки . Другими словами, язык L_u - это множество цепочек, кодов упорядоченных пар (M,), представляющих машину Тьюринга и допускаемый ею вход. Покажем, что существует машина Тьюринга U, называемая универсальной машиной, для которой L_u = L(U).

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

Пусть на 1-й ленте машины U хранятся переходы машины M вместе с входом ; на 2-й ленте - двоичный код машины M; на 3-й - состояние машины M; 4-ая - рабочая лента.

Машина U производит следующие операции:

1. Исследует вход, и если код M правильный, записывает на 2-ю ленту код входной цепочки . Для неправильных кодов M машина U не допускает никакого входа.

На 2-й ленте все клетки, кроме занятых кодом входа , заполняются символом , представляемым как 1000.

На 3-й ленте записывается 0, т.е. начальное состояние q₀ машины M, и считывающая головка обозревает первый символ кода .

Чтобы отобразить переход машины M, машина U отыскивает его на первой ленте, например, 0ⁱ 10^j 10^k 10^l 10^m (m=1,2,3 - кодирует R,L,S),

и выполняет следующие действия:

изменяет содержимое 3-ей ленты на 0^k;

заменяет 0^j на второй ленте на 0^l ;

перемещает головку на 2-й ленте согласно 0^m .

Если M не имеет перехода, то M останавливается, и U останавливается.

Если M попадает в допускающее состояние, то U допускает.

Таким образом, U допускает вход (M,) тогда и только тогда, когда M допускает .

Неразрешимость универсального языка. Проблема останова

Существуют рекурсивно перечислимые, но не рекурсивные языки, один из таких языков L_u . Сведением L_u к проблеме P можно доказать, что P не имеет алгоритма.

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

Доказательство. Была доказана рекурсивная перечислимость языка L_u. Допустим, что L_u рекурсивен, тогда по теореме язык L_u рекурсивен и существует допускающая его машина M, т.е. L_u = L(M). Преобразуем M в машину M ', допускающую L_u : если вход есть _i , т.е. код машины M_i , то M ' определяет, допускает ли M_i вход _i . Поскольку M допускает L_u, то M допускает _i , если M_i не допускает _i , т.е. когда _i L_d.

Таким образом, M ' допускает тогда и только тогда, когда L_d.

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

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

В математической логике рассматриваются разные типы сведений, образующие целую ветвь математической логики, теорию степеней неразрешимости. В общем виде, проблема P₁ сводима к проблеме P₂ (P₁ < _f P₂), если существует вычислимая функция f такая, что

xP₁ f(x)P₂ (xP₁ f(x)P₂).

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

Теорема. Если P₁ < _f P₂ , то

если P₁ не является рекурсивной, то P₂ также не рекурсивна (не-Р);

если P₁ не является рекурсивно перечислимой, то P₂ не рекурсивно перечислима (не-РП).

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

На входе P₁ , так как P₁ < _f P₂ , то f()P₂. Так как P₂ рекурсивно, существует алгоритм A:

A(x)=0, если x P₂, где x = f(), тогда и только тогда, когда P₁;

A(x)=1, если x P₂, где x = f(), тогда и только тогда, когда P₁.

Откуда следует, что P₁ рекурсивно, по противоречию P₂ - не рекурсивно.

Пусть P₁ не-РП, а P₂ - рекурсивно перечислимо. Тогда P₂ имеет допускающую ее машину M₂. Если на входе x P₂ машина M₂ допускает, тогда P₁ , где x=f(); в противном случае машина M₂ работает бесконечно, следовательно, и P₁ . Таким образом, машина, языком котором является P₁, допускает или не допускает свой вход одновременно с машиной M₂ , и, следовательно, допускает язык P₁, что противоречит условию.

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

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

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

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

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

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

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

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

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

если (M_i, ) L_u , т.е. машина M_i допускает на входе , то машина

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

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

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

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

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

Машина M ' строится по конкретной паре (M,), имеюшей длину n, тогда q₀ ,…,q_n состояния M ' (где q₀ - начальное состояние).

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

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

Когда M ' достигает пробела с состоянии q_n , она, используя похожий набор состояний, перемещает головку в левый конец ленты.

Используя дополнительные состояния M ' моделирует универсальную машину U.

Если U допускает, то M ' допускает. Если U никогда не допускает, то M ' никогда не допускает.

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

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

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

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

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

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

Пусть - свойство РП-языков, а L - множество кодов машин M_i таких, что L(M_i) .

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

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

a) Допустим, что , тогда существует непустой язык L, пусть xL. Построим алгоритм, сводящий L_u к L . По паре (M,) строится машина M ' такая, что (M,) L_u M ' L:

Если (M,) L_u, т.е. M не допускает вход , тогда M ' прекращает работу, не допуская свой вход x. L(M' ) = , следовательно,

L(M ' ) , а M' L. Если (M,) L_u, то L(M' ) = L и M' L.

Схема такого алгоритма приведена на рис.

Машина M' имеет две ленты: на первой записан код машины M и входа , на второй - код машины M_L , допускающей язык L.

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