Основные теоремы теории алгоритмов

Лекция 4

Вопросы и упражнения к Лекции 3

1.В каком случае считают, что алгоритм применим к данному объекту?

2. Что такое вычислимая последовательность?

3. Что такое разрешимое множество? Полуразрешимое множество?

4. Дать определение проекции множества?

5. Дать описание (не определение!!) понятия «вычислимая функция».

4.1. Алгоритм пошагового вычисления и его следствия

Пусть Á - некоторый алгоритм с исходными данными из множества «конструктивных» объектов Х в множество «конструктивных» объектов Y. Следующий алгоритм  информирует о работе Á по шагам: исходные данные  есть пары áx,nñ, хÎХ, nÎN

и алгоритм Â примененный к паре áx,nñ сообщает, закончится ли применение алгоритма Á к х за n шагов и если «да», то каков ответ применения (можно для Â среди значений ввести дополнительный символ, появление которого сигнализирует о том, что работа Á на х не закончена). Докажем теперь такие усиления Утверждений 3.3.3 и 3.3.4.

Утверждение 4.1.1. Следующие свойства подмножества А множества «конструктивных» объектов эквивалентны:

1) А есть область определения вычислимой функции (А – полуразрешимое множество);

2) А есть проекция разрешимого множества;

3) А=Æ или А есть множество значений вычислимой последовательности;

4) А есть множество значений вычислимой функции.

Доказательство. 1)Þ2) Если А=Domf и f: Х®Y – вычислимая функция, то А есть проекция разрешимого множества В={áx,nñ: xÎX, nÎN и алгоритм, вычисляющий f, применяется к х не более чем за n шагов}.

2)Þ3). Пусть множество ВÍХ´Y – разрешимо и А=прВ. По очереди перебираем все элементы множества «конструктивных» объектов Х´Y и если n-ый элемент áx_n,y_nñ попал в множество В, то пусть f(n)=x_n; в противном случае, т.к. А не пусто, то пусть f(n) равно какому-нибудь фиксированному элементу из А. Тогда последовательность значений функции f будет перечислять элементы множества А (дайте более формальное доказательство).

3)Þ4). В случае пустоты А оно есть множество значений нигде не определенной функции. Если же А есть множество значений вычислимой последовательности, то соответствующая функция и есть требуемая вычислимая функция.

4)Þ1). Пусть f:Y®X – вычислимая функция со множеством значений А. Требуемая функция с областью определения, равной А, вычисляется алгоритмом: «перебирать все пары án,yñ, nÎN, yÎY и для каждой такой пары делать n шагов вычислений f(y); как только для хотя бы одной пары будет получен ответ f(y)=x, то в качестве результата выдать 0». Ясно, что если нужного y нет, то алгоритм не остановится, а если есть (f(y)=x), то алгоритм остановится на некотором шаге m. Утверждение 4.1.1 доказано.

Напомним, что множество А называется счётным, если А=Æ или А есть множество значений некоторой последовательности.

Подмножество А множества «конструктивных» объектов назовем перечислимым, если А=Æ или А есть множество значений некоторой вычислимой последовательности. Ясно, что понятие перечислимого множества есть вычислимый аналог счётного множества. Утверждение 4.1.1 говорит, что множество перечислимо тогда и только тогда, когда оно полуразрешимо.

Утверждение 4.1.2. Пусть AÍX, BÍX – перечислимые множества. Тогда AÈB и AÇB – перечислимые множества. Если CÍX´Y перечислимое множество, то прС также перечислимое множество.

Доказательство Утверждения 4.1.2. Если А пусто или В пусто, то доказывать нечего. В противном случае, по Утверждению 4.1.1, А и В есть множества значений вычислимых функций f и g. Но тогда AÈB есть множество значений последовательности h, которая определяется так: h(2k)=f(k), h(2k+1)=g(k) (опишите работу требуемого алгоритма!).

Докажем перечислимость прС (перечислимость же множества AÇB также докажите сами в качестве упражнения). Пусть f:Z®X´Y и пусть g:X´Y®X. Полагаем h=g(f(z)). Функция h вычислима как композиция вычислимых функций (опишите соответствующий алгоритм). Очевидно, что функция h перечисляет множество прС. Утверждение 4.1.2 доказано.

Утверждение 4.1.3 (Теорема Поста). Подмножество А множества «конструктивных» объектов Х разрешимо тогда и только тогда, когда А и его дополнение Х\А перечислимы.

Доказательство. Если А разрешимо, то Х\А – разрешимо и оба множества перечислимы. Далее, если одно из множеств А или Х\А пусто, то все очевидно. Иначе требуемый алгоритм таков: «для исходного х перебираем натуральные числа до тех пор, пока не будет f(n)=х или g(n)=х (здесь f и g - вычислимые функции, перечисляющие А и Х\А соответственно); для первого такого n, если f(n)=х, то хÎА, если g(n)=х, то хÎ(Х\А)». Т.к. одновременное выполнение обеих равенств невозможно (почему?), то требуемый алгоритм описан и разрешимость А доказана.

Из теоремы Поста следует, что неразрешимое множество обязательно имеет неразрешимое дополнение.

Утверждение 4.1.4 (теорема о графике) Функция f:X®Y вычислима тогда и только тогда, когда её график {áx,yñ:y=f(x)} является перечислимым множеством.

