Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 43
Текст из файла (страница 43)
В частности, поскольку язык множеств является универсальным языком математики и всякому утверждению можно придать вид утверждения о множествах, язык разрешимых и перечислимых множеств является универсальным языком для утверждений о существовании (или отсутствии) алгоритмов решения математических проблем. Например, теорема 5.4 утверждает, что множество пар (х, у), таких, что алгоритм А„при данных у дает результат, неразрешимо, а теорема 5.12 — что неразрешимо множество всех общерекурснвных функций.
Итак, эффективно заданное множество — это множест-' во, обладающее разрешающей или перечисляющей функцией. Однако возникает вопрос, равносильны ли эти два типа задания. В одну сторону ответ почти очевиден. Теорема 5.14. Если непустое множество М разрешимо, то оно перечислимо. Для определенности будем считать, что М вЂ” это подмножество слов в алфавите А.
Пусть аь ам. „а ... — перечисление всех слов в алфавите А (например, в лексико-графическом порядке), 5 — некоторое слово из М. Перечисляющую функцию фм(а) для М определим так: ч р (О) = (1; ~рм(п), если сс„+, фМ; ч~м(п+ 1) = а„+и если а„+, 1=-М. Ясно, что фм(л) вычислима и всюду определена. П Обращение теоремы 5.14 неверно. Теорема 5.15. Существует множество М, которое перечислимо, но неразрешимо. Докажем, что таковым является множество М (х(А„(х) определен), т. е.
множество номеров самоприменимых алгоритмов. Из теоремы 5.9 следует, что М неразрешимо. Построим перечисляющую функцию фи для М. Будем считать для определенности, что алгоритмы — это г з „ч аз машины Тьюринга. Введем предикат Я (х, т) — истинный, если машина с номером х при данных х останавливается через т шагов.'Очевидно, что этот предикат вычислим и всюду определен( для его вычисления 3( (од) з( (о 21 з( (о,о) 3( ((,о) Я (2,0) 210 надо запустить машину Т„при данных х и дать ей проработать гп шагов. Предикат 31(х, гп) можно представить в виде бесконечной квадратной матрицы (табл. 5.3), строки которой соответствуют первому аргументу х, столбцы — второму аргументу гп, а в клетке (1, 1), т.
е. на пересечении 1-й строки и 1'-го столбца, стоит значение 5((1, 1). Упорядочим теперь клетки этой матрицы подобно тому, как упорядочивалось множество пар натуральных чисел в гл. 1 при доказательстве его счетности: (О, 0), (О, 1), (1, 0), (О, 2), (1, 1), (2, 0), (О, 3) ..., т. е. сначала клетки с суммой координат О, затем клетки с суммой 1 и т.
д. Тогда каждая клетка получит номер, соответствующий ее порядку в этой последовательности. Выберем какую-нибудь заведомо самоприменимую машину Тьюринга (например, любую всюду определенную машину из примеров $ 5.2), вычислим ее номер во введенной нумерации и обозначим его с. Определим теперь алгоритм вычисления функции фм(и): находим клетку (й 1) с номером и; если Ы(й 1) =И, то фм(и) = =1; если 5((1, 1) =Л, то фм(а) с.
Так как 1рм(п) =Š— это номер машины Т» останавливающейся при данных 1 через 1 шагов, то область значений фм содержит только номера самоприменимых машин. С другой стороны, всякая само- применимая машина Т, остановится через конечное число и шагов; но тогда фм(п') =х, где и' — это номер клетки ,(х, й). Таким обРазом, область значений фв совпадает с множеством номеров самоприменимых алгоритмов; кроме того, ввиду общерекурсивностн преднката 5! функция фм также общерекурснвна. Следовательно, она является перечисляющей функцией для М. П Согласно теореме 5.15 перечислимость — более слабый вид эффективности; хотя перечисляющая процедура и задает эффективно список элементов множества М, однако поиск данного элемента а в этом списке (всегда бесконечном, но, может быть, с повторяющимися элементами) может оказаться неэффективным: это неопределенно долгий процесс, который в конечном счете остановится, если а«=М, но не остановится, если афМ.
Поэтому список элементов М, заданный перечисляющей функцией, сам по себе не гарантирует разрешающей процедуры для М; теорема 5.15 дает пример, когда ее просто не существуе~. Впрочем, в одном важном случае перечпслимость гарантирует разрешимость. Теорема 5.16. М разрешимо, если и только М и М перечислимы. Действительно, если М разрешимо, то М также разре шимо: ф — 1 — Хм, но тогда перечислимость М и М следует из теоремы 5.!4. Пусть теперь М и М перечислимы с функциями ф и р— соответственно. Но тогда для любого элемента а его поиск в обоих списках, точнее, в объединенном списке фм(0), ф — (О), фм(1), ~>„—, (1) ...
обязательно увенчается успехом, так как либо аенМ, либо а«аМ. Такой поиск и есть разрешающая процедура для М, С) Сопоставление теорем 5.15 и 5.16 показывает, что допол. пение к перечислимому множеству может оказаться пепе речислимым; в частности, множество несамоприменимых алгоритмов неперечислимо. Такая «несимметрия» самопркменимости и несамоприменимости объясняется отмеченной ранее несимметрией положительного и отрицательного ответа при поиске заданного элемента в бесконечном списке: если А, самопрпменим, то, вычисляя А,(х), мы это когданибудь узнаем; если же А, несамоприменим, то об этом нельзя узнать, вьшисляя А„(х). Теорема Райса.
Заключительный комментарий. Про сматривая накопленный запас алгоритмическн неразреши- мых проблем, нетрудно заметить, что почти все они так или иначе свнзаны с самопрнменимостью — довольно экзоти- ческой ситуацией, когда алгоритм работает с собственным описанием. Читатель, интересующийся прикладной теорией алгоритмов, может решить, что поскольку понятие самопри- менимостп далеко от алгоритмической практики, то нераз- решимость в этой практике также никогда не встретится. Такого читателя ждет горькое разочарование.
Теорема 5.17 (теорема Райса). Никакое нетривиальное свойство вычислимых функций не является алгоритмически разрешимым. Для доказательства эту теорему удобнее сформулиро- вать в менее эффектном, но более точном виде; пусть С— любой класс вычислимых функций одной переменной, не- тривиальный в том смысле, что имеются как функции, при- надлежащие С,так и функции, не принадлежащие С. Тогда не существует алгоритма, который бы по номеру х функции 1, определял бы, принадлежит 1, классу С или нет; иначе говоря, множество (х()„енС) неразрешимо.
Д о к а з а т е л ь с т в о. Предположим, что множество М=(х((,~С) разрешимо; тогда оно обладает характерис- тической функцией 11, если 1,. ь- С (т. е, х ~=-М); ~0, если („фС. Пусть нигде не определенная функция ~э~М. Выберем какую-нибудь конкретную вычислимую функцию 1,е-=М и определим функцию Г(х, у); 1~,(у), если ~„(х) определена; г (х, у) = [)„(у), если 1„(х) не определена. Функция г(х, д) вычнслима: для ее вычисления надо, вычислять 1„(х); если 1,(х) определена, то этот процесс когда-нибудь остановится и тогда надо перейти к вычисле- нию ),(у), если же 1 (х) не определена, то процесс не оста- новится, что равносильно вычислению нигде не определен- ной функции ~,(у). Если в г(х, у) зафиксировать х, то Р станет вычислимой функцией от одной переменной у.
Номер этой функции зависит от значения х, т. е. явлнется всюду определенной функцией д(х); нетрудно показать, что д(х)' вычислима. Итак, ~~,(у), если 1, (х) определена; (<.,ы =1. 1~,(у), если ~„(х) не определена. 212 С ледовательно, ~«<,>енМ, если и только если 1~(х) определена (так как ),енМ, а )ОфМ). Отсюда 1, если ~„(х) определена; Х„(а(х)) = О, если Г,(х) не определена, т.
е. построена разрешающая функция для проблемы само- применимости, что невозможно. Для случая, когда 1,~М, выбираем г,енМ; последующие рассуждения аналогичны, а разрешающая функция для проблемы самоприменимостн будет иметь вид 1 — 11м(й'(х) ) П Из теоремы Райса следует, что по номеру вычислимой функции нельзя узнать, является ли эта функция постоянной, периодической, ограниченной, содержит ли она среди своих значений данное число и т. д. Создается впечатление, что вообще ничего нельзя узнать и все на свете неразрешимо.
С другой стороны, не противоречит ли теореме Райса тоточевидный факт, что по номеру машины Т всегда можно узнать, например, содержит ли она больше десяти команд или нету Для того чтобы разобраться в смысле теоремы Райса, надо прежде всего вспомнить, что номер х функции 1 — это номер алгоритма А„вычисляющего 1; в свою очередь, по номеру алгоритма однозначно восстанавливаетсн его описание, и разным номерам соответствуют разные алгоритмы. Для функций это неверно: при хну 1, и1„могут быть одной и той же функцией (в ее классическом смысле — см.
гл. 1). В теореме Райса участвуют и алгоритмы, и функции, н их следует четко различать. Класс С вЂ” это класс (или свойство) функций; в то же время «1,» означает «функция, вычисляемая алгоритмом А,». Таким образом, смысл теоремы Райса о том, что по описанию алгоритма ничего нельзя узнать о свойствах функции, которую он вычисляет. В частности, оказывается неразрешимой проблема эквивалентности алгоритмов: по двум заданным алгоритмам нельзя узнать, вычисляют они одну и ту же функцию или нет. Количество же команд — это свойство не функции, а описания алгоритма; к теореме Райса оно отношения не имеет, Опытного программиста теорема Райса не должна удивлять: он знает, что по тексту сколько-нибудь сложной программы, не запуская ее в работу, трудно понять, что она делает (т.
е. какую функцию вычисляет), не имея гипотез о том, что она должна делать; если это понимание и прн- 213 ходит, то каждый раз по-своему; систематического метода здесь не существует. С другой стороны, в этом тексте можно обнаружить алгоритмическим путем так называемые синтаксические ошибки (что и делают компиляторы с алгоритмических языков), т. е. выявлять те или иные свойства описания алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
