Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 42

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 42)

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

Введем функцию В(х) =А,(х)+1. Так как А, общере- курсивна, то и В(х) общерекурсивна. Если ВеиХ„то В име- ет номер хв и, следовательно, В (х) = А„(х). (5. 15) Тогда вточкех=ха по определениюВ(ха) =А в(хв)+1, а в силу (5.15) В(ха) =А,а(хз). Получаем противоречие, откуда следует, что В не входит в перечисление, порождае- мое ~р. (:! Если же в перечислении допускаются частичные функ- ции, то определение В не приводит к противоречию, а озна- чает лишь, что в точке хз В не определена.

з теоремы 5.!1 следует весьма важный результат. Теорема 5.12. Проблема определения общерекурсивностн алгоритмов неразрешима; не существует алгоритма В(х), такого, что для любого алгоритма А~ 1, если А„всюду определен; В(х) = О, если А„не всюду определен. Пусть алгоритм В(х) существует; тогда он определяет общерекурсивную функцию Г(х). Определим функцию д(х) следующим образом: п(О) =рд(1(д) =11; д(х + !) = ру (у ) д(х) й 1(р) = Ц. Так как номеров всюду определенных функций( н, следовательно, точек у, в которых 1(у) 1) — бесконечное множество, то д(х) всюду определена. Очевидно, что функция д из списка Аа, А» А,...

всех алгоритмов отбирает вге всюду определенные алгоритмы, т. е. является перечислением множества всех общерекурсивнык функций. Из теоремы 5.11 следует, что такое перечисление невозмо'кно н, следовательно, алгоритма В(х), определенного в условии теоремы 5.12, не существует. П Теоремы 5А', 5.11 и 5.12 проливают свет на роль понятия частичной определенности в теории алгоритмов. Еще в 2 5.1 среди требований к алгоритмам говорилось о желательно- 1 20$ стя такого требования, как результативность алгоритма '. Первым ударом по этому требованию была неразрешимость проблемы остановки, означающая, что если алгоритм А может быть частичным, то по алгоритму А и данным х нельзя узнать, даст А результат на данных х или нет) Возникает естественное желание либо вообще убрать частичные алгоритмы из общей теории алгоритмов (скажем, не считать их алгоритмами), либо ввести стандартный метод доопределения частичных алгоритмов.

Однако ни первое, ни второе эффективными методами сделать нельзя. Первая идея не годится из-за теоремы 5.12 — нет эффективного способа распознавать частичные алгоритмы среди множества всех алгоритмов, н, следовательно, предлагаемый отбор невозможен. Что же касается второй идеи, то для нее имеется не менее убедительное опровержение. Теорема 5.13.

Существует такая частично-рекурсивная функция 1, что никакая общерекурсивная функция д не является ее доопределением. г Определим 1 следующим образом: А (х) + 1, если А„(х) определен; )(х) = д а не опред лена, если А„(х) не определен. Как и прежде, предполагается, что зафиксирована нумерация ~р и гр-г(А,) =х. Очевидно, что )(х) вычислима. Пусть теперь д — произвольная общерекурсивная функция и хи— ее номер: ~р-'(д) =хк. Так как д всюду определена, то п(х ) = =А„(хк) определена и, следовательно, 1(ха) =д(хи)+1. Таким образом, для любой общерекурсивной функции и ) чь в точке ха.

Е) ледовательно, существуют частичные алгоритмы, которые нельзя доопределять до всюду определенных алгоритмов. , Наконец, еще одна идея: построить язык, описывающий все всюду определенные алгоритмы и только'нх, — не может осуществитьсгр потому, что описания в этом языке можно упорядочить (например, лекснкографически), и, следовательно, наличие такого языка означало бы существование полного перечисления всех всюду определенных функций, что противоречит теореме 5.11. Таким образом, прн формулировке общего понятия ал- ' Отметим, нто существенность этого требования проявляется в понятии неразрешимости; неразрешимость проблемы истолковывается как отсутствие всюду определенного алгоритма, решающего эту проблему. горятма неизбежно возникает дилемма — либо определение алгоритма должно быть достаточно общим, чтобы в число объектов, удовлетворяющих этому определению, заведомо вошли все объекты, которые естественно считать алгоритмами, либо требование об обязательной результативности алгоритма сохраняется.

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