Доказательство. Если f – вычислимая функция с непустым графиком (иначе теорема тривиальна), то её область определения (по Утверждению 4.1.1, пункт 1)) есть {g(0), g(1), …}, где g – вычислимая функция. Тогда график f перечислим как множество значений вычислимой функции h(n)=ág(n),f(n)ñ. Обратно. Если график функции f перечислим и не является пустым множеством, то график есть область значений для некоторой, всюду определенной на N, функции g:N®X´Y. Тогда исходная функция f вычислима таким алгоритмом: «для исходного данного х перебирать все натуральные числа, пока не найдётся n такое, что g(n)=áх,yñ; если нашлось, то взять первое такое n и в качестве результата выдать то y, что g(n)=áx,yñ». Заметим, что если f(х) не определено, то алгоритм работу не заканчивает. Утверждение 4.1.4 доказано.

4.2. Универсальная вычислимая функция

Пусть Х и Y – множества «конструктивных» объектов. Рассмотрим все алгоритмы, исходными данными которых являются элементы Х, а значения принадлежат Y. Через Выч(Х,Y) обозначим множество всех вычислимых функций из Х в Y. Также, пусть Р – третье множество «конструктивных» объектов.

Определение. Функция F: P´X®Y называется универсальной для класса функций Выч(X,Y), если для всякой функции f из этого класса найдётся такое р из Р, что ("xÎX)(F(p,x) @ f(x)). Совершенно очевидно, что для класса Выч (X,Y) cуществует универсальная функция, т.к. данный класс счётен и если f₀, f₁, …f_n,.. – пересчет этого класса, то пусть Р=N и полагаем F(n,x) @ f_n(x) для всех nÎN, xÎX. Для приведённой универсальной функции полагаем: F_p(x) @ F(p,x) для всех х из Х.

Утверждение 4.2.1. Для любых множеств «конструктивных» объектов Х и Y существует множество «конструктивных» объектов Р и вычислимая функция F: P´X®Y, которая является универсальной для класса Выч (Х,Y).

Доказательство. Для доказательства Утверждения 4.2.1 мы постулируем существование алгоритмического языка, на котором можно записать программу любого алгоритма с множеством исходных данных Х и результатов применения из Y. Эти программы есть элементы какого-то множества «конструктивных» объектов Р. Теперь зададим функцию F: F(p,x)=y Û «p является синтаксически правильной программой, дающей на входе х результат y». Функция F является вычислимой (алгоритм, вычисляющий F, называется интерпретатором введённого языка программирования) и универсальна, т.к. если функция fÎВыч(Х,Y) и вычисляется алгоритмом Á и если р – программа для Á, тогда для некоторого р ("хÎX) (f(х) @ F(p,x)). Утверждение 4.2.1 доказано.

Замечание. Если F_p= f, то соответствующих f программ р может быть много.

Если в Утверждении 4.2.1 в качестве Р взять множество натуральных чисел N, то получим такое

Следствие 4.2.2. Для любых множеств «конструктивных» объектов Х и Y существует вычислимая функция H: N´X®Y, универсальная для класса Выч(Х,Y).

Действительно, по Утверждению 4.2.1 есть множество Р и универсальная функция F. Если h – вычислимая биекция из N в P, то пусть h(n)=p_n. Положим H(n,x)@F(p_n,x). Ясно, что H:N´X®Y – вычислимая функция и является универсальной для класса Выч (Х,Y).

Замечание. Если H:N´X®Y универсальная функция и fÎВыч(Х,Y), то программу вычисления f относительно H называют номером f относительно H, а отображение n®H_n (последняя функция получается из H фиксацией первого аргумента) – нумерацией вычислимых функций, соответствующей универсальной функции H.

Пусть теперь H:N´N®N есть универсальная вычислимая функция для класса Выч(N,N). Пусть функция f определена так: f(n)@H(n,n)+1. Но таким образом мы все же не пришли к противоречию (какому?), т.к. значение H(s,s) м.б. не определено (здесь s есть номер функции f выше относительно нумерации n®H_n).

Предположим теперь, что f^ - всюду определенное продолжение функции f (т.е. f^ всюду определена и там, где определена f, имеем f(x)=f^(x). Сама f определена так: f(n)@H(n,n)+1, где H – универсальная функция для класса Выч((N,N)). Теперь уже не верно, что f(n)@H_n(n), т.к. левая часть равенства определена, а правая – нет. Если же правая часть определена, то и f(n) определено и равно H_n(n)+1 и f^(n) совпадает с f(n) и не равно H_n(n). Тогда f^ отлична от всех функций H_n и поэтому не является вычислимой функцией. Следовательно, доказано

Утверждение 4.2.3. Существует вычислимая функция f: N®N, не имеющая всюду определенного, вычислимого продолжения.

Утверждение 4.2.4. Существует перечислимое и неразрешимое множество.

Доказательство. Если множество А есть область определения функции f из Утверждения 4.2.3, то А – перечислимое множество. Если бы А было разрешимым множеством, то легко бы было построить всюду определенное вычислимое продолжение уже упомянутой выше функции f (постройте это продолжение самостоятельно).

4.3. Тезис Черча

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

Тезис Черча. Всякая вычислимая (неформально) функция является формально вычислимой (в данной предложенной формализации).

Дата добавления: 2014-01-06