ГЛАВА 9

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

Эта глава начинается повторением рассуждений из раздела 8.1, которые неформально обосновывали существование проблем, не разрешимых с помощью компьютера. Недос­татком тех «правдоподобных рассуждений» было вынужденное пренебрежение реаль­ными ограничениями, возникающими при реализации языка С (или другого языка про­граммирования) на любом реальном компьютере. Однако эти ограничения, вроде конеч­ности адресного пространства, не являются фундаментальными. Наоборот, с течением времени мы вправе ожидать от компьютеров неограниченного роста таких количествен­ных характеристик, как размеры адресного пространства, оперативной памяти и т.п.

Сосредоточившись на машинах Тьюринга, для которых ограничения такого рода от­сутствуют, можно лучше понять главное — принципиальные возможности вычислитель­ных устройств, если не сегодня, то в перспективе. В этой главе дается формальное дока­зательство того, что никакая машина Тьюринга не может решить следующую задачу.

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

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

Далее мы разделим проблемы, разрешимые с помощью машин Тьюринга, на два класса. В первый класс войдут те из них, которые имеют алгоритм решения (т.е. машину Тьюринга, которая останавливается независимо от того, допускает она свой вход или нет). Во второй класс войдут проблемы, разрешимые лишь с помощью таких машин Тьюринга, которые с недопустимыми входами могут работать бесконечно. В последнем случае проверить допустимость входа весьма проблематично, поскольку независимо от того, сколь долго работает МТ, неизвестно, допускается вход или нет. Поэтому мы со­средоточимся на методах доказательства «неразрешимости» проблем, т.е. что для них не существует алгоритма решения независимо от того, допускаются ли они машиной Тью­ринга, которая не останавливается на некоторых входах, или нет.

Будет доказано, что неразрешима следующая проблема.

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

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

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

Напомним, что язык L является рекурсивно-перечислимым (РП-языком), если L = L(M) для некоторой МТ М. В разделе 9.2 будут введены так называемые «рекурсивные», или «разрешимые», языки, которые не только рекурсивно перечислимы, но и допускаются не­которой МТ, останавливающейся на всех своих входах независимо от их допустимости.

Наша дальняя цель — доказать неразрешимость языка, состоящего из пар (М, w), ко­торые удовлетворяют следующим условиям.

М— машина Тьюринга (в виде соответствующего двоичного кода) с входным алфа­витом {0, 1}.

w — цепочка из символов 0 и 1.

М допускает вход w.

Если эта проблема неразрешима при условии, что алфавит — двоичный, то она, безус­ловно, будет неразрешимой и в более общем виде, при произвольном входном алфавите.

Прежде всего, необходимо сформулировать эту проблему как вопрос о принадлежно­сти некоторому конкретному языку. Поэтому нужно определить такое кодирование ма­шин Тьюринга, в котором использовались бы только символы 0 и 1 независимо от числа состояний МТ. Имея такие коды, можно рассматривать любую двоичную цепочку как машину Тьюринга. Если цепочка не является правильным представлением какой-либо МТ, то ее можно считать представлением МТ без переходов.

Для достижения промежуточной цели, представленной в данном разделе, использует­ся «язык диагонализации» L_d. Он состоит из всех цепочек w, каждая из которых не до­пускается машиной Тьюринга, представленной этой цепочкой. Мы покажем, что такой машины Тьюринга, которая бы допускала L_d, вообще не существует. Напомним: дока­зать, что язык не допускается никакой машиной Тьюринга, значит доказать нечто боль­шее, чем то, что данный язык неразрешим (т.е. что для него не существует алгоритма, или МТ, которая останавливается на всех своих входах).

Роль языка аналогична роли гипотетической программы Н₂ из раздела 8.1.2, ко­торая печатает hello, world, если ей на вход подается программа, не печатающая hello, world при чтении собственного кода. Точнее, как не существует Н₂, так и L_d не может быть допущен никакой машиной Тьюринга. Реакция первой на саму себя как на вход приводит к противоречию. Аналогично, если бы L_d допускался некоторой ма­шиной Тьюринга, то она противоречила бы самой себе при обработке своего собст­венного кода.

9.1.1. Перечисление двоичных цепочек

В дальнейшем нам понадобится приписать всем двоичным цепочкам целые числа так, чтобы каждой цепочке соответствовало одно целое число и каждому числу — одна це­почка. Если w — двоичная цепочка, то 1 w рассматривается как двоичное представление целого числа i. Тогда vv называется i-й цепочкой. Таким образом, е есть первая цепочка, О — вторая, 1 — третья, 00 — четвертая, 01 — пятая, и так далее. Это равносильно тому, что цепочки упорядочены по длине, а цепочки равной длины упорядочены лексикогра­фически. В дальнейшем z’-я цепочка обозначается через w-_v

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

Наша следующая цель — разработать для машин Тьюринга такой код, чтобы всякую МТ с входным алфавитом {0, 1} можно было рассматривать как двоичную цепочку. Мы только что показали, как перечислить двоичные цепочки. Поэтому у нас есть идентифика­ция машин Тьюринга целыми числами, и можно говорить об «г-ой машине Тьюринга М». Для того чтобы представить МТ М= (Q, {0, 1}, Г, 5, q,, В, F) как двоичную цепочку, нужно приписать целые числа состояниям, ленточным символам и направлениям L и R.

Будем предполагать, что состояниями являются q_h q₂, …, q_r при некотором г. Со­стояние q 1 всегда будет начальным, a q₂ — единственным допускающим. Заме­тим, что поскольку можно считать, что МТ останавливается, попадая в допус­кающее состояние, то одного такого состояния всегда достаточно.

Предположим, что ленточными символами являются Х\, Х₂, …. Л’^ при некотором s. Ху всегда будет символом 0, Х₂ — 1, аХ₃ — В, пробелом (пустым символом). Остальным же ленточным символам целые числа могут быть приписаны произ­вольным образом.

Направление L обозначается как £)₍, а направление R — как D₂.

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

Установив, какие целые числа соответствуют каждому из состояний, символов и на­правлений, можно записать код функции переходов 8. Пусть <5(<7;, Xj) = (q_k, X_h D_m) есть одно из правил перехода, где i,j, к, I, т — некоторые целые числа. Это правило кодиру­ется цепочкой 0’10’10^k10’l0^m. Заметим, что каждое из чисел i,j, к, I, т не меньше едини­цы, так что в коде каждого отдельного перехода нет двух 1 подряд.

Код МТ М состоит из кодов всех ее переходов, расположенных в некотором порядке и разделенных парами единиц:

С,11С₂11 … С_п ,11С_П, где каждое С означает код одного перехода М.

Пример 9.1. Рассмотрим МТ

M=({q_hq₂,q₃}, {0, 1}, {0, 1 ,B},S,q_uB, {q₂}), где функция 8 состоит из следующих правил.

<5(<7ь 1 ) = (<7з, О, Л)

= (</,, 1,Л)

= (<72, 0, Л)

<5(<7з, 5) = (<7З, 1,1) Переходы кодируются соответственно следующим образом.

0100100010100 0001010100100 00010010010100 0001000100010010

Первое правило, например, можно записать как 8(q_u Х₂) = Х_и D₂), поскольку 1 = Х₂, 0 ~ Х\ kR = D₂. Поэтому его кодом будет цепочка 0¹10²10³10¹10², как и записано выше. Кодом всей М является следующая цепочка.

01001000101001100010101001001100010010010100110001000100010010 Заметим, что существуют другие возможные коды машины М. В частности, коды четы­рех ее переходов можно переставить 4! способами, что дает 24 кода для М. □

В разделе 9.2.3 нам понадобится кодировать пары вида (М, vr), состоящие из МТ и цепочки. В качестве такого кода последовательно записываются код М, 111 и цепочка w. Поскольку правильный код МТ не может содержать три единицы подряд, первое вхож­дение 111 гарантированно отделяет код М от w. Например, если М— это МТ из примера 9.1, a w— цепочка 1011, то кодом (М, w) будет цепочка, представленная в кон­це примера 9.1, с дописанной к ней последовательностью 1111011.

9.1.3. Язык диагонализации

В разделе 9.1.2 были определены коды машин Тьюринга, и теперь у нас есть впол­не конкретное понятие М;, ‘7-й машины Тьюринга». Это МТ М, кодом которой являет­ся 1-я двоичная цепочка w_v Многие целые числа вообще не соответствуют машинам Тьюринга. Например, 11001 не начинается с 0, а цепочка 0010111010010100 содержит три 1 подряд. Если Wj не является правильным кодом МТ, то будем считать, что М, — МТ, у которой одно состояние и нет переходов, т.е. М, для этих значений / есть МТ, которая сразу останавливается на любом входе. Итак, если Wi не является правильным кодом МТ, то ЦМ) есть 0.

Теперь можно дать весьма существенное определение.

• Язык диагонализации L& — это множество всех цепочек Wi, не принадлежа­щих L(Mi).

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

Из рис. 9.1 видно, почему L_d называется языком «диагонализации». Для всех i и j эта таблица показывает, допускает ли МТ Mj входную цепочку wj; 1 означает «да, допуска­ет», а 0 — «нет, не допускает»^[1]. Можно считать ю строку таблицы характеристическим вектором языка L(M); единицы в этой строке указывают на цепочки, которые принад­лежат данному языку.

j ——

Числа на диагонали показывают, допускает ли М\ цепочку Чтобы построить язык нужно взять дополнение диагонали. Например, если бы таблица на рис. 9.1 была кор­ректной, то дополнение диагонали имело бы начало 1, 0, 0, 0, …. Таким образом, L_d дол­жен был бы содержать w\ = е и не содержать цепочки с vv₂ по vv₄, т.е. О, 1 и 00 и т.д.

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

9.1.4. Доказательство неперечислиллосги L_d

Развивая наши рассуждения о характеристических векторах и диагонали, формаль­но докажем основной результат, касающийся машин Тьюринга, — МТ, допускающей язык Li, не существует.

Теорема 9.2. Язык L_d не является рекурсивно-перечислимым, т.е. не существует ма­шины Тьюринга, которая допускала бы L_d.

Доказательство. Допустим, что L_d = L(M) для некоторой МТ М. Так как L_d — язык над алфавитом {0, 1}, М должна содержаться в построенной нами последовательности машин Тьюринга, поскольку эта последовательность содержит все МТ с входным ал­фавитом {0, 1}. Следовательно, в ней есть, по крайней мере, один код машины М, скажем,т.е. М— М\.

Выясним теперь, принадлежит ли Wj языку L_d.

Если м>\ принадлежит Ц, то М, допускает vv,. Но тогда (по определению L_d) w-, не при­надлежит L_d, так как L_d содержит лишь такие Wj, для которых Щ не допускает Wj.

Точно так же, если w; не принадлежит L&, то М\ не допускает vv,. Но тогда (по оп­ределению L_d) W{ принадлежит L_A.

Поскольку Wi не может одновременно и принадлежать, и не принадлежать L_d, приходим к противоречию с нашим предположением о том, что М существует. Таким образом, Ц не является рекурсивно-перечислимым языком. □

9.1.5. Упражнения к разделу 9.1

• Запишите следующие цепочки:

а)   (*)w₃₇;

б)   w₁₀₀.

• Запишите один из возможных кодов машины Тьюринга, изображенной на рис. 8.9.
• (!) Ниже приводятся определения двух языков, похожих на L_d, но все же отлич­ных от него. Используя операции типа диагонализации, покажите, что каждый из них не может допускаться никакой машиной Тьюринга. Отметим, что при этом нужно использовать не диагональ, а какую-то другую бесконечную после­довательность элементов матрицы, изображенной на рис. 9.1:

а)   (*) множество всех w„ для которых М₂\ не допускает м>\,

б)   множество всех для которых Л/, не допускает vv_2l.

• (!) Машины Тьюринга, рассмотренные до сих пор, имели входной алфавит {О, 1}. Допустим, мы хотели бы приписать целые числа всем машинам Тьюрин­га, независимо от их входного алфавита. Это, вообще говоря, невозможно. Ведь в то время, как имена состояний или рабочие символы на ленте (которые не яв­ляются входными), произвольны, каждый входной символ имеет значение. На­пример, языки (0^ПГ | п > 1} и {aⁿbⁿ | п > 1} похожи, однако не совпадают и до­пускаются разными МТ. Допустим тем не менее, что у нас есть бесконечное множество символов {а_ь а₂, …}, из которого выбираются все алфавиты МТ. Покажите, как можно приписать целые числа всем МТ, входной алфавит кото­рых является конечным подмножеством этих символов.

