Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 87
Текст из файла (страница 87)
В дальнейшем г'-я цепочка обозначается через и;. 9.1.2. Коды машин Тьюринга Наша следующая цель — разработать для машин Тьюринга такой код, чтобы всякую МТ с входным алфавитом !О, 1) можно было рассматривать как двоичную цепочку. Мы только что показали, как перечислить двоичные цепочки. Поэтому у нас есть идентификация машин Тьюринга целыми числами, и можно говорить об "~'-ой машине Тьюринга М'*. Для того чтобы представить МТ М= Я, !О, 1), Г, В, пь В, Р) как двоичную цепочку, нужно приписать целые числа состояниям, ленточным символам и направлениям В и В. ° Будем предполагать, что состояниями являются 0ь 7з, ..., и, при некотором г.
Состояние г7, всегда будет начальным, а пз — единственным допускающим. Заметим, что поскольку можно считать, что МТ останавливается, попадая в допус- кающее состояние, то одного такого состояния всегда достаточно. ° Предположим, что ленточными символами являются Хь Хп ..., Х, при некотором з. Х, всегда будет символом О, Х вЂ” 1, а Хз — В, пробелом (пустым символом). Остальным же ленточным символам целые числа могут быть приписаны произвольным образом. ° Направление В обозначаешься как Вь а направление  — как В, Поскольку состояниям и ленточным символам любой МТ М можно приписать целые числа не единственным образом, то и кодировок МТ будет, как правило, более одной.
Но в дальнейшем это не будет играть роли, так как мы покажем, что МТ М с ЦМ) = 7а вообще непредставима никаким кодом. Установив, какие целые числа соответствуют каждому из состояний, символов и направлений, можно записать код функции переходов В.
Пусть фд„Х) = (ттмХь В„) есть одно из правил перехода, где 1, т', А, 1, т — некоторые целые числа. Это правило кодируется цепочкой 0'10'10" 10'10 . Заметим, что каждое из чисел 0 ) А, 0 лт не меньше единицы, так что в коде каждого отдельного перехода нет двух 1 подряд. Код МТ М состоит из кодов всех ее переходов, расположенных в некотором порядке и разделенных парами единиц; С ~ 1 1 Сг 1 1 ...
Сп-! 1 1 Сп где каждое С означает код одного перехода лт. Пример 9.1. Рассмотрим МТ М = (( уь г7„0з), 10, 1), 10, 1, В), 4 Вь В, ! 7з)), где функция д состоит из следующих правил. 9.1. НЕПЕРЕЧИСЛИМЫЙ ЯЗЫК 379 б(дь1) =(Оь О,Я) Ж9,, О) =(9ь1,1!) б(дз, 1) = (9ь О, Я) ~дз,в) =(9ь1,~) Переходы кодируются соответственно следующим образом. 0100100010100 00010!0100100 ООО!0010010100 ООО!00010001ООГО Первое правило, например, можно записать как б(до Хз) = (9ь Хь Вз), поскольку 1 =Хм 0 =-Х, и и = ьэз. Поэтому его кодом будет цепочка 0 1О 1О ! 0 10, как и записано выше.
! 2 Э ! Кодом всей М является следующая цепочка. 0100!ООО!0100!!ООО!0101001001ШОО!0010010!0011000!000100010010 Заметим, что существуют другие возможные коды машины М. В частности, коды четырех ее переходов можно переставить 4! способами, что дает 24 кода для М. П В разделе 9,2.3 нам понадобится кодировать пары вида (М, и), состоящие из МТ и цепочки. В качестве такого кода последовательно записываются код М, !!! и цепочка и.
Поскольку правильный код МТ не может содержать три единицы подряд, первое вхождение !1! гарантированно отделяет код М от и. Например, если М вЂ” это !ЫТ из примера 9.1, а н — цепочка 1011, то кодом (М, и) будет цепочка, представленная в конце примера 9.1, с дописанной к ней последовательностью 11!! О! 1. 9.1.3.
Язык диагонализации В разделе 9.1.2 были определены коды машин Тьюринга, и теперь у нас есть вполне конкретное понятие М„"Ьй машины Тьюринга*', Это МТ М, кодом которой является ня двоичная цепочка ио Многие целые числа вообще не соответствуют машинам Тьюринга. Например, 11001 не начинается с О, а цепочка 0010!! 10100! 0100 содержит три ! подряд. Если и', не является правильным кодом МТ, то будем считать, что М,— МТ, у которой одно состояние и нет переходов, т.е. М, для этих значений 1 есть МТ, которая сразу останавливается на любом входе.
Итак, если и, не является правильным кодом МТ, то ЦМ) есть Я. Теперь можно дать весьма существенное определение. ° Язык диагонпгизании (а — это множество всех цепочек и'„не принадлежащих ЦМ). Таким образом, 1, состоит из всех цепочек зг, каждая из которых не допускается соответствующей машиной Тьюринга с кодом и. Из рис. 9.1 видно, почему (., называется языком "диагонализации". Для всех ! и / эта таблица показывает, допускает ли МТ М входную цепочку и,; 1 означает "да, допуска- 880 ГЛАВА 9. НЕРАЗРЕШИМОСТЬ ст", а 0 — "нет, не допускает", Можно считаты-ю строку таблицы характеристическии вектором языка ЦМ); единицы в этой строке указывают на цепочки, которые принад- лежат данному языку.
г 3 Диагональ Рнс. 91 Хаблггяа, предстаелнюглан донуспгнмоспм веночек матннгенн Тьюрггггеа Числа на диагонали показывают, допускает ли Лг', цепочку и;. Чтобы построить язык 1е, нужно взять дополнение диагонали. Например, если бы таблица на рис. 9.1 была корректной, то дополнение диагонали имело бы начало 1, О, О, О, Таким образом, 1е должен был бы содержать и, = в и не содержать цепочки с и, по и,, т.е. О, 1 и 00 и т.д. Операция с дополнением диагонали для построения характеристического вектора языка, которому не может соответствовать никакая строка, называется диагоннлнзичией.
Она приводит к желаемому результату, поскольку дополнение диагонали само по себе являешься характеристическим вектором, описывающим принадлежность некоторому языку, а именно — л'е. Действительно, этот характеристический векзор отличается от каждой из строк таблицы на рис. 9.1 хотя бы в одном столбце. Поэтому дополнение диагонали не может быть характеристическим вектором никакой машины Тьюринга. 9.1.4.
Доказательсгво иеперечислимосги 1, Развивая наши рассуждения о характеристических векторах и див~опали, формально докажем основной результат, касающийся машин Тьюринга, — МТ, допускающей язык е'.е, не существует. Теорема 9.2. Язык 1е не является рекурсивно-перечислимым, т.с. не существует машины Тьюринга, которая попускала бы Се. Доказательство. Допустим, что )е = ЦМ) для некоторой МТ М. Так как 1е — язык иад алфавитом (О, 1), Лу должна содержаться в построенной нами последовательности машин Тьюринга, поскольку эта последовательность содержит все МТ с входным ал- ' Заметим, что в действительности зта таблица выглядит совсем нс так, как нл рисунке.
Ес всрхнис строки должны быть заполнены нулями, поскольку всс нсбольшис цслыс числа не могут быть правильными кодами МТ. 9.1. НЕПЕРЕЧИСЛИМЫИ ЯЗЫК 381 фавитом (О, 1). Слеловательно, в ней есть, по крайней мере, один код машины М, скажем, г', т.е. М= Мь Выясним теперь, принадлежит ли н, языку Е,. ° Если и;. принадлежит Т.ж то ЛХ допускает ип Но тогда (по определению Е,) и; не принадлежит Е,, так как (ч содержит лишь такие нл для которых Мз пе допускает и,.
° Точно так же, если и, не принадлежит Т,ж то М не допускает н,. Но тогда (по определению ба) н, принадлежит 1ч. 9.2.5. Чпражнения к разделу 9.1 9.1.1. Запишите следующие цепочки: а) (я) нз~', б) ж не. Запишите один из возможных кодов машины Тьюринга, изображенной на рис. 8.9. 9.1.2. 9.1.3. (1) Ниже приводятся определения двух языков, похожих на бж но все же отличных от него. Используя операции типа диагонализации, покажите, что каждый из них не может допускаться никакой машиной Тьюринга. Отметим, что при этом нужно использовать не диагональ, а какую-то другую бесконечную последовательность элементов матрицы, изображенной на рис. 9.1: а) (я) множество всех и;, для которых Мз, не допускает и„ б) множество всех и„для которых М не допускает ив, (!) Машины Тьюринга, рассмотренные до сих пор, имели входной алфавит (О, 1).
Допустим, мы хотели бы приписать целые числа всем машинам Тьюринга, независимо от их входного алфавита. Это, вообще говоря, невозможно. Ведь в то время, как имена состояний или рабочие символы на ленте (которые не являются входными), произвольны, каждый входной символ имеет значение. Например, языки (О"1" ! п> 1) и (а"Ь" ! п> 1) похожи, однако не совпадают и допускаются разными МТ. Допустим тем не менее, что у нас есть бесконечное множество символов (аь аз, ), пз которого выбираются все алфавиты МТ. Покажите, как можно приписать целые числа всем МТ, входной алфавит кото- 9.1.4. рых является конечным подмножеством этих символов. 9.2.
Неразрешимая РП-проблема Итак, мы убедились, что существует проблема (язык диагоназизации 1ч), которая не допускается никакой машиной Тьюринга. Наша следующая цель — уточнить структуру ре- 382 ГЛАВА 9. НЕРАЗРЕШИМОСТЬ Поскольку и, не может одновременно и принадлежать, и не принадлежать рь приходим к противоречию с нашим предположением о том, что М существует. Таким образом, 1., не является рекурсивно-перечислимым языком, ьЗ яурсивно-перечислимых языков (РП-языков), т.е. допустимых машинами Тьюринга, разбив ях на два класса. В первый класс войдут языки, которым соответствует то, что обычно понимается как алгоритм, т.е. МТ, которая не только распознает язык, но и сообшает, что входная цепочка не принадлежит этому языку.
Такая машина Тьюринга в конце концов всегда останавливается независимо от того, достигнуто ли допускающее состояние. Второй класс языков состоит из тех РП-языков, которые не допускаются никакой машиной Тьюринга, останавливающейся на всех входах. Зги языки допускакзтся несколько неудобным образом: если входная цепочка принадлежит языку, то мы в конце концов об этом узнаем, но если нет, то машина Тьюринга будет работать вечно. Поэтому никогда нельзя быть уверенным, что данная входная цепочка не будет когда-нибудь лопущена.
Примером языка данно~о типа, как будет показано ниже, является множество таких закодированных пар (М и), в которых МТ Мдопускает вход и. 9.2.1. Рекурсивные языки Язык 2, называется рекурсивным, если 2, = ЦМ) для некоторой машины Тьюринга М, удовлетворяющей следующим условиям. 1. Если и принадлежит 2„то М попадает в допускающее состояние (и, следовательно. останавливается).
2. Если н не принадлежит Е, то М в конце концов останавливается, хотя и нс попадает в допускающее состояние. МТ этого типа соответствуе~ интуитивному понятию "алгоритма" — правильно опреде- ленной последовательности шагов, которая всегда заканчивается и приводит к некоторому ответу. Если мы рассматриваем язык Е как "проблему", то проблема Е называется раэреигаиай, если она является рекурсивным языком. В противном случае проблема на- зывается неразрвизимой.
Существование алгоритма зачастую важнее, чем наличие некоторой МТ, решакзщсй данную проблему. Как упоминалось ранее, машины Тьюринга, которые могут не останавливаться, не дают информации. необходимой для утверждения, что цепочка нс принадлежит языку, т.е, они "не решают проблему". Таким образом, разделение проблем и языков на разрешимые (для них существует алгоритм решения) и неразрешимые часто важнее, чем разделение на рекурсивно перечнслимые (для них существует МТ какого- либо типа) и неперечислимые (для них вообще не существует МТ). На рис. 9.2 представ- лено соотношение трех классов языков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
