Игошин Математическая логика и теория алгоритмов (1019110), страница 90

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

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

Это означает, что возможно развитие и изложение теории алгоритмов, инвариантное по отношению к способу формализации понятия «алгоритм». Это своего рода общая теория алгоритмов. Основные ее понятия — алгоритм и вычислимая функция. 361 При интерпретировании этой общей теории, например, в теории рекурсивных функций понятие алгоритм превращается в рекурсивное описание функции, понятие вычислимая функция— в понятие частично рекурсивная (или обшерекурсивная) функция. (При этом следует всегда помнить, что алгоритм и вычисляемая им функция — это не одно и то же. Одна и та же функция может вычисляться с помощью разных алгоритмов.) Будем рассматривать функции 3'от одного или нескольких аргументов, заданные на множестве АГ= (О, 1, 2, 3, 4, ..., и, ...) всех натуральных чисел или на некоторых его подмножествах (частичные функции) и принимающие значения в множестве Ф.

Таким образом, рассматриваются функции 3; являющиеся отображениями декартовой п-й степени АГ" в множество АГ. Область определения О3 функции 3'есть подмножество множества У" = АГх ... х АГ; О3 = ((хь ", х,):Лхь ..., х„) — определено). Область изменения (значений) 3 есть подмножество множества АГ: 1~'= (у а )ч': (Лхь ..., х„) (Яхн ..., х„) = у)).

Определение 35.1. Функция 3"(хн ..., х„) называется вычислимой, если существует алгоритм, позволяющий вычислять ее значения для тех наборов аргументов, для которых она определена, и работающий вечно, если функция для данного набора значений аргументов не определена. Пусть М ~ Ф" = АГ х ... х Ф. Определение 35.2. Множество М называется разрешимым, если существует алгоритм Аи, который по любому объекту а дает ответ, принадлежит а множеству Мили нет. Алгоритм Аи называется разрешающим алгоритмом для М. Известно понятие характеристической фупкции множества М.

Ею называется функция уи, заданная на множестве М, принимающая значения в двухэлементном множестве (О, Ц и определяемая следующим образом: )О,если(х„...,х„) е М; 1 1 если (х~ хд) е М Отсюда ясно, что множество М разрешимо тогда и только тогда, когда его характеристическая функция )„и вычислима. Примером разрешимого множества может служить множество всех тавтологий логики высказываний.

Разрешающий алгоритм состоит в прямом вычислении значений данной формулы на всевозможных наборах значений ее пропозициональных переменных (составление таблицы истинности формулы). Пусть теперь Ма )У. Определение 35.3. Множество М ~ )ч' называется (рекурсивна, или эффективно, или алгоритмически) перечислимым, если М либо пусто, либо есть область значений некоторой вычислимой функ- 362 ции или, другими словами, если существует алгоритм для последовательного порождения (перечисления) всех его элементов. Другими словами, М перечислимо, если существует такая вычислимая функция Чгм(х), что а а М е» (3х)(а = щ,(х)). Функция Чгм называется перечисляющей множество М (или для множества М); соответственно алгоритм, вычисляющий ум, называется перечисляющим или порождающим для М.

