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

Лекция 3

3.1 Вычислимые функции.

Введём некоторые понятия, причем эти понятия не определяем, т.к. считаем их интуитивно ясными: это понятия «алгоритм», «исходное данное» и ряд др. С каждым алгоритмом будем связывать множество возможных исходных данных. Если x - возможное исходное данное, то при применении алгоритма А к x возможны три исхода: применение А к x завершится за конечное число шагов и будет получен некоторый результат; применение А к x закончится, но безрезультатно; алгоритм А будет работать на x бесконечно, т.е. применение не закончится. В первом случае говорят, что А применим к x, в двух других случаях говорят, что А не применим к x. Приведём нужные примеры. Например, можно, начиная с 0, всё время прибавлять 1. Применение никогда не закончится. Или, начиная с 0, прибавить 5 раз по 1 и закончить вычисление. Применение состоялось. Или, начиная с 0, прибавить 0 и остановится – нет результата.

Множество тех исходных данных, к которым алгоритм применим, будем называть областью применения алгоритма.

Частичной функцией из множества X в множество Y назовем любое подмножество АÍX´Y такое, что если первые компоненты упорядоченных пар равны, то и их вторые компоненты равны (в частности, А м.б. пустым). Частичные функции назовём просто функциями, при этом такая функция м.б. и всюду определенной. Каждому алгоритму на множестве исходных данных Х м.б. сопоставлена естественным образом функция на Х так, что f(x) @ Á(x), где Á - алгоритм на множестве Х. При этом знак @ называется условным равенством, т.е. Á и f одновременно определены или неопределены и первом случае имеет место f(x)=Á(x).

Функция называется вычислимой, если существует вычисляющий ее алгоритм. Например, нигде не определенная функция вычислима.

Конечно, понятие алгоритма имеет смысл только в случае, если исходные данные и результат вычисления (обработки) исходных данных являются «конструктивными» объектами. Мы будем считать, что натуральные числа или конечные слова в алфавите (также конечном) суть «конструктивные» объекты и никаких дальнейших пояснений о «конструктивных» объектах не делаем.

Замечание. Не следует думать, что для доказательства вычислимости функции нужно предъявлять соответствующий алгоритм. Функция f, равная 1, если верна гипотеза Ферма и равная 0 в противном случае, вычислима, т.к. равна тождественно 1 или 0 (т.к. проблема Ферма уже решена, то можно вместо неё взять любую другую, нерешённую ещё, математическую проблему).

Функция вычислима, если существует алгоритм, ее вычисляющий.

Задачи:а) приведите примеры вычислимых функций; б) определим функцию так: f(n)=0, если в десятичное разложение числа p входит кортеж 012345678910…n и f(n)=1 в противном случае; является ли f вычислимой функцией?

Решения: а) например, вычисление целой части из корня квадратного – вычислимая функция (алгоритм таков: перебираем натуральные числа с 0, возводим в квадрат и находим ближайший меньший данного);

б) функция вычислима (постройте соответствующий алгоритм, который постепенно вычисляет десятичные знаки числа p).

Замечание. Если множество X бесконечно и множество Y не пусто, то найдётся невычислимая функция из X в Y (т.к. множество всех алгоритмов счётно, а множество всех функций (частичных!!) несчётно). Сколько элементов должно содержать множество Y, чтобы нашлась всюду определенная невычислимая функция из X в Y? Достаточно двух элементов.

3.2 Разрешимые множества.

Пусть Х и Y – множества «конструктивных» объектов. Подмножество А Í Х – назовём разрешимым, если найдется алгоритм, который по всякому хÎХ решает, хÎА или нет (другими словами, если характеристическая функция А (т.е. такая функция f(х), что f(х)=1, если хÎА и f(х)=0 иначе) является вычислимой).

Утверждение 3.2.1. Пересечение, объединение и дополнение разрешимых множеств разрешимо.

Задача. Докажите Утверждение 3.2.1. См. решение ниже.

Следствия Утверждения 3.2.1: множества нечетных чисел, простых чисел, кубов натуральных чисел разрешимы (докажите!).

Замечание. Если X - бесконечное множество, то существует неразрешимое подмножество Х (вспомнить, что множество вычислимых функций – счётно).

Доказательство 3.2.1. Если А и В – разрешимые множества, то есть алгоритмы для их характеристических функций. Запускаем работать оба алгоритма. Если оба алгоритма указывают на принадлежность элемента как к А, так и к В, то полагаем соответствующую функцию равной 1, а иначе – 0. Для объединения аналогично, но оба алгоритма должны быть равны 0 для случая непринадлежности элемента ни к А, ни к В. Для дополнения совсем просто.

3.3 Полуразрешимые множества

Назовём множество АÍХ полуразрешимым, если найдется алгоритм, который применим к элементам множества А и не работает на элементах из дополнения А, т.е. если А является областью определения какой-либо вычислимой функции.

Замечание. Для бесконечного Х не всякое его подмножество полуразрешимо, т.к. множество вычислимых функций счётно.

Утверждение 3.3.1. Всякое разрешимое множество полуразрешимо.

Задача. Докажите Утверждение 3.3.1. См. решение ниже.

Замечание. Несколько ниже мы докажем, что обращение Утверждения 3.3.1 невозможно, т.е. приведём пример или докажем существование полуразрешимого множества, не являющегося разрешимым.

Утверждение 3.3.2 Любое конечное АÍХ – разрешимо.

Задача. Докажите Утверждение 3.3.2. См. решение ниже.

Замечание. Мы считаем, что любое множество «конструктивных» объектов не более чем счётно, а также, что любое множество «конструктивных» объектов можно «перебрать», т.е. существует такая вычислимая функция, которая пересчитывает все объекты из Х без повторений. Мы также принимаем без доказательства тот факт, что если Х и Y – множества «конструктивных» объектов, то Х´Y - также множество «конструктивных» объектов.

Пусть АÍХ´Y. Проекцией А назовём множество прА={x: $yÎY(áx,yñÎA)}.

Утверждение 3.3.3 Проекция разрешимого множества является полуразрешимым множеством.

Доказательство. Укажем требуемый алгоритм: «перебираем элементы множества Y до тех пор, пока не найдется такой yÎY, что áx,yñÎA; если такой y найден, то выдать результатом 0».

Замечание. Если нужного y нет, то на таком х алгоритм работает бесконечно.

Всюду определенная функция f: N®X называется вычислимой последовательностью, если f – вычислимая функция.

Утверждение 3.3.4. Множество значений вычислимой последовательности является полуразрешимым множеством..

Доказательство. Укажем нужный алгоритм: «для исходного данного х перебирать все натуральные числа, пока не найдётся такое nÎN, что f(n)=x; при нахождении такого n выдать результатом 0».

Доказательства.

3.3.1. Если элемент принадлежит множеству А (разрешимому!), то полагаем функцию равной 1, а если нет, то бесконечно прибавляем к ней 1 (она не остановится и будет неприменима).

3.3.2. Конечное множество задаётся своим списком!

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