В этом жэ смысле используется термин «разрешимость» при введении одного из важнейших понятий теории алгоритмов — понятия разрешимого множества. Разрешимые н перечислнмые множества. Множество М называется разрешимым (или рекурсивным), если сушествует алгоритм Ам, который по любому объекту а дает ответ, принадлежит а множеству М нли нет. Алгоритм Ам называется разрешающим алгоритмом для М. Эквивалентное, но несколько более точное определение: множество М называется разрешимым, если оно обладает общерекурсивной характеристической функцрйй, т. е. вычислимой всюду определенной функцией тм, з"акой, что 11, если а ЯМ; Км(а) = ~ ' (10, если а ц~ М.

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

в. Множество квадратов натуральных чисел М(а(а=я') перечислимо (оно просто задано перечис- ляющей функцией а=х~) и разрешимо. В качестве разрешающей процедуры можно предложить, например, следующую'. данное число а сравниваем последовательно с О, 1', 2'... и т. д. до тех пор, пока не появится такое число и', что либо а и', либо а<в'. В первом случае аевМ, во втором а фМ. б.

Множество М„из гл. 1, т. е. множество всех троек цифр, встречающихся в десятичном разложении и, перечислимо. Перечисляющая процедура для него заключается в последовательном вычислении знаков разложения и (один из алгоритмов их вычисления известен всем еще из школьногр курса геометрии) и выписывании троек из получающейся последовательности; для определенной таким образом функции ~рл имеем'; ~)„=314, ф (1) =159,ф„(2) =265 и т, д.

Некоторые тройки могут повторяться, поэтому ф„= это пример функции, перечисляющей с повторениями. Неизвестно (по крайней мере, к моменту написания этой книги) никакого разрешающего алгоритма для Мк, несмотря на то, что очевидна конечность Мв1 С другой стороны, это вовсе ие означает, что М неразрешимо; оно может оказаться и разрешимым (например, через достаточно большое количество шагов перечисляющей процедуры окажется, что выписаны все возможные тройки от 000 до 999). в. Из индуктивных определений, как правило, нетрудно извлечь порождающую процедуру. Иногда она содержится в них явно, как, скажем, в определении (и+1)!=и!(и+1), задающем и перечисляющую функцию ф(п) =и1, и способ ее вычисления. Иногда, чтобы получить из такого опреде-.

ления порождающую функцию, нужно ввести дополнительные соглашения. Например, известное индуктивное определение АЛГОЛа «идентификатор — это либо буква, либо идентификатор, к которому справа приписана буква или . цифра» порождает все возможные в АЛГОЛе идентификаторы; однако для того, чтобы придать этому процессу порождения вид перечисляющей функции, нужно ввести порядок перечисления. Если в качестве такого порядка принять лексико-графический и договориться, что буквы в этом порядке предшествуют цифрам, то в алфавите из 26 латинских букв и 10 цифр ф(0) =а, ф(25) г, ф(51) =ах, ф(54) =а2 и т. д. С помощью аналогичных соглашений на основе индуктивного определения формулы (см., например, $3.1, 6.1) можно построить перечисляющие функции для разлйчных множеств формул. г.

Из предыдущего примера видно, что перечисляющая ЮЗ функция, определенная на натуральном ряду, устанавливает соответствие (не обязательно взаимно однозначное) между числами и элементами порождаемого множества. Например, идентификатору аг соответствует число 51. Функция ~р, нумерующая алгоритмы (т. е. нумерация на стр. 202), устанавливает соответствие между описаниями алгоритмов и числами, причем в нашем случае соответствие взаимно однозначное. Поэтому можно сказать, что нумерация ~р, определенная на стр. 202, является перечисляющей функцией без повторений для множества всех алгоритмовв.

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

Характеристики

Список файлов книги