9.2. Неразрешимая РП-пробдема

Итак, мы убедились, что существует проблема (язык диагонализации L_d), которая не до­пускается никакой машиной Тьюринга. Наша следующая цель — уточнить структуру ре­курсивно-перечислимых языков (РП-языков), т.е. допустимых машинами Тьюринга, разбив их на два класса. В первый класс войдут языки, которым соответствует то, что обычно по­нимается как алгоритм, т.е. МТ, которая не только распознает язык, но и сообщает, что входная цепочка не принадлежит этому языку. Такая машина Тьюринга в конце концов всегда останавливается независимо от того, достигнуто ли допускающее состояние.

Второй класс языков состоит из тех РП-языков, которые не допускаются никакой машиной Тьюринга, останавливающейся на всех входах. Эти языки допускаются не­сколько неудобным образом: если входная цепочка принадлежит языку, то мы в конце концов об этом узнаем, но если нет, то машина Тьюринга будет работать вечно. Поэтому никогда нельзя быть уверенным, что данная входная цепочка не будет когда-нибудь до­пущена. Примером языка данного типа, как будет показано ниже, является множество таких закодированных пар (М, vv), в которых МТ М допускает вход vv.

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

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

1. Если w принадлежит L, то М попадает в допускающее состояние (и, следовательно, останавливается).
2. Если w не принадлежит L, то М в конце концов останавливается, хотя и не попадает в допускающее состояние.

МТ этого типа соответствует интуитивному понятию «алгоритма» — правильно опреде­ленной последовательности шагов, которая всегда заканчивается и приводит к некото­рому ответу. Если мы рассматриваем язык L как «проблему», то проблема L называется разрешимой, если она является рекурсивным языком. В противном случае проблема на­зывается неразрешимой.

Существование алгоритма зачастую важнее, чем наличие некоторой МТ, решающей данную проблему. Как упоминалось ранее, машины Тьюринга, которые могут не оста­навливаться, не дают информации, необходимой для утверждения, что цепочка не при­надлежит языку, т.е. они «не решают проблему». Таким образом, разделение проблем и языков на разрешимые (для них существует алгоритм решения) и неразрешимые часто важнее, чем разделение на рекурсивно перечислимые (для них существует МТ какого- либо типа) и неперечислимые (для них вообще не существует МТ). На рис. 9.2 представ­лено соотношение трех классов языков.

• Рекурсивные языки.
• Языки, которые рекурсивно перечислимы (РП), но не рекурсивны.
• Неперечислимые (не-РП) языки.

На рисунке указаны правильные положения не РП-языка L_d и «универсального языка» L_u, который, как мы вскоре докажем, является РП, но не рекурсивным.

Не-РП

Рис. 9.2. Соотношение рекурсивных, неперечислимых и РП-языков

Почему «рекурсивные»?

Современные программисты знакомы с понятием рекурсивной функции. Остается непонятным, что общего между рекурсивными функциями и машинами Тьюринга, которые всегда останавливаются. Еще хуже, что нерекурсивными, или неразреши­мыми, называются языки, которые не распознаются никаким алгоритмом, хотя под «нерекурсивными» мы привыкли понимать вычисления настолько простые, что они не требуют обращений к рекурсивным функциям.

Термин «рекурсивный» как синоним слова «разрешимый» возник в период развития математики, предшествовавший появлению компьютеров. В качестве понятия вычис­ления обычно использовались формализмы, основанные на рекурсии (но не итерации или цикле). В этих системах понятий (не рассматриваемых здесь) было нечто от вы­числений в таких языках функционального программирования, как LISP или ML. В этом смысле выражение «проблема рекурсивна» означало, что она «проста настолько, что можно записать рекурсивную функцию, которая всегда приводит к ее решению за конечное число шагов». И в наши дни применительно к машинам Тьюринга этот тер­мин имеет в точности тот же смысл.

Термин «рекурсивно-перечислимый» — из того же семейства понятий. С помощью некоторой функции элементы языка можно выписать в некотором порядке, т.е. «перечислить» их. Языки, элементы которых можно перечислить в некотором поряд­ке, — это именно те языки, которые допускаются некоторой МТ (возможно, рабо­тающей бесконечно на недопустимых входах).

9.2.2. Дополнения рекурсивных и РП-языков

Для доказательства того, что некоторый язык принадлежит второму кольцу на рис. 9.2 (т.е. является РП, но не рекурсивным), часто используется дополнение этого языка. Покажем, что рекурсивные языки замкнуты относительно дополнения. Поэтому, если язык L является РП, а его дополнение L — нет, то L не может быть рекурсивным. Если бы L был рекурсивным, то L также был бы рекурсивным, а следовательно, и РП. Докажем это важное свойство замкнутости рекурсивных языков.

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

• Допускающие состояния М становятся не допускающими состояниями М, не имеющими переходов, т.е. в этих состояниях М останавливается, не допуская.
• М имеет новое допускающее состояние г, из которого нет переходов.
• Для каждой комбинации из недопускающего состояния и ленточного символа М, в которой М не имеет перехода (т.е. останавливается, не допуская), добавляется пере­ход в допускающее состояние г.

Рис. 9.3. Строение МТ, допускающей дополнение рекурсивного языка

W

Поскольку М всегда останавливается, то всегда останавливается и М . Кроме того, М допускает множество именно тех цепочек, которые не допускаются М, т.е. L . □

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

Теорема 9.4. Если язык L и его дополнение являются РП, то L рекурсивен. Отметим, что тогда по теореме 9.3 язык L также рекурсивен.

Доказательство. Доказательство представлено на рис. 9.4. Пусть L = L (М\) и L = L(M₂). Параллельная работа машин имитируется МТ М. Чтобы эта модель стала простой и очевидной, можно взять МТ с двумя лентами и затем преобразовать ее в одно- ленточную. Одна из них имитирует ленту М\, а вторая — ленту М₂. Состояния М\ и М₂ являются компонентами состояния М.

Если вход w машины М принадлежит L, то А/, в конце концов попадает в допус­кающее состояние; тогда М допускает и останавливается. Когда же в допускающее со­
стояние попадает М₂, М останавливается, не допуская. Таким образом, М останавлива­ется при любом входе, и L(M) — это в точности L. Отсюда заключаем, что язык L — рекурсивный. □

Рис. 9.4. Моделирование двух МТ, одна из которых допускает некоторый язык, а вторая — его дополнение

Теоремы 9.3 и 9.4 можно объединить следующим образом. Из девяти способов рас­положения языка L и его дополнения L (см. диаграмму на рис. 9.2) возможны лишь сле­дующие четыре^[2].

• Оба языка/, и L рекурсивны, т.е. оба они находятся во внутреннем кольце.
• Ни L, ни L не являются РП, т.е. оба они находятся во внешнем кольце.
• L является РП, но не рекурсивным, и I не является РП, т.е. один находится в сред­нем кольце, а другой — во внешнем.
• L является РП, но не рекурсивным, и L не является РП, т.е. L и L меняются места­ми по отношению к случаю 3.

В качестве доказательства отметим, что теорема 9.3 исключает возможность того, что один из языков (L или L ) является рекурсивным, а второй принадлежит какому-либо из оставшихся классов. При этом теорема 9.4 исключает возможность того, что оба языка являются РП, но не рекурсивными.

Пример 9.5. Рассмотрим язык L_d, который, как мы знаем, не является РП. Поэтому язык I d не может быть рекурсивным. Однако L _d может быть либо не-РП, либо РП, но не рекурсивным. На самом деле верно последнее.

L а есть множество цепочек w_b допускаемых соответствующими М_;. Этот язык по­хож на универсальный язык L_u, состоящий из всех пар (М, w), где М допускает w, ко­торый, как мы покажем в разделе 9.2.3, является РП. Точно так же можно показать, что L d является РП. □

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

В разделе 8.6.2 уже неформально обсуждалось, как можно использовать машину Тьюринга в качестве модели компьютера с загруженной в него произвольной програм­мой. Иными словами, отдельно взятая МТ может использоваться как «компьютер с запи­санной программой», который считывает свою программу и данные с одной или не­скольких лент, содержащих входную информацию. В данном разделе будет формализо­вана идея того, что машина Тьюринга является представлением программы, записанной в память компьютера.

Универсальный язык L_u определяется как множество двоичных цепочек, которые яв­ляются кодами (в смысле определения из раздела 9.1.2) пар (М, vv), где М— МТ с двоич­ным входным алфавитом, aw — цепочка из (0+1)*, принадлежащая L{M). Таким обра­зом, L_u — это множество цепочек, представляющих некоторую МТ и допускаемый ею вход. Покажем, что существует МТ U, которую часто называют универсальной машиной Тьюринга, для которой L_u = L(U). Поскольку входом U является двоичная цепочка, то в действительности U — это некоторая М_} в списке машин Тьюринга с двоичным входом (см. раздел 9.1.2).

Рабочая лента

Рис. 9.5. Структура универсальной машины Тьюринга

Проще всего U описывается как многоленточная машина Тьюринга в стиле рис. 8.22. В машине U переходы М вначале хранятся на первой ленте вместе с цепочкой vv. Вторая лента используется для моделирования ленты машины М, в том же формате, что и у кода М. Таким образом, ленточный символ X, машины М кодируется как 0′, а коды разделя­ются одиночными 1. На третью ленту U записывается состояние М, причем состояние q, представляется в виде i нулей. Схема U представлена на рис. 9.5.

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

• Исследует вход для того, чтобы убедиться, что код М является правильным кодом МТ. Если это не так, U останавливается, не допуская. Это действие корректно, по­скольку неправильные коды по договоренности представляют МТ без переходов, а такие МТ не допускают никакого входа.
• Записывает на вторую ленту код входной цепочки Таким образом, каждому сим­волу 0 из w на второй ленте ставится в соответствие цепочка 10, а каждой 1 — це­почка 100. Отметим, что пустые символы, которые находятся на ленте самой М и представляются цепочками вида 1 ООО, на этой ленте появляться не будут. Все клет­ки, кроме занятых символами цепочки w, будут заполняться пустыми символами машины U. Но при этом U знает, что если она ищет имитируемый символ М и нахо­дит свой собственный пустой символ, то она должна заменить его последовательно­стью 1000, имитирующей пустой символ М.
• На третьей ленте записывает 0, т.е. начальное состояние М, и перемещает головку второй ленты U в первую имитируемую клетку.
• Для того чтобы отобразить переход М, U отыскивает на своей первой ленте переход О¹1040^k 10¹10^т, у которого 0′ есть состояние на ленте 3, а О¹ — ленточный символ М, начинающийся с позиции на ленте 2, обозреваемой Это переход, который М со­вершает на следующем шаге. Машина U должна выполнить следующие действия:

а)   изменить содержимое ленты 3 на 0^к, т.е. отобразить изменение состояния М. Для этого U вначале заменяет все символы 0 на ленте 3 пустыми символами, а затем копирует 0^к с ленты 1 на ленту 3;

б)   заменить О’ на ленте 2 символами О¹, т.е. поменять ленточный символ М. Ес­ли потребуется больше или меньше места (т.е. j * Г), то для управления про­странством используются рабочая лента и техника переноса (см. раз­дел 8.6.2);

в)   переместить головку на ленте 2 в ту позицию слева или справа, в которой находится ближайший символ 1. При т = 1 совершается сдвиг влево, а при т = 2 — вправо. Таким образом, U имитирует движение М влево или вправо.

• Если Мне имеет перехода, соответствующего имитируемым состоянию и ленточно­му символу, то в п. 4 переход не будет найден. Таким образом, в данной конфигура­ции М останавливается, и то же самое должна делать
• Если М попадает в свое допускающее состояние, то U допускает.

Этими действиями U имитирует работу М со входом w. U допускает закодированную па­ру (М, w) тогда и только тогда, когда М допускает w.

Более эффективная универсальная МТ

Машина U, эффективно имитирующая М, т.е. не требующая сдвига ленточных сим­волов, должна вначале определять число ленточных символов, используемых М. Если число символов лежит в пределах от 2^k_1 до 2^k— 1, то однозначно представить раз­личные ленточные символы можно с помощью ^-битового двоичного кода. Каждой клетке М можно поставить в соответствие к клеток машины U. Для того чтобы упро­стить имитацию, можно переписать в машине U данные переходы М и вместо опи­санного нами унарного кода переменной длины использовать бинарный код фикси­рованной длины.

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

