dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 85
Текст из файла (страница 85)
Во второй класс войдут проблемы, разрешимые лишь с помощью таких машинТьюринга, которые с недопустимыми входами могут работать бесконечно. В последнемслучае проверить допустимость входа весьма проблематично, поскольку независимо оттого, сколь долго работает МТ, неизвестно, допускается вход или нет. Поэтому мы сосредоточимся на методах доказательства “неразрешимости” проблем, т.е. что для них несуществует алгоритма решения независимо от того, допускаются ли они машиной Тьюринга, которая не останавливается на некоторых входах, или нет.Будет доказано, что неразрешима следующая проблема.• Допускает ли данная машина Тьюринга данный вход?Затем из неразрешимости этой проблемы будет выведена неразрешимость ряда других проблем.
Например, будет показано, что все нетривиальные задачи, связанные с языком машины Тьюринга, неразрешимы, как и многие проблемы, в которых речь вообщене идет о машинах Тьюринга, программах или компьютерах.Стр. 3779.1. Íåïåðå÷èñëèìûé ÿçûêНапомним, что язык L является рекурсивно-перечислимым (РП-языком), если L = L(M)для некоторой МТ M. В разделе 9.2 будут введены так называемые “рекурсивные”, или“разрешимые”, языки, которые не только рекурсивно перечислимы, но и допускаются некоторой МТ, останавливающейся на всех своих входах независимо от их допустимости.Наша дальняя цель — доказать неразрешимость языка, состоящего из пар (M, w), которые удовлетворяют следующим условиям.1.M — машина Тьюринга (в виде соответствующего двоичного кода) с входным алфавитом {0, 1}.2.w — цепочка из символов 0 и 1.3.M допускает вход w.Если эта проблема неразрешима при условии, что алфавит — двоичный, то она, безусловно, будет неразрешимой и в более общем виде, при произвольном входном алфавите.Прежде всего, необходимо сформулировать эту проблему как вопрос о принадлежности некоторому конкретному языку.
Поэтому нужно определить такое кодирование машин Тьюринга, в котором использовались бы только символы 0 и 1 независимо от числасостояний МТ. Имея такие коды, можно рассматривать любую двоичную цепочку какмашину Тьюринга. Если цепочка не является правильным представлением какой-либоМТ, то ее можно считать представлением МТ без переходов.Для достижения промежуточной цели, представленной в данном разделе, используется “язык диагонализации” Ld.
Он состоит из всех цепочек w, каждая из которых не допускается машиной Тьюринга, представленной этой цепочкой. Мы покажем, что такоймашины Тьюринга, которая бы допускала Ld, вообще не существует. Напомним: доказать, что язык не допускается никакой машиной Тьюринга, значит доказать нечто большее, чем то, что данный язык неразрешим (т.е. что для него не существует алгоритма,или МТ, которая останавливается на всех своих входах).Роль языка Ld аналогична роли гипотетической программы H2 из раздела 8.1.2, котораяпечатает hello, world, если ей на вход подается программа, не печатающая hello,world при чтении собственного кода. Точнее, как не существует H2, так и Ld не может бытьдопущен никакой машиной Тьюринга. Реакция первой на саму себя как на вход приводит кпротиворечию. Аналогично, если бы Ld допускался некоторой машиной Тьюринга, то онапротиворечила бы самой себе при обработке своего собственного кода.9.1.1.
Ïåðå÷èñëåíèå äâîè÷íûõ öåïî÷åêВ дальнейшем нам понадобится приписать всем двоичным цепочкам целые числа так,чтобы каждой цепочке соответствовало одно целое число и каждому числу — одна цепочка. Если w — двоичная цепочка, то 1w рассматривается как двоичное представлениецелого числа i.
Тогда w называется i-й цепочкой. Таким образом, ε есть первая цепочка,378Стр. 378ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜ0 — вторая, 1 — третья, 00 — четвертая, 01 — пятая, и так далее. Это равносильно тому,что цепочки упорядочены по длине, а цепочки равной длины упорядочены лексикографически. В дальнейшем i-я цепочка обозначается через wi.9.1.2.
Êîäû ìàøèí ÒüþðèíãàНаша следующая цель — разработать для машин Тьюринга такой код, чтобы всякуюМТ с входным алфавитом {0, 1} можно было рассматривать как двоичную цепочку. Мытолько что показали, как перечислить двоичные цепочки. Поэтому у нас есть идентификация машин Тьюринга целыми числами, и можно говорить об “i-ой машине Тьюринга Mi”.Для того чтобы представить МТ M = (Q, {0, 1}, Γ, δ, q1, B, F) как двоичную цепочку,нужно приписать целые числа состояниям, ленточным символам и направлениям L и R.• Будем предполагать, что состояниями являются q1, q2, …, qr при некотором r.
Состояние q1 всегда будет начальным, а q2 — единственным допускающим. Заметим, что поскольку можно считать, что МТ останавливается, попадая в допускающее состояние, то одного такого состояния всегда достаточно.• Предположим, что ленточными символами являются X1, X2, …, Xs при некотором s.X всегда будет символом 0, X2 — 1, а X3 — B, пробелом (пустым символом). Остальным же ленточным символам целые числа могут быть приписаны произвольным образом.• Направление L обозначается как D1, а направление R — как D2.Поскольку состояниям и ленточным символам любой МТ M можно приписать целыечисла не единственным образом, то и кодировок МТ будет, как правило, более одной. Нов дальнейшем это не будет играть роли, так как мы покажем, что МТ M с L(M) = Ld вообще непредставима никаким кодом.Установив, какие целые числа соответствуют каждому из состояний, символов и направлений, можно записать код функции переходов δ.
Пусть δ(qi, Xj) = (qk, Xl, Dm) естьодно из правил перехода, где i, j, k, l, m — некоторые целые числа. Это правило кодируется цепочкой 0i10j10k10l10m. Заметим, что каждое из чисел i, j, k, l, m не меньше единицы, так что в коде каждого отдельного перехода нет двух 1 подряд.Код МТ M состоит из кодов всех ее переходов, расположенных в некотором порядкеи разделенных парами единиц:C111C211 … Cn–111Cn,где каждое C означает код одного перехода M.Пример 9.1. Рассмотрим МТM = ({q1, q2, q3}, {0, 1}, {0, 1, B}, δ, q1, B, {q2}),где функция δ состоит из следующих правил.9.1. ÍÅÏÅÐÅ×ÈÑËÈÌÛÉ ßÇÛÊСтр.
379379δ(q1, 1) = (q3, 0, R)δ(q3, 0) = (q1, 1, R)δ(q3, 1) = (q2, 0, R)δ(q3, B) = (q3, 1, L)Переходы кодируются соответственно следующим образом.01001000101000001010100100000100100101000001000100010010Первое правило, например, можно записать как δ(q1, X2) = (q3, X1, D2), поскольку 1 = X2,0 = X1 и R = D2. Поэтому его кодом будет цепочка 01102103101102, как и записано выше.Кодом всей M является следующая цепочка.01001000101001100010101001001100010010010100110001000100010010Заметим, что существуют другие возможные коды машины M. В частности, коды четырех ее переходов можно переставить 4! способами, что дает 24 кода для M. В разделе 9.2.3 нам понадобится кодировать пары вида (M, w), состоящие из МТ ицепочки.
В качестве такого кода последовательно записываются код M, 111 и цепочка w.Поскольку правильный код МТ не может содержать три единицы подряд, первое вхождение 111 гарантированно отделяет код M от w. Например, если M — это МТ изпримера 9.1, а w — цепочка 1011, то кодом (M, w) будет цепочка, представленная в конце примера 9.1, с дописанной к ней последовательностью 1111011.9.1.3. ßçûê äèàãîíàëèçàöèèВ разделе 9.1.2 были определены коды машин Тьюринга, и теперь у нас есть вполне конкретное понятие Mi, “i-й машины Тьюринга”. Это МТ M, кодом которой является i-я двоичнаяцепочка wi. Многие целые числа вообще не соответствуют машинам Тьюринга.
Например,11001 не начинается с 0, а цепочка 0010111010010100 содержит три 1 подряд. Если wi не является правильным кодом МТ, то будем считать, что Mi — МТ, у которой одно состояние инет переходов, т.е. Mi для этих значений i есть МТ, которая сразу останавливается на любомвходе. Итак, если wi не является правильным кодом МТ, то L(Mi) есть ∅.Теперь можно дать весьма существенное определение.• Язык диагонализации Ld — это множество всех цепочек wi, не принадлежащих L(Mi).Таким образом, Ld состоит из всех цепочек w, каждая из которых не допускается соответствующей машиной Тьюринга с кодом w.Из рис.
9.1 видно, почему Ld называется языком “диагонализации”. Для всех i и j этатаблица показывает, допускает ли МТ Mi входную цепочку wj; 1 означает “да, допуска-380Стр. 380ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜет”, а 0 — “нет, не допускает”1. Можно считать i-ю строку таблицы характеристическимвектором языка L(Mi); единицы в этой строке указывают на цепочки, которые принадлежат данному языку.ДиагональРис. 9.1. Таблица, представляющая допустимость цепочек машинами ТьюрингаЧисла на диагонали показывают, допускает ли Mi цепочку wi.
Чтобы построить языкLd, нужно взять дополнение диагонали. Например, если бы таблица на рис. 9.1 была корректной, то дополнение диагонали имело бы начало 1, 0, 0, 0, …. Таким образом, Ld должен был бы содержать w1 = ε и не содержать цепочки с w2 по w4, т.е. 0, 1 и 00 и т.д.Операция с дополнением диагонали для построения характеристического вектораязыка, которому не может соответствовать никакая строка, называется диагонализацией.Она приводит к желаемому результату, поскольку дополнение диагонали само по себеявляется характеристическим вектором, описывающим принадлежность некоторомуязыку, а именно — Ld. Действительно, этот характеристический вектор отличается откаждой из строк таблицы на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