Пример 35.4. Рассмотрим множество М = (1, 4, 9, 16, 25, 36, ...) квадратов натуральных чисел. Оно перечислимо; для получения его элементов нужно последовательно брать числа 1, 2, 3, 4, ... и возводить их в квадрат. Другими словами, Месть область значений вычислимой функции 7(х) = хз: М = (1з, 2з, 3', 4з, ...). Более того, это множество является также и разрешимым: для проверки того, принадлежит или иет некоторое число данному множеству, нужно разложить число на простые множители, что позволит выяснить, является ли оно точным квадратом. Далее, в теореме 35.6 будет показано, что любое разрешимое множество перечислимо, а в теореме 35.7 — что обратное утверждение неверно.

Важность понятий разрешимости и перечислимости множеств для оснований математики связана с тем, что язык теории множеств является в известном смысле универсальным языком математики. Всякому математическому утверждению можно придать вид утверждения о каких-либо множествах. В связи с этим к способам задания множеств предъявляются повышенные требования. Необходимо точное понимание таких понятий, как «конструктивный способ задания множества» и «множество, заданное эффективно».

Это и достигается благодаря понятиям разрешимости и перечислимости множества. Язык разрешимых и перечислимых множеств является универсальным языком для'утверждений о существовании (или отсутствии) алгоритмов решения математических проблем. Теорема 35.5. Если множества М и Е перечислимы, то перечислимы множества М() Е и М П Е. Доказательство. Если имеются алгоритмы для порождения элементов множеств М и Е, то алгоритм для порождения множества М () Е получается из исходных путем их одновременного применения. Следовательно, множество М() Е перечислимо. Пусть теперь алгоритм йм последовательно порождает элементы т„тп ть ... множества М, а алгоритм йс последовательно порождает элементы (п !и 1„...

множества Е. Тогда алгоРитм для перечисления элементов множества М() Е заключается в следующем. Поочередно с помощью алгоритмов йм и йс порождаются элементы ть („тп 1п т,, )з и т.д. Каждый вновь порожденный 363 элемент т; сравнивается со всеми ранее порожденными элементами ~;, Если т; совпадает с одним из них, то он включается во множество М() Т,. В противном случае надо переходить к порождению элемента 1; и сравнивать его со всеми ранее порожденными элементами т,, и т.д. Описанная процедура позволяет эффективно перечислить все элементы множества М() ь', что и требовалось доказать. П Теорема 35.б. Пусть М ~ Ф. Множество М разрешимо тогда и только тогда, когда оно само и его дополнение М перечислимы.

До к аз а тел ь ство. Иеобходимость. Пусть М вЂ” разрешимое множество. Можем считать, что Ми И, т.е. имеется элемент а а М Тогда характеристическая функция ум множества М, как было отмечено выше, вычислима, т.е. имеется алгоритм для ее вычисления. Строим алгоритм для перечисления множества М. Рассмотрим функцию 1х, если ум(х) = 1, '1а, если)(м(х) = О. Отсюда М = ЯО), г(1), /"(2), г(3), ...), т.е. М есть множество значений функции Г, которая, очевидно, вычислима ввиду вычислимости функции ум(х). Следовательно, множество М перечислимо.

Аналогично, выбрав элемент Ь е М, строим функцию: е(х) =~ ' (Ь, если ум(х) = 1, ~х,если км(х) =О, которая также вычислима ввиду вычислимости функции ум(х). Кроме того, М = (е(0), «(О, е(2), е(3), ...), т.е. М есть множество значений вычислимой функции д. Следовательно, множество М также перечислимо. Достаточность. Пусть множества М и М перечислимы, т. е.

М = ( г(0), Д1), )"(2), ЯЗ), ...) и М = (е(0), е(1), е(2), е(3), ...), где ~и е — некоторые вычислимые функции. Тогда алгоритм, выясняющий, принадлежит или нет произвольное число и множеству М, действует следующим образом. Последовательно порождаем элементы )"(0), б(0)„Г(1), я(1), г(2), е(2), ... и на каждом шаге получаемый элемент сравниваем с п. Поскольку п должно принадлежать либо М, либо М, то на конечном шаге получим Як) = и или б()с) = п. Если г(lс) = и, то и е М, а если е(1с) = и, то и е М и, значит, и е М. Следовательно, множество М разрешимо. (3 Прежде чем переходить к следующей теореме, отметим, что существует эффективное перечисление всех упорядоченных пар натуральных чисел, которое называется диагональным методом, или диагональным процессом: 364 (О, 0) (1, 0) (2, 0) (3, 0) (4, 0) (О, 1)' (1, 1) (2, 1) (3, 1) (4, 1) (О, 4 (1, 2) (2, 2) (3, 2) (4, 2) у Перечисление осуществляется последовательным прохождением по диагоналям, начиная с левого верхнего угла.

Первыми парами этого перечисления являются: (О, 0), (О, 1), (1, 0), (О, 2), (1,!), (2, 0), (О, 3), ... Можно доказать, что в данной последовательности пара (т, и) стоит на месте с номером тз + 2ти+ и'+ Зт+ и+ 2 С(т, и)— 2 Теорема 35.7. Суа!ествует иеречислимое, но неразрешимое множество натуральных чисел. Д о к а з а т е л ь с т в о. На основании предыдущей теоремы достаточно привести пример такого множества Унатуральных чисел, которое само было бы перечислимо, а его дополнение Уперечислимым не было.

Ясно, что перечислимых множеств натуральных чисел (как и алгоритмов) имеется лишь счетное количество. Следовательно, все перечислимые множества можно расположить в последовательность (перенумеровать): Мь, Мн Мм ... Более того, можно считать, что эта нумерация эффективна, т.е. по номеру множества можно восстановить само это множество. (В начале з 36 будет показано, как можно эффективно перенумеровать все машины Тьюринга, рассматривая их затем как алгоритмы, вычисляющие функции, порождающие перечислимые множества.) Рассмотрим теперь алгоритм й, который последовательно порождает все элементы следующего множества У.

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

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