Представим проблему, которая является РП, но не рекурсивной. Это язык L_u. Нераз­решимость L_u (т.е. его нерекурсивность) во многих отношениях важнее, чем наш преды­дущий вывод о том, что язык Ь^ не является РП. Причина состоит в следующем. Сведе­нием L_a к другой проблеме Р можно показать, что алгоритма, решающего Р, не сущест­вует, независимо от того, является ли Р РП. Однако сведение L& к Р возможно лишь тогда, когда Р не является РП, поэтому L& не может использоваться при доказательстве неразрешимости проблем, которые являются РП, но не рекурсивными. Вместе с тем, ес­ли нужно показать, что проблема не является РП, то можно использовать только Z_d, в то время как язык L_u оказывается бесполезным, поскольку он является РП.

Теорема 9.6. L_u является РП, но не рекурсивным.

Доказательство. В разделе 9.2.3 доказано, что язык L_u является РП. Допустим, что L_a рекурсивен. Тогда по теореме 9.3 L _u (дополнение L_u) — также рекурсивный язык. Но если существует МТ М, допускающая L _и, то, используя описанный ниже метод, можно построить МТ, допускающую L_d. Поскольку нам известно, что L_& не является РП, прихо­дим к противоречию с предположением, что язык L_u является рекурсивным.

Проблема останова

Проблема останова машины Тьюринга считается подобной проблеме L_u; она также является РП, но не рекурсивной. В действительности, определенная А. М. Тьюрингом машина допускала, не попадая в допускающее состояние, а останавливаясь. Для МТ М можно определить Н(М) как множество входов vv, на которых М останавливается независимо от того, допускает ли М вход vv. Тогда проблема останова состоит в опре­делении множества таких пар (М, w), у которых w принадлежит Н(М). Это еще один пример проблемы/языка, которая является РП, но не рекурсивной.

Предположим, что L(M) = L _u. На рис. 9.6 показано, как можно преобразовать МТ М в МТ М\ которая допускает L_d с помощью следующих действий.

Рис. 9.6. Сведение Ьлк L u

• М’ преобразует входную цепочку w в wl 1 В качестве упражнения читатель может написать программу для выполнения этого шага на одной ленте. Однако легче это сделать, используя для копии w вторую ленту, и затем преобразовать двухленточную МТ в одноленточную.
• М’ имитирует М на новом входе. Если w есть w, в нашем перечислении, то М’ опре­деляет, допускает ли М\ вход Поскольку М допускает L _и, то она допускает тогда и только тогда, когда М\ не допускает w_t, т.е. когда w, принадлежит L_d.

Таким образом, М’ допускает w тогда и только тогда, когда w принадлежит L_d. Поскольку по теореме 9.2 машины М’ не существует, приходим к выводу, что язык L_u не является рекурсивным. □

9.2.5. Упражнения к разделу 9.2

• Покажите, что проблема останова, т.е. проблема определения множества пар (М, w), где М останавливается (допуская или нет) на входе и>, является РП, но не рекурсивной. (См. врезку «Проблема останова» в разделе 9.2.4.)
• Во врезке «Почему «рекурсивные»?» из раздела 9.2.1 говорилось о «рекурсив­ных функциях» как модели вычислимости, используемой наравне с машинами Тьюринга. В данном упражнении рассмотрим пример записи рекурсивных функций. Рекурсивная функция — это функция F, определенная конечным на­бором правил. Каждое правило устанавливает значение функции F для опреде­ленных аргументов; в правиле могут присутствовать переменные, неотрица­тельные целочисленные константы, функция прибавления единицы (successor), сама функция F и выражения, построенные композицией перечисленных функ­ций. Например, функция Аккермана определяется следующим образом.
  • /1(0, у) = 1 для всеху > 1.
  • А( 1,0) = 2.
  • А(х; 0) = х + 2 для х > 2.
  • А(х +l,j+l) = А(А(х, у + 1), у) для любых х > 0 и у >

Выполните следующее:

а)   (*) вычислите А(2, 1);

б)   (!) опишите А(х, 2) как функцию от х;

в)   (!) вычислите А(4, 3).

• Опишите неформально многоленточные машины Тьюринга, которые перечис­ляют следующие множества целых чисел в том смысле, что, начав с пустых лент, они печатают на одной из лент цепочку Ю^Ю’²!…, представляющую множество {г’ь г₂, …}:

а)   (*) множество квадратов целых чисел {1, 4, 9, …};

б)   множество простых чисел {2, 3, 5, 7, 11, …};

в)   (!!) множество всех таких г, для которых М\ допускает w,. Указание. Такие i невозможно генерировать в порядке возрастания. Причина состоит в том, что данный язык, который есть L <ь является РП, но не рекурсивным. Такие языки по определению можно перечислить, но не в порядке возрастания. «Прием» с их перечислением состоит в том, чтобы смоделировать работу всех М со входами vv,. При этом мы не можем позволить какой-либо М рабо­тать вечно, поскольку это помешает продолжать проверку для других М_р где i Ф j. Поэтому мы вынуждены работать поэтапно, проверяя на k-и этапе лишь конечное множество машин М ^и ограничивая проверку каждой машины ко­нечным числом шагов. Таким образом, каждый этап проверки будет выпол­нен за конечное время. Поскольку для всякой МТ М и всякого числа шагов 5 найдется такой этап, на котором будет промоделировано не менее s шагов М, то в конце концов мы обнаружим все М, допускающие w_is и перечислим номера г.

• (*) Пусть L_u L₂, …, L_k— набор языков в алфавите Z, для которого верны сле­дующие утверждения.
  • Li ПLj Ф 0 для всехi Ф j, т.е. никакая цепочка не принадлежит сразу двум языкам.
  • Li lj Z₂ U • • U L_k = Е*, т.е. каждая цепочка принадлежит одному из этих языков.
  • Все языки L[, где i = 1, 2, …, к, рекурсивно перечислимы. Докажите, что тогда каждый из этих языков рекурсивен.
• (*!) Пусть L рекурсивно перечислим и L не является РП. Рассмотрим язык L’= {Ow |’vv принадлежит!} U {lw | vv не принадлежит!}.

Можете ли вы наверняка сказать, что язык L’ или его дополнение являются ре­курсивными, РП или не-РП? Ответ обоснуйте.

9.2.6. (!) За исключением операции дополнения в разделе 9.2.2, свойства замкнутости

рекурсивных и РП-языков пока не обсуждались. Выясните, замкнуты ли рекур­сивные и/или РП-языки относительно перечисленных ниже операций:

а)   (*) объединение;

б)   пересечение;

в)    конкатенация;

г)   замыкание Клини (звездочка);

д)   (*) гомоморфизм;

е)   обратный гомоморфизм.

Обосновывая замкнутость, можно использовать неформальные, но достаточно

понятные конструкции.

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

Статус языков L_u и Ц относительно неразрешимости и рекурсивной перечислимо­сти нам уже известен. Используем их для демонстрации других неразрешимых или не РП-языков. В доказательствах используется техника сведения. Все неразрешимые проблемы, которые рассматриваются вначале, связаны с машинами Тьюринга. Куль­минацией данного раздела является доказательство «теоремы Райса». В ней утвержда­ется, что любое нетривиальное свойство МТ, зависящее лишь от языка, допускаемого машиной Тьюринга, должно быть неразрешимым. Материал раздела 9.4 позволяет ис­следовать некоторые неразрешимые проблемы, не связанные ни с машинами Тьюрин­га, ни с их языками.

9.3.1. Сведения

Понятие сведения было введено в разделе 8.1.3. В общем случае, если у нас есть ал­горитм, преобразующий экземпляры проблемы Р_х в экземпляры проблемы Р₂, которые имеют тот же ответ (да/нет), то говорят, что Р\ сводится к Р₂. Доказательство такой сво­димости используется, чтобы показать, что Р₂ не менее трудна, чем Р\. Таким образом, если Р\ не является рекурсивной, то и Р₂ не может быть рекурсивной. Если Р, не являет­ся РП, то и Р₂ не может быть РП. Как уже упоминалось в разделе 8.1.3, чтобы доказать, что проблема Р₂ не менее трудна, чем некоторая известная Р_и нужно свести Р[ к Р₂, а не наоборот.

Как показано на,рис. 9.7, сведение должно переводить всякий экземпляр Р\ с ответом «да» (позитивный) в экземпляр Р₂ с ответом «да», и всякий экземпляр Р, с ответом «нет» (негативный) — в экземпляр Р₂ с ответом «нет». Отметим, что неважно, является ли каж-

Рис. 9.7. Сведение переводит позитивные экземпляры в позитивные, а негативные — в негативные

Формально сведение Pi к Р₂ является машиной Тьюринга, которая начинает работу с экземпляром проблемы Pi на ленте и останавливается, имея на ленте экземпляр пробле­мы Р₂. Как правило, сведения описываются так, как если бы они были компьютерными программами, которые на вход получают экземпляры Р\ и выдают экземпляры Р₂. Экви­валентность машин Тьюринга и компьютерных программ позволяет описывать сведение в терминах как тех, так и других. Значимость процедуры сведения подчеркивается сле­дующей широко используемой теоремой.

Теорема 9.7. Если Pi можно свести к Р₂, то:

а)   если Pi неразрешима, то и Р₂ неразрешима;

б)   если РI не-РП, то Р₂ также не-РП.

Доказательство. Предположим сначала, что проблема Pi неразрешима. Если решить Р₂ возможно, то, объединяя сведение f, к f₂ и алгоритм решения последней, можно по­строить алгоритм, решающий Р_х. Эта идея была проиллюстрирована на рис. 8.7. Пояс­ним подробнее. Пусть дан экземпляр w проблемы Р\. Применим к нему алгоритм, кото­рый переводит w в экземпляр х проблемы Р₂. Затем применим к х алгоритм, решающий Р₂. Если алгоритм выдает ответ «да», то х принадлежит Р₂. Поскольку Pi была сведена к Р₂, то известен ответ «да» для Pi на w, т.е. w принадлежит Р_х. Точно так же, если х не принадлежит Р₂, то и w не принадлежит Р,. Итак, ответ на вопрос «х принадлежит Р₂?» является также правильным ответом на вопрос «w принадлежит Р_ХТ\

Таким образом, получено противоречие с предположением, что проблема Р\ нераз­решима. Делаем вывод, что если Pi неразрешима, то и Р₂ неразрешима.

дый экземпляр Р2 образом одного или нескольких экземпляров Pi. В действительности, обычно лишь небольшая часть экземпляров Р2 образуется в результате сведения.

Рассмотрим теперь часть б. Предположим, что Р₂ (в отличие от Pi) является РП. В данном случае у нас есть алгоритм сведения Pi к Р₂, но для Р₂ существует лишь процеду­ра распознавания, т.е. МТ, которая дает ответ «да», когда ее вход принадлежит Р₂, и мо­
жет работать бесконечно, когда вход не принадлежит Р₂. Как и в части а, с помощью ал­горитма сведения преобразуем экземпляр w проблемы Р_х в экземпляр х проблемы Р₂. За­тем применим к х МТ для Р₂. Если х допускается, то допустим и w.

Эта процедура описывает МТ (возможно, работающую бесконечно), языком кото­рой является Pi. Если w принадлежит Pi, то х принадлежит Р_г, и поэтому данная МТ допускает w. Если же w не принадлежит Р_и то х не принадлежит Р₂. Тогда МТ может или остановиться, или работать бесконечно, но в обоих случаях она не допустит w. Поскольку по предположению МТ, распознающей Р_и не существует, то полученное противоречие доказывает, что МТ для Р₂ также не существует. Таким образом, если Pi не-РП, то и Р₂ не-РП. □

9.3.2. Машины Тьюринга, допускающие пустой язык

В качестве примера сведения, связанного с машинами Тьюринга, исследуем языки, известные как L_e и L_nc. Оба они состоят из двоичных цепочек. Если w — двоичная цепоч­ка, то она представляет некоторую МТ М из перечисления, описанного в разделе 9.1.2.

