Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
97
Добавлен:
09.02.2015
Размер:
68.57 Кб
Скачать

Лекция 8 Алгоритмическая разрешимость и неразрешимость Вычислимые функции, разрешимые и перечислимые множества

Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, её вычисляющий, то есть такой алгоритм А, что

  • если f(n) определено для некоторого натурального n, то алгоритм А останавливается на входе n и печатает f(n);

  • если f(n) не определено, то алгоритм А не останавливается на входе n.

Определение 8.1. Говорят, что алгоритм А вычисляет функцию f(x), если:

  1. существует взаимно однозначное соответствие между областью определения f(х) и областью применимости А;

  2. для любого х из области определения f верно: f(x)= А((x))

В этом случае функция f(x) называется вычислимой функцией.

Несколько замечаний по поводу этого определения.

  1. Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определённая функция вычислима (в качестве А надо взять программу, которая всегда зацикливается).

  2. Можно было бы изменить определение, сказав так: «если f(n) не определено, то либо алгоритм А не останавливается, либо останавливается, но ничего не печатает». На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).

  3. Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите {0,1}), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, «конструктивные объекты». Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа.

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

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

Определение 8.2. Множество натуральных чисел X называется разрешимым, если существует алгоритм, который по любому натуральному n определяет, принадлежит ли оно множеству X.

Определение 8.3. Говорят, что Алгоритм А разрешает множество М относительно множества Х, где МХ, если:

  1. Для любого х из множества М верно, что А(х) = “истина”;

  2. Для любого у из Х, но у не принадлежит М, А(у) =“ложь”.

В этом случае говорят, что множество М разрешимое.

Очевидно, пересечение, объединение и разность разрешимых множеств разрешимы. Любое конечное множество разрешимо.

Аналогично определяют разрешимость множеств пар натуральных чисел, множеств рациональных чисел и т. д.

Перечислимые множества

Определение 8.4. Множество натуральных чисел называется перечислимым, если оно перечисляется некоторым алгоритмом, то есть если существует алгоритм, который печатает (в произвольном порядке и с произвольными промежутками времени) все элементы этого множества и только их.

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

Существует много эквивалентных определений перечислимого множества. Вот некоторые из них:

Определение 8.5. Говорят, что алгоритм А перечисляет множество В если область применимости А есть множество натуральных чисел N, а совокупность результатов есть множество В.

В этом случае В называется перечислимым множеством. Другими словами, в перечислимом множестве все элементы занумерованы целыми числами. Любой элемент в перечислимом множестве может быть найден по его номеру.

Теорема 8.1.

  1. Множество перечислимо, если оно есть область определения вычислимой функции.

  2. Множество перечислимо, если оно есть область значений вычислимой функции.

Была сформулирована и доказана теорема о графике вычислимой функции.

Теорема 8.2. Функция F является вычислимой тогда и только тогда, когда её график является совокупностью точек x и F(x), образуют перечислимые множества.

Изучение свойств вычислимой функции, а стало быть, и алгоритма, показало, что:

  1. область применимости любого алгоритма – перечислимое множество;

  2. функция f(x) вычислима тогда и только тогда, когда перечислим ее график, т.е. множество {(x, f(x))} перечислимо;

  3. множество MX разрешимо относительно множества X, когда M и X\M перечислимы.

Следствие. Алгоритмы не могут работать на множестве вещественных чисел.

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

Самое важное различие между этими понятиями для нас состоит в том, что алгоритм определяет некоторый процесс, который мы называем вычислительным. Понятие функции не предполагает и не определяет никакого процесса. Функция представляется в виде «черного ящика», на вход которого подали аргументы и на выходе получили результат. Как этот результат был получен – умалчивается. Понятие алгоритма наоборот, прежде всего, сфокусировано на процессе вычисления результата.

Соседние файлы в папке Мат. логика все лекции