- •Лекции по дискретной математике
- •Аннотация
- •Оглавление
- •Предисловие
- •Рекомендуемая литература
- •Начальные сведения
- •1. Множества
- •2. Отображения и соответствия
- •3. Отношения
- •4. Натуральные числа
- •1. Логика высказываний
- •1.1. Высказывания и операции над ними
- •1.2. Формулы логики высказываний
- •1.3. Равносильность формул
- •1.4. Принцип двойственности
- •1.5. Тождественно истинные формулы
- •1.6. Система натурального вывода
- •1.7. Принцип резолюций
- •2. Логика предикатов
- •2.1. Понятие предиката
- •2.2. Логические операции над предикатами
- •2.3. Кванторы
- •2.5. Выполнимые формулы и проблема разрешения
- •2.6. Логика предикатов и математическая практика
- •3. Формальные теории
- •3.1. Формализация в математике
- •3.2. Исчисление высказываний
- •3.3. Исчисление предикатов
- •4. Алгоритмы и вычислимость
- •4.1. Мощность множества
- •4.2. Счетные множества
- •4.3. Диагональный метод Кантора
- •4.4. Уточнение понятия алгоритма
- •4.5. Рекурсивные функции
- •4.6. Вычислимость и разрешимость
- •5. Булевы функции
- •5.1. Двоичные векторы
- •5.2. Понятие булевой функции
- •5.3. Булевы функции от одной и двух переменных
- •5.5. Полные системы булевых функций
- •6. Элементы теории кодирования
- •6.1. Двоичное кодирование
- •6.2. Векторное пространство {0,1}n
- •6.3. Отображения {0,1}n в {0,1}m
- •6.4. Блочные двоичные коды
- •6.5. Коды Хемминга
- •7. Функции выбора и их логическая форма
- •7.1. Понятие функции выбора
- •7.2. Примеры функций выбора
- •7.4. Логическое представление функций выбора
- •7.5. Основные свойства функций выбора
134
4.6. Вычислимость и разрешимость
Можно показать, подобно тому, как это делалось в п. 4.4, что традиционно считающиеся вычислимыми функции имеют рекурсивные описания и, значит, частично рекурсивны. Обычно используемые вычислительные схемы также реализуются с помощью простейших функций и элементарных операций. Все это и ряд других соображений приводит к следующей формулировке.
Тезис Черча. Числовая функция тогда и только тогда алгоритмически вычислима, когда она частично рекурсивна.
Построим пример невычислимой функции. Начнем с некоторых общих определений и замечаний.
Подмножество множества натуральных чисел M N называется разрешимым, если его характеристическая функция
χM(x)=1 при x M, χM(x)=0 при x M
рекурсивна. Содержательно разрешимость множества M означает, что существует алгоритм, позволяющий по любому числу x определить за конечное число шагов, принадлежит это число множеству M или нет.
Подмножество множества натуральных чисел M N называется перечислимым, если оно является областью значений некоторой общерекурсивной функции f. Перечислимость множества M означает, что его элементы могут быть последовательно выписаны (возможно с повторениям) с помощью некоторой эффективной процедуры.
135
Всякое непустое разрешимое множество M является перечислимым.
Доказательство. Несложно определить перечисляющую функцию f. Пусть m – произвольный элемент множества M. Определяем по рекурсии:
f(0)=m; f(x+1)=χM(x)(x+1)+(1−χM(x+1))f(x),
то есть f(x+1)=x+1, если x+1 M, и f(x+1)=f(x), если x+1 M.
Обратное, вообще говоря, неверно. Не всякое перечислимое множество является разрешимым. Перечислимое множество разрешимо лишь в том случае, когда перечислимо также и его дополнение.
В конце п. 4.4 было показано, что частично рекурсивные функции можно эффективно перенумеровать, используя их рекурсивные описания. Некоторые номера соответствуют общерекурсивным функциям. Обозначим множество таких номеров через M и покажем, что множество M неперечислимо.
Теорема. Множество номеров общерекурсивных функций не перечислимо.
Доказательство. Предположим противное. Пусть ϕ(x) – общерекурсивная функция, множеством значений которой является M. Тогда последовательность ϕ(0), ϕ(1), ϕ(2),… содержит номера всех общерекурсивных функций, и только их. Следуя диагональному методу, определим функцию g(x) формулой
136
g(x)=fϕ(x)(x)+1.
Это определение дает алгоритм вычисления значений функции g(x). В соответствии с тезисом Черча, функция g(x) частично рекурсивна, и, значит, общерекурсивна, поскольку функция g(x) определена для любого x. Значит, функция g(x) должна получить свой номер при перечислении с помощью
ϕ(x). Пусть этот номер равен n, то есть g(x)=fϕ(n)(x). Но тогда g(n)=fϕ(n)(n)+1=g(n)+1, что невозможно.
Вообще неперечислимые и неразрешимые семейства функций – это не «экзотика», а, скорее, норма.
Приведем без доказательства следующую теорему.
Терема (Райс). Никакое нетривиальное семейство вычислимых функций не является алгоритмически разрешимым.
Иными словами, если C – некоторое семейство вычислимых функций такое, что есть функции, входящие в это семейство, а есть и не входящие в него, то множество номеров функций из C неразрешимо. Не существует алгоритма, который бы позволял по номеру функции сказать, входит она в C или нет.
Так, по номеру функции нельзя узнать, является ли она монотонной, периодической и т.п. Заметим, что, нумеруя частично рекурсивные функции, мы на самом деле нумеровали их рекурсивные описания, то есть вычисляющие их алгоритмы. Теорема Райса утверждает, что по номеру алгоритма нельзя
137
узнать, периодична ли, например, функция, вычисляемая в соответствии с этим алгоритмом.