Если М\ = 0, т.е. М\ не допускает никакого входа, то М, принадлежит Д. Таким обра­зом, Д состоит из кодов всех МТ, языки которых пусты. С другой стороны, если ДМ) не пуст, то w принадлежит Д_е. Таким образом, Д_с состоит из кодов всех машин Тьюринга, которые допускают хотя бы одну цепочку.

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

Д = {М | ДМ) = 0}

Д_е = {М| ДМ) Ф 0}

Отметим, что Д и Д_с— языки над алфавитом {0, 1}, дополняющие друг друга. Как будет видно, Z.,,_e является «более легким». Он РП, но не рекурсивный, в то время как L_e — не-РП.

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

Доказательство. Достаточно предъявить МТ, допускающую L„_e. Проще всего это сделать, описав недетерминированную МТ М, которая схематично изображена на рис. 9.8. Согласно теореме 8.11 Мможно преобразовать в детерминированную МТ.

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

Работа М заключается в следующем.

На вход М подается код МТ M_v

Используя недетерминизм, Мугадывает вход w, который, возможно, допускается М\.

М проверяет, допускает ли М\ свой вход w. В этой части М может моделировать ра­боту универсальной МТ U, допускающей L_u.

Если М{ допускает w, то и М допускает свой вход, т.е. M_t.

Таким образом, если М_{ допускает хотя бы одну цепочку, то М угадает ее (среди прочих, конечно) и допустит А/;. Если же L(M_t) = 0, то ни одна из угаданных w не допускается М^ и Мне допустит М_х. Таким образом, ЦМ) = L_ne. □

Следующим шагом будет доказательство, что язык Ь_ю не является рекурсивным. Для этого сведем к L_ne язык L_u, т.е. опишем алгоритм, который преобразует вход (М, w) в вы­ход М’— код еще одной машины Тьюринга, для которой w принадлежит L(M) тогда и только тогда, когда язык ЦМ’) не пуст. Таким образом, М допускает w тогда и только то­гда, когда М’ допускает хотя бы одну цепочку. Прием состоит в том, что М’ игнорирует свой вход, а вместо этого моделирует работу М на w. Если М допускает w, то М’ допус­кает свой собственный вход. Таким образом, ЦМ’) не пуст тогда и только тогда, когда М допускает w. Если бы L_m. был рекурсивным, то у нас был бы алгоритм выяснения, допус­кает ли Мвход w: построить М’и проверить, будет ли L(M’) = 0. Теорема 9.9. Язык L_ne не является рекурсивным.

Доказательство. Уточним доказательство, кратко описанное выше. Нужно постро­ить алгоритм, который преобразует свой вход — двоичный код пары (М, w) — в МТ М’, для которой ЦМ’) * 0 тогда и только тогда, когда М допускает вход w. Данная конст­рукция схематично представлена на рис. 9.9. Как будет показано, если М не допускает w, то М’ не допускает никакого входа, т.е. ЦМ’) = 0. Но если М допускает w, то М’ допус­кает любой вход, и поэтому, конечно же, ЦМ’) Ф 0.

Рис. 9.9. Схема МТ М’, построенной по (М, w) в теореме 9.9; М’ допускает произвольный вход тогда и только тогда, когда М допускает w

М’ по построению выполняет следующие действия.

1. М’ игнорирует собственный вход. Она заменяет его цепочкой, представляющей МТ М и ее вход w. Поскольку М’ строится для конкретной пары (М, w), имеющей неко­торую длину п, можно построить М’с состояниями q₀, q_x, …, q„ {qo — начальное со­стояние), причем:

а)   в состоянии q-„ i = 0, 1, …, п — 1, М’ записывает (/+ 1)-й бит кода (М, w), пе­реходит в состояние q_i+l и сдвигается вправо;

б)   в состоянии q_n в случае необходимости М’ сдвигается вправо и заполняет все непустые клетки (содержащие «хвост» цепочки х, если ее длина больше п) пробелами.

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

М\ используя дополнительные состояния, моделирует универсальную МТ U на по­лученной ленте.

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

Приведенное описание М’ показывает возможность построения машины Тьюринга, кото­рая переводит код М и цепочки w в код М’. Таким образом, существует алгоритм сведения L_u к L_m. Кроме того, если М допускает w, то М’ допускает любой вход х, который первона­чально содержался на ее ленте. То, что вначале вход х был проигнорирован, не имеет никакого значения, поскольку по определению МТ допускает то, что было на ее ленте до начала операций. Таким образом, если М допускает w, то код М’ принадлежит L,_K.

Наоборот, если Мне допускает vv, то М’никогда не допустит свой вход, каким бы он ни был. Следовательно, в этом случае код М’не принадлежит L_ne. Таким образом, L_u сво­дится к L_ne с помощью алгоритма, который строит М’ по данным М и w. Поскольку L_u не является рекурсивным, то и L_ne также не рекурсивен. Того, что это сведение существует, вполне достаточно для завершения доказательства. Однако для того, чтобы проиллюст­рировать значимость сведения, продолжим наши рассуждения. Если бы L_ne был рекур­сивным, то можно было бы построить алгоритм для L_u следующим образом.

Преобразовать (М, vv) в МТ М’описанным выше способом.

Выяснить с помощью гипотетического алгоритма для i_ne, верно ли ЦМО = 0. Если это так, то сказать, что М не допускает vv, если же ЦМ’) ф 0, то сказать, что М допускает w.

Поскольку из теоремы 9.6 известно, что такого алгоритма для L_u нет, приходим к противо­речию с тем, что Ь_ж является рекурсивным, и делаем вывод, что L„_c — не рекурсивный. □

Теперь известен и статус языка L_c. Если бы Д был РП, то по теореме 9.4 и он, и L_ne были бы рекурсивными. Но поскольку L_ne не является рекурсивным по теореме 9.9, то справедливо следующее утверждение.

Теорема 9.10. Язык L_e не является РП. □ 9.3.3. Теорема Райса и свойства РП-языков

Неразрешимость языков, подобных L_e и L_nc, в действительности представляет собой частный случай гораздо более общей теоремы: любое нетривиальное свойство РП- языков неразрешимо в том смысле, что с помощью машин Тьюринга невозможно распо­знать цепочки, которые являются кодами МТ, обладающих этим свойством. Примером свойства РП-языков служит выражение «язык является контекстно-свободным». Вопрос о том, допускает ли данная МТ контекстно-свободный язык, является неразрешимым ча­стным случаем общего закона, согласно которому все нетривиальные свойства РП- языков неразрешимы.

Свойство РП-языков представляет собой некоторое множество РП-языков. Таким образом, формально свойство языка быть контекстно-свободным — это множество всех КС-языков. Свойство быть пустым есть множество {0}, содержащее только пустой язык.

Почему проблемы и их дополнения различны

Интуиция подсказывает, что в действительности проблема и ее дополнение — одна и та же проблема. Для решения одной можно использовать алгоритм решения другой, и лишь на последнем шаге взять отрицание ответа: вместо «нет» сказать «да» и наобо­рот. Если проблема и ее дополнение рекурсивны, это действительно верно. Однако, как обсуждалось в разделе 9.2.2, существуют две другие возможности. Во- первых, может быть, что ни сама проблема, ни ее дополнение не являются даже РП. Тогда ни одна из них вообще не может быть решена никакой МТ. В этом смысле они по-прежнему похожи друг на друга. Существует, однако, еще одна интересная ситуа­ция типа L_t и L_nt, когда один из языков является РП, а другой — нет. Для языка, являющегося РП, можно построить МТ, которая получает на вход цепочку w и исследует, почему данная цепочка принадлежит языку. Так, для L_ne и данной в ка­честве входа МТ М мы заставляем нашу МТ искать цепочки, которые допускает эта МТ, и, обнаружив хотя бы одну такую цепочку, допускаем М. Если М— МТ с пус­тым языком, то мы никогда не будем знать наверняка, что М не принадлежит L_nt, но при этом никогда и не допустим М, и это будет правильным откликом МТ. С другой стороны, для дополнения этой проблемы — языка L_t, который не является РП, вообще не существует способа, позволяющего допустить все его цепочки. Пред­положим, что нам дана цепочка М, представляющая МТ с пустым языком. Проверяя различные входы М, мы можем никогда не найти такого, который М допускает, но при этом не сможем и быть уверенными в том, что такого входа нет среди еще непро­веренных. Поэтому М никогда не сможет быть допущена, даже если и должна.

Свойство называется тривиальным, если оно либо пустое (т.е. никакой язык вообще ему не удовлетворяет), либо содержит все РП-языки. В противном случае свойство назы­вается нетривиальным.

• Отметим, что пустое свойство 0 и свойство быть пустым языком — не одно и то же.

Мы не можем распознать множество языков так, как сами эти языки. Причина в том, что обычный бесконечный язык нельзя записать в виде цепочки конечной длины, кото­рая может быть входом некоторой МТ. Вместо этого мы должны распознавать машины Тьюринга, которые допускают эти языки. Код самой МТ конечен, даже если язык, кото­рый она допускает, бесконечен. Таким образом, если V— это свойство РП-языков, то L_r— множество кодов машин Тьюринга М, языки ДМ) которых принадлежат V. Гово­ря о разрешимости свойства V, мы имеем в виду разрешимость языка Lp.

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

Доказательство. Пусть V— нетривиальное свойство РП-языков. Вначале допустим, что пустой язык 0 не принадлежит V’, противоположный случай рассмотрим позже. По­скольку V— нетривиально, должен существовать непустой язык Д принадлежащий V. Пусть М/. обозначает МТ, допускающую L.

Сведем Д к Lp, и этим докажем, что язык L^ неразрешим, поскольку Д неразрешим. Алгоритм сведения получает на вход пару (М, w) и выдает некоторую МТ М’. Структура М’представлена на рис. 9.10. Если Мне допускает w, то L(M’) есть 0, и Д№) = L, если М допускает w.

М’— двухленточная МТ. Одна лента используется для моделирования работы М со входом w. Напомним, что алгоритм сведения получает на вход пару (М, w) и может ис­пользовать ее для построения переходов М’. Таким образом, имитация М со входом w «встроена» в М’, которой не нужно считывать с ленты переходы М.

Вторая лента М’ используется для моделирования работы M_L с цепочкой х, вход­ной для М’. Еще раз отметим, что переходы M_L известны алгоритму сведения и мо­гут быть «встроены» в переходы М’. По построению МТ М’ должна выполнять сле­дующие операции.

1. Имитировать работу М со входом w. Отметим, что w не является входом М’. М’ за­писывает Ми w на одну из своих лент и имитирует МТ U на этой паре, как в доказа­тельстве теоремы 9.8.

• Если М не допускает w, то М’ больше ничего не делает, т.е. не допускает любой свой вход х, поэтому ЦМ’) = Мы предположили, что 0 не содержится в свойстве V, поэтому код М’ не принадлежит L-p.
• Если М допускает w, то М’ начинает имитацию M_L на своем собственном входе х. Таким образом, М’ допускает именно язык Поскольку L принадлежит V, то код М’ принадлежит L-p.

Как видим, построение М’ по М и w можно провести в соответствии с некоторым алго­ритмом. Поскольку этот алгоритм превращает (М, w) в М\ которая принадлежит L_p то­гда и только тогда, когда (Л/, и>) принадлежит L_m этот алгоритм представляет собой све­дение ЬцКЬрИ доказывает неразрешимость свойства V.

Для завершения доказательства нужно еще рассмотреть вариант, когда 0 принадле­жит V. Для этого рассмотрим дополнение V свойства V, т.е. множество РП-языков, не обладающих свойством V. Из описанных выше рассуждений следует, что свойство V неразрешимо. Однако поскольку всякая МТ допускает некоторый РП-язык, то L_v , т.е. множество (кодов) машин Тьюринга, не допускающих языки из V, совпадает с Ь^ — множеством МТ, допускающих языки из V. Предположим, что язык разрешим. То­гда L^ также должен быть разрешимым, поскольку дополнение рекурсивного языка ре­курсивно (теорема 9.3). □

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

Согласно теореме 9.11 все проблемы, связанные только с языками машин Тьюринга, неразрешимы. Некоторые из них интересны сами по себе. Например, неразрешимы сле­дующие вопросы.

• Пуст ли язык, допускаемый МТ (ответ дают теоремы 9.9 и 9.3)?
• Конечен ли язык МТ?
• Регулярен ли язык, допускаемый МТ?
• Является ли язык МТ контекстно-свободным?

Вместе с тем, теорема Райса не означает, что любая проблема, связанная с МТ, не­разрешима. Например, вопросы о состояниях МТ, в отличие от вопросов о языке, могут быть разрешимыми.

Пример 9.12. Вопрос о том, имеет ли МТ пять состояний, разрешим. Алгоритм, ре­шающий его, просматривает код МТ и подсчитывает число состояний, встреченных в его переходах.

Еще один пример разрешимого вопроса — существует ли вход, при обработке кото­рого МТ совершает более пяти переходов? Алгоритм решения становится очевидным, если заметить, что, когда МТ делает пять переходов, она обозревает не более девяти кле­ток вокруг начальной позиции головки. Поэтому можно проимитировать пять переходов МТ на любом из конечного числа входов, длина которых не более девяти. Если все эти имитации не достигают останова, то делается вывод, что на любом входе данная МТ со­вершает более пяти переходов. □

9.3.5. Упражнения к разделу 9.3

• (*) Покажите, что множество кодов машин Тьюринга, допускающих все входы, которые являются палиндромами (возможно, наряду с другими входами), нераз­решимо.
• Большая Компьютерная Корпорация для увеличения сократившегося объема продаж решила выпустить высокотехнологичную модель машины Тьюринга под названием МТЗС, оснащенную звонками и свистками. В основном МТЗС сов­падает с обычной МТ, за исключением того, что каждое состояние этой машины отмечено либо как «состояние-звонок», либо как «состояние-свисток». Как толь­ко МТЗС попадает в новое состояние, то, в зависимости от его типа, она либо звенит, либо свистит. Докажите, что проблема определения, свистнет ли когда- нибудь данная МТЗС М при данном входе w, неразрешима.
• Покажите, что язык кодов МТ, которые, начиная с пустой ленты, в конце концов записывают где-либо на ней символ 1, неразрешим.
• (!) В соответствии с теоремой Райса известно, что каждый из следующих вопро­сов неразрешим:

а)   содержит ли L(M) хотя бы две цепочки?

б)   бесконечен ли ЦА/)?

в)    является ли язык L(M) контекстно-свободным?

г)   (*) верно ли, что L(M) = (L{M)fl

Являются ли они рекурсивно перечислимыми или не-РП?

• (!) Пусть язык I состоит из троек (M_h М₂, к), образованных парой кодов МТ и целым числом, для которых ЦМ/) П Ь(М₂) содержит не менее, чем к цепочек. Покажите, что L является РП, но не рекурсивным.
• Покажите, что следующие вопросы разрешимы:

а)   (*) множество кодов МТ М, которые, имея в начальный момент пустую ленту, в конце концов записывают на ней некоторый непустой символ. Указание. Если М имеет т состояний, рассмотрите первые т + 1 совершае­мых ею переходов;

б)   (!) множество кодов МТ, которые никогда не совершают сдвиг влево;

в) (!) множество пар (М, w), для которых МТ М при обработке входа w не обо­зревает никакую клетку на ленте более одного раза.

• (!) Покажите, что следующие проблемы не являются рекурсивно-перечислимыми:

а)   (*) множество пар (М, w), для которых МТ М при обработке входа w не оста­навливается;

б)   множество пар (М_ь М₂), для которых L(M_t) П L(M₂) = 0;

в)   множество троек (М_ь М₂, М₃), для которых L(M_X) = L(M₂) L(M-$), т.е. язык первой машины — это конкатенация языков двух других МТ.

• (!!) Ответьте, является ли каждое из следующих множеств рекурсивным, РП, но не рекурсивным, или не-РП:

а)   (*) множество кодов всех МТ, останавливающихся на любом входе;

б)   множество кодов всех МТ, которые не останавливаются ни на каком входе;

в)   множество кодов всех МТ, останавливающихся хотя бы на одном входе;

г)   (*) множество кодов всех МТ, которые не останавливаются хотя бы на од­ном входе.

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

В этом разделе начнется сведение неразрешимых вопросов о машинах Тьюринга к неразрешимым вопросам о «реальных вещах», т.е. обычных предметах, не имеющих от­ношения к абстрактным машинам Тьюринга. Начнем с проблемы, которая называется «проблемой соответствий Поста» (ПСП). Эта проблема по-прежнему довольно абстракт­на, но она связана уже не с машинами Тьюринга, а с цепочками. Наша цель — доказать неразрешимость этой проблемы, чтобы затем доказывать неразрешимость других про­блем путем сведения ПСП к ним.

Докажем неразрешимость ПСП сведением L_u к ней. Чтобы облегчить доказательство, рассмотрим вначале «модифицированную» версию ПСП, а потом сведем ее к исходной ПСП. Затем сведем L_u к модифицированной ПСП. Цепь этих сведений представлена на рис. 9.11. Поскольку известно, что исходная проблема L_a неразрешима, можно сделать вывод, что ПСП также неразрешима.

	МПСП		ПСП
Алгоритм		Алгоритм

Рис. 9.11. Цепь сведений в доказательстве неразрешимости проблемы соответствий Поста

9.4.1. Определение проблемы соответствий Поста

Экземпляр проблемы соответствий Поста (ПСП) состоит из двух списков равной длины в некотором алфавите 2. Как правило, мы будем называть их списками А и В, и писать А = vw_b w₂, …, w_k и В = х_и х₂, …, х_к при некотором целом к. Для каждого / пара (Wj, Х[) называется парой соответствующих цепочек.

Мы говорим, что экземпляр ПСП имеет решение, если существует последователь­ность из одного или нескольких целых чисел /_ь i₂, …, i_m, которая, если считать эти числа индексами цепочек и выбрать соответствующие цепочки из списков Ли В, дает одну и ту же цепочку, т.е. w_ixwi₂… Wj_m = xj,xj₂…x_jin. В таком случае последовательность /_ь i₂, …, i_m называется решающей последовательностью, или просто решением, данного экземпляра ПСП. Проблема соответствий Поста состоит в следующем.

• Выяснить, имеет ли решение данный экземпляр ПСП.

Пример 9.13. Пусть 2 = {0, 1}, А и В — списки (рис. 9.12). Данный экземпляр ПСП имеет решение. Пусть, например, т = 4, i_x = 2, i₂ = 1, /₃ = 1 и Ц = 3, т.е. решающая после­довательность имеет вид 2, 1, 1,3. Для проверки записываются конкатенации соответст­вующих цепочек каждого из списков в порядке, задаваемом данной последовательно­стью, т.е. w₂w₁vv₁w3 = x₂xix,x₃ = 101111110. Отметим, что это решение— не единствен­ное. Например, 2, 1, 1, 3, 2, 1, 1, 3 также является решением. □

	Список А	Список В
i	Wi	X,
1	1	111
2	10111	10
3	10	0

Рис. 9.12. Экземпляр ПСП

ПСП как язык

Речь идет о вопросе, существует ли решение у экземпляра ПСП, поэтому данную проблему нужно представить в виде языка. Поскольку экземпляры ПСП могут иметь произвольные алфавиты, язык ПСП на самом деле есть множество цепочек над неко­торым фиксированным алфавитом, которыми кодируются экземпляры ПСП. Эти ко­ды во многом напоминают коды машин Тьюринга с произвольными множествами со­стояний и ленточных символов, рассмотренные в разделе 9.1.2. Например, если эк­земпляр ПСП имеет алфавит, содержащий до 2^к символов, то для каждого из этих символов можно- использовать ^-битный двоичный код.

Поскольку каждый экземпляр ПСП имеет конечный алфавит, то некоторое к можно найти для каждого экземпляра. Следовательно, все экземпляры проблемы можно за­кодировать с помощью алфавита из 3-х символов: 0, 1 и «запятой», разделяющей це­почки. Код начинается двоичной записью числа к и запятой за ней. Затем записывает­ся каждая из пар цепочек, в которых цепочки разделены запятыми, а символы зако­дированы к-битными двоичными числами.

Пример 9.14. Пусть, как и раньше, 2 = {0, 1}, но теперь экземпляр проблемы пред­ставлен списками, как на рис. 9.13.

	Список/!	Список В
	W;	х{
1	10	101
2	011	И
3	101	011

Рис. 9.13. Еще один экземпляр ПСП

В этом примере решения нет. Допустим, что экземпляр ПСП, представленный на рис.9.13, имеет решение, скажем, /_ь i₂, …, i_m при некотором т> 1. Утверждаем, что /’i = l. При i] = 2 цепочка, начинающаяся с w₂ = 011, должна равняться цепочке, которая начинается с х₂ = 11. Но это равенство невозможно, поскольку их первые символы — 0 и 1, соответственно. Точно так же невозможно, чтобы i\ = 3, поскольку тогда цепочка, на­чинающаяся с w₃ = 101, равнялась бы цепочке, которая начинается с х₃ = 011. •

Если i’i = 1, то две соответствующие цепочки из списков А и В должны начинаться так: А: 10… В: 101…

Рассмотрим теперь, каким может быть /₂.

• Вариант i₂ — 1 невозможен, поскольку никакая цепочка, начинающаяся с WiWj = 1010, не может соответствовать цепочке, которая начинается с Х\Х\ = 101101; эти цепочки различаются в четвертой позиции.
• Вариант i₂ = 2 также невозможен, поскольку никакая цепочка, начинающаяся с w\w₂ = 10011, не может соответствовать цепочке, которая начинается с х\х₂ = 10111; они различаются в третьей позиции.
• Возможен лишь вариант i₂ =

При i₂ = 3 цепочки, соответствующие списку чисел 1, 3, имеют следующий вид.

А: 10101… В: 101011…

Пока не видно, что последовательность 1, 3 невозможно продолжить до решения. Одна­ко обосновать это несложно. Действительно, мы находимся в тех же условиях, в которых были после выбора = 1. Цепочка из списка В отличается от цепочки из списка А лиш­ним символом 1 на конце. Чтобы избежать несовпадения, мы вынуждены выбирать h — 3, /₄ = 3 и так далее. Таким образом, цепочка из списка А никогда не догонит цепочку из списка В, и решение никогда не будет получено. □

9.4.2. „Модифицированная» ПСП

Свести L_a к ПСП легче, если рассмотреть вначале промежуточную версию ПСП, кото­рая называется модифицированной проблемой соответствий Поста, или МПСП. В моди­фицированной ПСП на решение накладывается дополнительное требование, чтобы первой парой в решении была пара первых элементов списков А и В. Более формально, экземпляр МПСП состоит из двух списков A = w_uw₂, …, и В = х_ьх₂, …, х_к, и решением является последовательность из 0 или нескольких целых чисел /_ь /₂, …, /_т, при которой

WlWi,Wi₂…W_im = ад,х_;2…х;_т.

Отметим, что цепочки обязательно начинаются парой (vv_b х_х), хотя индекс 1 даже не указан в качестве начального элемента решения. Кроме того, в отличие от ПСП, решение которой содержит хотя бы один элемент, решением МПСП может быть и пустая после­довательность (когда W\ =x_t). Однако такие экземпляры не представляют никакого ин­тереса и далее не рассматриваются.

Частичные решения

В примере 9.14 для анализа экземпляров ПСП используется широко распространен­ный метод. Рассматривается, какими могут быть частичные решения, т.е. последова­тельности индексов /_ь /₂, …, для которых одна из цепочек w_nw₎₂..,\v_ir и x_nx_l2…x_h яв­ляется префиксом другой, хотя сами цепочки не равны. Заметим, что если последова­тельность целых чисел является решением, то всякий префикс этой после­довательности должен быть частичным решением. Поэтому понимание того, как вы­глядят частичные решения проблемы, позволяет определить, какими могут быть пол­ные решения.

Отметим, однако, что, поскольку ПСП неразрешима, не существует и алгоритма, по­зволяющего вычислять все частичные решения. Их может быть бесконечно много, а также, что гораздо хуже, если даже частичные решения wi,w_i2…wi_r и xj|x_i2…x_ir ведут к решению, разница их длин может быть сколь угодно большой.

Пример 9.15. Списки, представленные на рис. 9.12, можно рассматривать как экзем­пляр МПСП. Однако этот экземпляр МПСП не имеет решения. Для доказательства заме­тим, что всякое его частичное решение начинается с индекса 1, поэтому цепочки, обра­зующие решение, должны начинаться следующим образом.

А: 1…

В: 111…

Следующим целым в решении не может быть 2 или 3, поскольку и w₂, и w₃ начинаются с 10, и поэтому при таком выборе возникнет несоответствие в третьей позиции. Таким об­разом, следующий индекс должен быть 1, и получаются такие цепочки. А: 11… В: 111111…

Эти рассуждения можно продолжать бесконечно. Только еще одно число 1 позволяет из­бежать несоответствия в решении. Но если все время выбирается индекс 1, то цепочка В остается втрое длиннее А, и цепочки никогда не сравняются. □

Важным шагом в доказательстве неразрешимости ПСП является сведение МПСП к ПСП. Далее будет показано, что МПСП неразрешима, путем сведения L_u к МПСП. Тем самым будет доказана неразрешимость ПСП. Действительно, если бы она была разре­шима, то можно было бы решить МПСП, а следовательно, и L_u.

По данному экземпляру МПСП с алфавитом Е соответствующий экземпляр ПСП строится следующим образом. Вначале вводится новый символ *, который помещается между символами цепочек экземпляра МПСП. При этом в цепочках списка А он следует за символами алфавита Е, а в цепочках списка В — предшествует им. Исключением яв­ляется новая пара, которая строится по первой паре экземпляра МПСП; в этой паре есть дополнительный символ * в начале w_h поэтому она может служить началом решения ПСП. К экземпляру ПСП добавляется также заключительная пара ($, *$). Она служит последней парой в решении ПСП, имитирующем решение экземпляра МПСП.

Формализуем описанную конструкцию. Пусть дан экземпляр МПСП со списками А = w_u w₂, …, w_k и В = х_и х₂, …, х_к. Предполагается, что символы * и $ отсутствуют в ал­фавите Е данного экземпляра МПСП. Строится экземпляр ПСП со списками С = у_п, у_и …, Ук+i и D = z₀, zi, …, z_k+1 следующим образом.

• Для /= 1, 2, …, к положим равной w, с символом * после каждого ее символа, а Zj — равной х, с символом * перед каждым ее символом.
• >’о = *у_х и z₀ = zi, т.е. нулевая пара выглядит так же, как первая, с той лишь разницей, что в начале цепочки из первого списка есть еще символ *. Отметим, что нулевая пара будет единственной парой экземпляра ПСП, в которой обе цепочки начинаются одним и тем же символом, поэтому всякое решение данного экземпляра ПСП долж­но начинаться с индекса 0.
• у_к+1 = $ иг_к+1 = *$.

Пример 9.16. Пусть рис. 9.12 изображает экземпляр МПСП. Тогда экземпляр ПСП, построенный с помощью описанных выше действий, представлен на рис. 9.14. □ Теорема 9.17. МПСП сводится к ПСП.

Доказательство. В основе доказательства лежит описанная выше конструкция. До­пустим, что iь i₂, …, i_m — решение данного экземпляра МПСП со списками А и В; тогда w₁w_i|w_i2…w_im = х1х_пх₁₂…х{_т. Если заменить каждую цепочку w соответствующей у и каж­дую х— соответствующей z, то получатся две почти одинаковые цепочки         и

Z\Z{\Z\i—Z[_m. Разница между ними в том, что у первой не хватает * в начале, а у второй — в конце, т.е.

*у\у^п-■ -yim = zlzi,z_i2.. -z_im*.

	Список С	Список D
i	У<	zi
0	*1*	*1*1*1
1	1*
2	1*0*1*1*1*	*1*0
3	1*0*	*0
4	$	*$

Рис. 9.14. Построение экземпляра ПСП по экземпляру МПСП

Однако уо = *V| и z₀ = z_t, поэтому можно «расправиться» с * в начале, изменив первый индекс на 0:

УоУпУп— -Уы = гоВД₂.. .z_im*. Для учета * в конце добавим индекс k + 1. Поскольку y_k+) = $, a z_k+I = *$, получим:

УъУ^Уъ-■-УтУы = z₀zi₁zi₂…zi_mz_k+1. Итак, показано, что последовательность 0, /_ь /₂,…, i_m, к + 1 — решение экземпляра ПСП.

Теперь докажем обратное, т.е. если построенный экземпляр ПСП имеет решение, то исходный экземпляр МПСП также имеет решение. Заметим, что решение данного экземпляра ПСП должно начинаться индексом 0 и заканчиваться индексом к + 1, по­скольку только в нулевой паре цепочки у₀ и z₀ начинаются и только в (к + 1)-й паре цепочки y_k+1 и z_k+1 оканчиваются одним и тем же символом. Таким образом, решение экземпляра ПСП можно записать в виде 0, /_ь i₂, …, i_m, к + 1.

Мы утверждаем, что /_ь i₂, …, i_m есть решение экземпляра МПСП. Действительно, из цепочкиy_Qy_jj’i₂…yi_m>’_k+i можно удалить все символы * и символ $ в конце. В результате получим цепочку w_lw_uw_ll…w\_m. Точно так же, удалив символы * и символ $ из цепочки ZoZ;,^.. .Z_imr_k._b получим xix_ux_l2 .. ,x,_m. Поскольку

УаУ\1У\2-■ -УхпУы = гоЗД₂.. .z_itnz_k+1, получаем:

Итак, решение экземпляра ПСП содержит в себе решение экземпляра МПСП.

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

9.4.3. Завершение доказательства неразрешимости ПСП

Завершим цепь сведений (см. рис. 9.11), сведя L_u к МПСП. По заданной паре (М, w) строится экземпляр МПСП (А, В), имеющий решение тогда и только тогда, когда МТ М допускает вход w.

Основная идея состоит в том, что частичные решения экземпляра МПСП (А, В) ими­тируют обработку входа w машиной М. Частичные решения будут состоять из цепочек, которые являются префиксами последовательности МО М #а_л#а₂#а_ъ#…, где о_А— на­чальное МО Мпри входной цепочке w и а, aj₊₁ для всех /’. Цепочка из списка В всегда на одно МО впереди цепочки из списка А, за исключением ситуации, когда М попадает в допускающее состояние. В этом случае используются специальные пары, позволяющие списку А «догнать» список бив конце концов выработать решение. Однако если машина не попадает в допускающее состояние, то эти пары не могут быть использованы, и про­блема не имеет решения.

Для того чтобы упростить построение экземпляра МПСП, воспользуемся теоре­мой 8.12, согласно которой можно считать, что МТ никогда не печатает пробел и ее го­ловка не сдвигается левее исходного положения. Тогда МО машины Тьюринга всегда будет цепочкой вида aqP, где аи (3 — цепочки непустых символов на ленте, а с/ — со­стояние. Однако тогда, когда головка обозревает пробел непосредственно справа от а, позволим цепочке /3 быть пустой вместо того, чтобы помещать пробел справа от состоя­ния. Таким образом, символы цепочек а и /3 будут в точности соответствовать содержи­мому клеток, в которых записан вход, а также всех тех клеток справа, в которых головка уже побывала.

Пусть М= (Q, Е, Г, 5, q₀, В, F) — машина Тьюринга, удовлетворяющая условиям тео­ремы 8.12, и w — входная цепочка из Е*. По ним строится экземпляр МПСП следующим образом. Чтобы понять, почему пары выбираются пары именно так, а не иначе, нужно помнить, что нам нужно, чтобы первый список всегда на одно МО отставал от второго, если только М не попадает в допускающее состояние.

1. Первая пара имеет следующий вид.

Список А Список В

#                  #q_Qw#

В соответствии с правилами МПСП эта пара — первая в любом решении. С нее на­чинается имитация М на входе w. Заметим, что в начальный момент список В опе­режает список А на одно полное МО.

Ленточные символы и разделитель # могут быть добавлены в оба списка. Пары

Список А Список В

X                      X                       для каждого X из Г

# #

позволяют «копировать» символы, не обозначающие состояния. Выбирая такие пары, можно одновременно и удлинить цепочку списка А до соответствующей цепочки списка В, и скопировать часть предыдущего МО в конец цепочки списка В. Это поможет нам за­писать в конец цепочки списка В следующее МО в последовательности переходов М.

Для имитации перехода М применяются специальные пары. Для всех q из Q — F (т.е. состояние q не является допускающим), р из Q и X, Y,Z из Г есть следующие пары.

Список А    Список В

qX              Yp                 если 8(q, X) = (p,Y, R)

ZqX            pZY               если S(iq, X) = (p, Y, L); Z— любой ленточный символ

q#               Yp#               если S(q, В) = (p, Y, R)

Zq#             pZY#             если S(q, B) = (p, Y, L); Z — любой ленточный символ

Как и в пункте 2, эти пары позволяют добавить к цепочке В следующее МО, допи­сывая цепочку А таким образом, чтобы она соответствовала цепочке В. Однако эти пары используют состояние для определения, как нужно изменить текущее МО, что­бы получить следующее. Эти изменения— новое состояние, ленточный символ и сдвиг головки — отображаются в МО, которое строится в конце цепочки В.

Если МО, которое находится в конце цепочки В, содержит допускающее состояние, нужно сделать частичное решение полным. Для этого добавляются «МО», которые в действительности не являются МО машины М, а отображают ситуацию, при которой в допускающем состоянии разрешается поглощать все ленточные символы по обе стороны от головки. Таким образом, если q — допускающее состояние, то для всех ленточных символов X и Г существуют следующие пары.

Список А Список В

XqY               q

Xq                  q

qY                  q

Наконец, если допускающее состояние поглотило все ленточные символы, то оно ос­тается в одиночестве как последнее МО в цепочке В. Таким образом, разность цепо­чек (суффикс цепочки В, который нужно дописать к цепочке А для того, чтобы она со­ответствовала В) есть <т#, и для завершения решения используется последняя пара.

Список А Список В

qM                  #

В дальнейшем пары этих пяти типов называются парами из правила 1, из правила 2 и так далее.

Пример 9.18. Преобразуем в экземпляр МПСП машину М= {{q_h q₂, q₃}, {0, 1}, {0, 1, В}, 8, q_h В, {q₃}) с таблицей 8

	8(q„ 0)	1)	fifa, В)
Я1	(<72,1, Л)	(Я2, 0, L)	(Я 2, 1,1)
Я 2	(Яз, 0, L)	СЯ1, о, R)	(Я2, о, R)
Яз	—	—	—

и входной цепочкой w = 01.

Чтобы упростить построение, заметим, что М никогда не печатает пробел В, и его не будет ни в одном МО. Поэтому все пары с пустым символом В опускаются. Полный спи­сок пар с указанием их происхождения представлен на рис. 9.15.

Отметим, что М допускает входную цепочку 01 в результате следующей последова­тельности переходов.

q,01 Н lftl Н Н 1^01 q₃Wl

Рассмотрим последовательность частичных решений, которая имитирует эти вычисления Мив конце концов приводит к решению. Начать нужно с первой пары, как того требует всякое решение МПСП. А:#

В: #q,01#

Для того чтобы частичное решение можно было продолжить, следующая цепочка из списка А должна быть префиксом разности q/01 #. Поэтому следующей парой должна быть (qfi, 1 q₂). Это одна из пар, имитирующих переходы, полученная по правилу 3. Итак, получаем следующее частичное решение.

A: #qfi В: #qfi\#\q₂

Теперь можно продолжить частичное решение, используя «копирующие» пары из прави­ла 2 до тех пор, пока не дойдем до состояния во втором МО. Тогда частичное решение примет такой вид. A:#q,01#1 В: #q,01#\q₂l#l

Для имитации перехода тут снова можно использовать пару из правила 3. Подходящей является пара (<721, 0qi), и в результате получается следующее частичное решение.

A: #q_l0l#lq₂l В: #qfi\#\q₂\#\0q,

Правило	Список А	Список В	Источник
(1)	#	#q, 01#
(2)	0	0
	1	1
	#	#
(3)	q, 0		Siqi,0) = (q2, 1 ,R)
	0<7,1#	q2 00	S(qul) = (q2, 0,1)
	lq,l#	q2l0	Siqi,l) = (q2, 0, L)
	0 q,#	q2 01#	diqi,B) = (q2,\,L)
	1 q,#	q211#	Siqi,B) = (q2,\,L)
	0q20	q300#	S(q2, 0) = (q3, 0, L)
	lq20	q310#	8{Чъ 0) = (qh 0,1)
	q21	0 q,	S(q2, l) = (qu0, R)
	q2#	0 q2#	%q2, B) = (q2, 0, R)
(4)	0q30	qs
	0 q3l	qj
	\qs 0	q3
	\q3\	qs
	0 q3	qs
		q3
	qs 0	qs
		qs
(5)	q3##	#

Рис. 9.15. Экземпляр МПСП, построенный по МТ М и слову w из примера 9.18

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

A:#q,0\#\q₂l#\ В: #qfimq₂\mq,#\

Подходящей парой из правила 3 является (0qfi, q₂01#), и получается новое частич­ное решение.

A: #q,0l#lq₂m0q₁#

В: #q,0l#lq₂m0q,#lq₂0l# Используя теперь еще одну пару (\q₂0, q₃10) из правила 3, приходим к допусканию.

А: %Д)1#1<7₂1#10<7;#1<7₂0

В: #^01#1^1#10^#1^01#^10 Теперь, с помощью пар из правила 4 в МО исключаются все символы, кроме q₃. Для правильного копирования символов нужны также пары из правила 2. Частичное решение продолжается до следующего.

А: #q,0l#lq₂l#l0q,#lq₂0l#q₃l0l#q₃0l#q₃l#

В: #qj0\#\q₂l#\0qi#lq₂0\#q₃\01#q₃0\#q₃\#q₃# Теперь в МО находится лишь q₃. Чтобы завершить решение, можно использовать пару (q₃##, #) из правила 5.

A: #qi01#lq₂l#10qi#lq₂01#q₃l01#q₃0l#q₃l#q₃##

В: #qi0l#lq₂l#\0qi#lq₂0l#q₃l0\#q₃0l#q₃l#q₃##

□

Теорема 9.19. Проблема соответствий Поста неразрешима.

Доказательство. Цепь сведений, представленная на рис. 9.11, почти завершена. Све­дение МПСП к ПСП было показано в теореме 9.17. В данном разделе приведена конст­рукция, позволяющая свести L_u к МПСП. Таким образом, для завершения доказательства неразрешимости ПСП покажем, что эта конструкция корректна, т.е.

• М допускает w тогда и только тогда, когда построенный экземпляр МПСП имеет решение.

(Необходимость) Основную идею подсказывает пример 9.18. Если w принадлежит L(M), то можно проимитировать работу М со входом w, начав с пары из правила 1. Для копирования состояния каждого МО и имитации одного перехода М используются пары из правила 3, а для копирования ленточных символов и при необходимости маркера # — из 2. Если М попадает в допускающее состояние, то с помощью пар из правила 4 и за­ключительной пары из 5 мы позволяем цепочке А догнать цепочку В, тем самым форми­руя решение.

(Достаточность) Нужно доказать, что если данный экземпляр МПСП имеет реше­ние, то только потому, что М допускает w. Отметим, что, поскольку мы имеем дело с МПСП, любое решение должно начинаться с первой пары, так что начало частичного решения имеет Следующий вид.

А:#

В: #q₀w#

Поскольку в этом частичном решении нет допускающего состояния, то пары из правил 4 и 5 бесполезны. Состояния и окружающие их один или два символа могут быть обрабо­таны только с помощью пар из правила 3, а все остальные ленточные символы и # долж­ны быть обработаны с помощью пар из правила2. Поэтому, если Мне попала в допус­кающее состояние, все частичные решения имеют общий вид А: х В: ху,

где х — последовательность МО машины М, представляющих вычисления М со входом w, возможно, с символом # и началом а следующего МО в конце. Разность у содержит завершение а, еще один символ # и начало МО, следующего за а, вплоть до точки, на которой заканчивается а в х.

Отметим, что до тех пор, пока М не попадает в допускающее состояние, частичное решение не является решением, поскольку цепочка В длиннее цепочки А. Поэтому, если решение существует, то М должна когда-нибудь попасть в допускающее состояние, т.е. допустить w. □

9.4.4. Упражнения к разделу 9.4

Выясните, имеют ли решение следующие экземпляры ПСП. Каждый из них представлен двумя списками — А и В, и /-е цепочки списков соответствуют друг другу (/= 1, 2,…).

а)    (*) А = (01,001, 10); В = (011, 10,00).

б)   А = (01,001, 10); В = (011,01,00).

в)   А = (ab, a, be, с); В = (be, ab, са, а).

(!) Было доказано, что ПСП неразрешима в предположении, что алфавит £ мо­жет быть произвольным. Покажите, что ПСП неразрешима даже при ограниче­нии Е = {0, 1}, сведя ПСП к данному частному случаю.

(*!) Допустим, ПСП ограничена односимвольным алфавитом Е = {0}. Будет ли ПСП и в этом ограниченном случае по-прежнему неразрешимой?

(!) ТАГ-система Поста образуется множеством пар цепочек в некотором ко­нечном алфавите X и стартовой цепочкой. Если (w, х) — пара и у — произволь­ная цепочка в Е, то мы говорим, что wy |- ух. Таким образом, на одном шаге

можно стереть некоторый префикс w «текущей» цепочки wy и вместо него в

*

конце приписать второй компонент пары с w — цепочку х. Определим |- как

нуль или несколько шагов точно так же, как для порождений в КС-грам-

*

матиках. Покажите, что проблема выяснения, верно ли z |- е для данного мно­жества пар Р и стартовой цепочки z, неразрешима. Указание. Пусть для любых

МТ М и цепочки w стартовая цепочка z является начальным МО со входом w и разделителем # на конце. Выберите пары Р так, что всякое МО М должно в кон­це концов превращаться в МО, в которое М попадает за один переход. Устройте так, что если М попадает в допускающее состояние, то текущая цепочка может быть в конце концов стерта, т.е. сведена к е.

9.5. Другие неразрешимые проблемы

Здесь рассматривается ряд других неразрешимых проблем. Основным методом дока­зательства их неразрешимости является сведение к ним ПСП.

Проблемы, связанные с программами

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

Наша программа может выполнять любое конкретное действие, например, останав­ливаться или печатать фразу hello, world, если она нашла решение. В противном случае программа никогда не выполняет это конкретное действие. Таким образом, во­прос о том, печатает ли программа hello, world, останавливается ли, вызывает ли определенную функцию, заставляет ли консоль звенеть, или выполняет любое другое не­тривиальное действие, неразрешим. В действительности для программ справедлив ана­лог теоремы Райса: всякое нетривиальное свойство программы, связанное с ее действия­ми (но не лексическое или синтаксическое свойство самой программы), является нераз- ршиыым.

Неразрешимость проблемы неоднозначности КС-грамматик

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

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

Уточним эту идею. Пусть экземпляр ПСП состоит из списков А = w_b w₂, Wk и В = х_{, х₂, …, х_к. Для списка А построим КС-грамматику с одной переменной А. Терминалами будут все символы алфавита Z, используемые в данном экземпляре ПСП, плюс не пере­секающееся с Е множество индексных символов а_ь а₂, …, а_к, которые представляют вы­боры пар цепочек в решении ПСП. Таким образом, индексный символ а, представляет выбор Wi из списка А или из списка В. Продукции КС-грамматики для списка А имеют следующий вид.

А —» wiAdi | w₂Aa₂ I … I w^Aa^ | W\d\ [ w₂a₂ I … I Wk«k Обозначим эту грамматику через G_A, а ее язык — через L_A. Язык типа L_A будет называть­ся в дальнейшем языком для списка А.

Заметим, что все терминальные цепочки, порожденные переменной А в G_A, имеют вид Wi₁Wi₂—Wi_II1ai_in«-a_i2ai₁ при некотором т > 1, где /_ь i₂, …, i_m— последовательность це­лых чисел в пределах от 1 до к. Все выводимые цепочки содержат одиночный символ А, отделяющий цепочки w от индексных символов а, до тех пор, пока не используется одно из к правил последней группы, в которых А отсутствует. Поэтому деревья разбора имеют структуру, представленную на рис. 9.16.

А

Рис. 9.16. Общий вид деревьев разбора в грамматике GA

Заметим также, что любая терминальная цепочка порождается в G_A одним-един- ственным способом. Индексные символы в конце цепочки однозначно определяют, ка­кое именно правило должно использоваться на каждом шаге, поскольку тела лишь двух продукций оканчиваются данным индексным символом а,: А —> щАа, и Л —> и^а;. Первую продукцию нужно использовать, когда данный шаг порождения не последний, в против­ном же случае используется вторая продукция.

Рассмотрим теперь вторую часть экземпляра ПСП— список В = х_х,х₂, …,x_k. Этому списку мы поставим в соответствие еще одну грамматику Gb с такими про­дукциями.

В —> х\Ва_х | х₂Ва₂ I … I хфа_к \ х_ха_х | х₂а₂ | … | x_ka_k

Язык этой грамматики обозначим через L_в. Все замечания, касающиеся G_A, справедливы и для G_B. В частности, терминальная цепочка из L_u имеет одно-единственное порожде­ние, определяемое индексными символами в конце этой цепочки.

Наконец, мы объединяем языки и грамматики двух списков, формируя грамматику G_ab для всего данного экземпляра ПСП. G_AB имеет следующие компоненты.

Переменные А, В и S, последняя из которых — стартовый символ.

Продукции S —> А | В.

Все продукции грамматики G_A.

Все продукции грамматики G_B.

Утверждаем, что грамматика G_AB неоднозначна тогда и только тогда, когда экземп­ляр (А, В) ПСП имеет решение. Это утверждение является основным в следующей теореме.

Теорема 9.20. Вопрос о неоднозначности КС-грамматики неразрешим. Основная часть сведения ПСП к вопросу о неразрешимости КС-грамматики проведе­на выше. В силу неразрешимости ПСП это сведение доказывает неразрешимость про­блемы неоднозначности КС-грамматики. Остается лишь показать корректность приве­денной конструкции, т.е. что

• G_ab неоднозначна тогда и только тогда, когда экземпляр (А, В) ПСП имеет решение.

(Достаточность) Предположим, что i_x,i₂,…,i_m— решение данного экземпляра ПСП. Рассмотрим два порождения в G_AB.

S=>A=> Wjj/la;, => ~w_nw_xlAa_na_n =>•■■=>

Wj [Wfc • • ■ Щ_т-1 Л°im-1′ ‘ ‘ ^ai2I => Wi I Wi2 • • ■ ^Wim°im’ » ^ai2°i I

S => В => x_nBa_tl => x^x_nBa_na_n =>■■■=>

Поскольку /ь i₂, …, z_m— решение, то w_:lw_n—w_lm = х_их,₂—х,_т, т.е. эти два порождения представляют собой порождения одной и той же цепочки. А поскольку сами порожде­ния, очевидно, являются двумя различными левыми порождениями одной и той же тер­минальной цепочки, делаем вывод, что грамматика G_AB неоднозначна.

(Необходимость) Как было отмечено ранее, для данной терминальной цепочки суще­ствует не более одного порождения в G_A и не более одного порождения в G_B. Поэтому терминальная цепочка может иметь в G_Ab два левых порождения лишь в том случае, ес­ли одно из них начинается с5=>^ и продолжается порождением в G_A, а второе начина­ется с S => В и продолжается порождением в G_B.

Цепочка с двумя порождениями имеет окончание из индексов а,_т—а₁₂а,, при неко­тором т> 1. Это окончание и должно быть решением данного экземпляра ПСП, по­скольку то, что ей предшествует в цепочке с двумя порождениями, есть одновременно

hw_ilw,₂—w_lm,hx_ilx_il—x_im. □

9.5.3. Дополнение языка списка

Наличие контекстно-свободных языков, подобных Ь_А для списка А, позволяет пока­зать неразрешимость ряда проблем, связанных с КС-языками. Еще больше фактов о не­разрешимости свойств КС-языков можно получить, рассмотрев дополнение этого языка L_a . Отметим, что язык L_A состоит из всех цепочек в алфавите X U {а/, а₂, …, а_к}, не со­держащихся в L_A, где £ — алфавит некоторого экземпляра ПСП, а а, — символы, кото­рые не принадлежат Z и представляют индексы пар в этом экземпляре ПСП.

Интересными элементами языка L_A являются цепочки, префикс которых принадле­жит Z , т.е. является конкатенацией цепочек из списка А, а суффикс состоит из индекс­ных символов, не соответствующих цепочкам из префикса. Однако помимо этих эле­ментов в L_a содержатся цепочки неправильного вида, не принадлежащие языку регу­лярного выражения Z*(a, + а₂ + … + а_к)*.

Мы утверждаем, что L_A является КС-языком. В отличие от L_A, грамматику для 1_А построить нелегко, но можно построить МП-автомат, точнее— детерминированный МП-автомат. Конструкция описывается в следующей теореме.

Теорема 9.21. Если Ь_А— язык для списка А, то L_A является контекстно-свобод­ным языком.

Доказательство. Пусть Е— алфавит цепочек из списка А= (w_;,w₂, …,Wk}, а 1= {а/,а₂, …, йк}— множество индексных символов. ДМПА Р, который по по­строению должен допускать L_A , работает следующим образом.

Обозревая символ из £, Р записывает его в магазин. Поскольку все цепочки из X* принадлежат L_A , Р допускает их по мере чтения.

При виде индексного символа из /, скажем, а„ Р просматривает магазин, чтобы про­верить, образуют ли символы из его верхней части цепочку w,^R, т.е. обращение соот­ветствующей цепочки:

а)   если это не так, то входная цепочка, а также всякое ее продолжение принад­лежат . Поэтому Р переходит в допускающее состояние, в котором он до­читывает вход, не изменяя содержимое магазина;

б)   если цепочка Wi^R была извлечена из верхней части магазина, но маркер дна магазина не показался на вершине, то Р допускает, но запоминает в своем состоянии, что он ищет только символы из / и может еще встре­тить цепочку из L_A (которую не допустит). Р повторяет шаг 2 до тех пор, пока вопрос о принадлежности входа языку L_A будет оставаться не­разрешенным;

в)   если vf;^R была извлечена и показался маркер дна магазина, то Р прочитал вход, принадлежащий L_A. Р не допускает этот вход. Однако, поскольку вся­кое продолжение этого входа уже не может содержаться в L_A, Р переходит в такое состояние, в котором он допускает все последующие входы, не изме­няя магазин.

3. Если после того, как Р считал один или несколько символов из /, он встречает еще один символ из Z, то входная цепочка не может принадлежать L_A, поскольку имеет неправильную форму. Поэтому Р переходит в состояние, в котором он допускает

этот и все последующие входы, не изменяя магазин.

□

Для получения результатов о неразрешимости КС-языков можно использовать L_a, L_b и их дополнения различными способами. Часть этих фактов собрана в сле­дующей теореме.

Теорема 9.22. Пусть G/ и G₂ — КС-грамматики, a R — регулярное выражение. Тогда неразрешимы следующие проблемы:

а) L(G,)f)L(G₂) = 0?

б) L(Gi) — L(G₂) ?

в)   ЦО,) = ЦЯ)?

г)   верно ли, что L(Gj) — 7* для некоторого алфавита Т1

д)   L(G,)cL(G₂)?

е)  L(R) с L(Gi) ?

Доказательство. Каждое из доказательств представляет собой сведение ПСП. Пока­жем, как преобразовать экземпляр (А, В) ПСП в вопрос о КС-грамматиках и/или регу­лярных выражениях, который имеет ответ «да» тогда и только тогда, когда данный эк­земпляр ПСП имеет решение. В некоторых случаях ПСП сводится к самому вопросу, сформулированному в теореме, в других же случаях —■ к его дополнению. Это не имеет значения, поскольку, если показано, что дополнение проблемы неразрешимо, то сама проблема также не может быть разрешимой, так как рекурсивные языки замкнуты отно­сительно дополнения (теорема 9.3).

Алфавит цепочек данного экземпляра ПСП обозначим Е, а алфавит индексных символов — I. В наших сведениях будем опираться на то, что L_A, L_B, L_A и L_B имеют КС-грамматики. КС-грамматики либо строятся непосредственно, как в разделе 9.5.2, либо вначале строятся МП-автоматы для языков-дополнений (см. теорему 9.21), а за­тем с помощью теоремы 6.14 они преобразуются в КС-грамматики.

Пусть L(Gj) = L_K и L(G\) = L_B. Тогда L(G/) f) L(G₂) — множество решений данного экземпляра ПСП. Пересечение пусто тогда и только тогда, когда решений нет. Отме­тим, что технически мы свели ПСП к языку, который состоит из пар КС-грамматик с непустым пересечением их языков, т.е. показали, что проблема «является ли пересе­чение языков двух КС-грамматик непустым?» неразрешима. Однако, как указано во введении к доказательству, доказать неразрешимость дополнения проблемы — это то же самое, что доказать неразрешимость самой проблемы.

Поскольку КС-языки замкнуты относительно объединения, то можно построить КС- грамматику G; для L_a U L_B . Поскольку (Е U /)* — регулярное множество, то для него, конечно же, можно построить КС-грамматику G₂■ Далее, L_A U L_B — L_A П L_B ■ Таким образом, в L(Gi) отсутствуют лишь цепочки, которые представляют решения данного экземпляра ПСП. L(G₂) содержит все цепочки из (Е U Г)’, так что эти языки совпадают тогда и только тогда, когда данный экземпляр ПСП не имеет решения.

Рассуждения точно такие же, как и в п. 2, но полагаем R регулярным выражением

(г U i)\

Достаточно рассуждений п. 3, поскольку Е U /— единственный алфавит, замыкани­ем которого может быть L_A U L_B .

Пусть G/ — КС-грамматика для (2 U Г) и G₂ — КС-грамматика для L_A \J L_B . Сле­довательно, L(Gj) с L(G₂) тогда и только тогда, когда L_A U L_B = (Е U /)*, т.е. тогда и только тогда, когда данный экземпляр ПСП не имеет решения.

Рассуждения точно такие же, как и в п. 5, но полагаем R регулярным выражением

(Е UI)*, a L(Gi) — Г_л U V □

9.5.4. Упражнения к разделу 9.5

9.5.1. (*) Пусть L— множество (кодов) КС-грамматик G, у которых L(G) содержит хотя бы один палиндром. Покажите неразрешимость L. Указание. Сведите ПСП к L путем построения по каждому экземпляру ПСП грамматики, содержащей палиндром тогда и только тогда, когда этот экземпляр ПСП имеет решение.

• (!) Покажите, что язык L_A U L_B является регулярным тогда и только тогда, ко­гда он представляет собой множество всех цепочек над своим алфавитом, т.е. экземпляр (А, В) ПСП не имеет решения. Таким образом, докажите неразреши­мость вопроса, порождает ли КС-грамматика регулярный язык. Указание. До­пустим, решение ПСП существует; например, в L_A U L_B нет цепочки wx, где w — цепочка из алфавита экземпляра ПСП, ах — соответствующая цепочка ин­дексных символов, записанная в обратном порядке. Определим гомоморфизм h(0) = w и h( l)=x. Тогда, что представляет собой L_A U L_B )? В доказатель­стве того, что язык L_a U L_B нерегулярен, используйте замкнутость регулярных множеств относительно обратного гомоморфизма и дополнения, а также лемму о накачке для регулярных множеств.
• (!!) Вопрос о том, является ли дополнение КС-языка также КС-языком, не­разрешим. С помощью упражнения 9.5.2 можно показать, что неразрешим вопрос о том, является ли дополнение КС-языка регулярным языком, но это не одно и то же. Чтобы доказать первое утверждение, нужно определить другой язык, который представляет цепочки, не являющиеся решениями эк­земпляра (А, В) ПСП. Пусть Lав есть множество цепочек вида wttxttyttz со следующими свойствами.
  • w и х — цепочки над алфавитом £ данного экземпляра ПСП.
  • у и z — цепочки над алфавитом индексов I данного экземпляра.
  • # — символ, не принадлежащий ни X, ни /.
  • w*x^K.
  • уФг^я.
  • jc^r не совпадает с тем, что порождает цепочка индексов у в соответствии со списком В.

1. w не совпадает с тем, что порождает цепочка индексов z^R в соответствии со списком А.

Отметим, что L_AB состоит из всех цепочек, принадлежащих £*#£*#/*#/*, если только экземпляр (А, В) ПСП не имеет решения, но независимо от этого L_AB является КС-языком. Докажите, что Ь_АВ является КС-языком тогда и только тогда, когда решения нет. Указание. Как и в упражнении 9.5.2, используйте прием с обратным гомоморфизмом, а для того, чтобы добиться равенства длин тех или иных подцепочек, воспользуйтесь леммой Огдена, как в указа­нии к упражнению 7.2.5, б.

9.6. Резюме

Рекурсивные и рекурсивно-перечислимые языки. Языки, допускаемые машинами Тьюринга, называются рекурсивно-перечислимыми (РП), а РП-языки, допускае­мые МТ, которые всегда останавливаются, — рекурсивными.

Дополнения рекурсивных и РП-языков. Множество рекурсивных языков замкнуто относительно дополнения, и если язык и его дополнение являются РП, то оба они рекурсивны. Поэтому дополнение языка, являющегося РП, но не рекурсивным, не может быть РП.

Разрешимость и неразрешимость. «Разрешимость» есть синоним «рекурсив- ности», однако языки чаще называются «рекурсивными», а проблемы (которые представляют собой языки, интерпретируемые как вопросы) — «разрешимыми». Если язык не является рекурсивным, то проблема, которую выражает этот язык, называется «неразрешимой».

Язык Lj. В этот язык входит каждая цепочка в алфавите {0, 1}, которая, будучи проинтерпретированной как код МТ, не принадлежит языку этой МТ. Язык Ь_А яв­ляется хорошим примером не РП-языка, т.е. его не допускает ни одна машина Тьюринга.

Универсальный язык. Язык L_a состоит из цепочек, интерпретируемых как код МТ, к которому дописан ее вход. Цепочка принадлежит L_u, если эта МТ до­пускает данный вход. Язык L_u — это пример РП-языка, который не является рекурсивным.

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

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

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

9.7. Литература

Результат о неразрешимости универсального языка фактически взят из работы Тью­ринга [9], хотя там он выражен в терминах вычислений арифметических функций и ос­танова, а не в терминах языков и допустимости по заключительному состоянию. Теорема Райса взята из [8].

Неразрешимость проблемы соответствий Поста была доказана в [7], но приведенное здесь доказательство, не вошедшее в печатные работы, принадлежит Р. В. Флойду (R. W. Floyd). Неразрешимость ТАГ-систем Поста (определенных в упражнении 9.4.4) доказывается в [6].

Основополагающими работами о неразрешимости вопросов, связанных с контекстно- свободными языками, являются [1] и [5]. Однако неразрешимость неоднозначных КС- грамматик была установлена независимо друг от друга Кантором [2], Флойдом [4], Хом- ским и Шютценберже [3].

• Bar-Hillel, М. Perles, and Е. Shamir, «On formal properties of simple phrase-structure grammars», Z. Phonetik. Sprachwiss. Kommunikations-forsch. 14 (1961), pp. 143-172.
• C. Cantor, «On the ambiguity problem in Backus systems», J. ACM 9:4 (1962), pp. 477-479.
• Chomsky and M. P. Schutzenberger, «The algebraic theory of context-free languages», Computer Programming and Formal Systems (1963), North Holland, Amsterdam, pp. 118-161. (Хомский H., Шютценберже M. Алгебраическая теория контекстно- свободных языков. — Кибернетический сборник, новая серия, вып. 3. — М.: Мир, 1966, С. 195-242.)
• W. Floyd, «On ambiguity in phrase structure languages», Communications of the ACM 5:10(1962), pp. 526-534.
• Ginsburg and G. F. Rose, «Some recursively unsolvable problems in ALGOL-like lan­guages», J. ACM 10:1 (1963), pp. 29-47.
• L. Minsky, «Recursive unsolvability of Post’s problem of ‘tag’ and other topics in the theory of Turing machines», Annals of Mathematics 74:3 (1961), pp. 437-455.
• Post, «A variant of a recursively unsolvable problem», Bulletin of the AMS 52 (1946), pp. 264-268.
• G. Rice, «Classes of recursively enumerable sets and their decision problems», Trans­actions of the AMS 89 (1953), pp. 25-59.
• M. Turing, «On computable numbers with an application to the Entscheidungsprob- lem», Proc. London Math. Society 2:42 (1936), pp. 230-265.

^[1] Заметим, что в действительности эта таблица выглядит совсем не так, как на рисунке. Ее верхние строки должны быть заполнены нулями, поскольку все небольшие целые числа не могут быть правильными кодами МТ.

^[2] По существу, их всего три. — Прим. ред.