- •Ф.К. Алиев, и.А. Юров
- •Введение
- •Основные способы задания двоичных функций
- •1.1. Табличный способ задания
- •1.2. Геометрический способ задания
- •1.3. Задание двоичных функций формулами
- •Основные способы задания двоичных функций (продолжение)
- •2.1. Нормальные формы двоичных функций
- •2.2. Многочлен Жегалкина и действительный многочлен двоичной функции
- •2.3. Теорема о разложении в ряд Фурье
- •Полнота и замкнутость. Критерий полноты системы. Функционально полные системы. Замкнутые классы булевых функций
- •3.1. Полнота и замкнутость. Функционально полные системы
- •3.2. Замкнутые классы булевых функций
- •3.3. Критерий полноты системы булевых функций
- •4.1. Псевдобулевы функции
- •4.2. Функции k-значной логики
- •5.1 Минимизация двоичных функции
- •5.2. Геометрическая интерпретация минимизации днф
- •6.1. Метод Квайна — Мак-Класки нахождения сокращённой днф двоичной функции
- •6.2. Метод нахождения тупиковых днф
- •6.3. Метод Петрика нахождения тупиковых днф
- •Алгебраические системы
- •7.1. Алгебраические системы. Булевы алгебры
- •7.2. Изоморфизм алгебраических систем
- •Алгебры высказываний. Предикаты и операции над ними
- •8.1. Основные логические операции и их свойства
- •8.2. Предикаты и операции над ними
- •Исчисление предикатов
- •9.1. Общее понятие о логическом исчислении
- •9.2. Формулы алгебры предикатов
- •9.3. Равносильность формул. Основные отношения равносильности
- •9.4. Использование равносильностей для упрощения формул
- •9.5. Построение исчисления предикатов
- •9.6. Выводимость и доказуемость формул
- •9.7. Семантика исчисления предикатов
- •Понятие о теории моделей
- •Элементы теории алгоритмов
- •11.1. Основные требования к алгоритмам
- •11.2. Машина Тьюринга и функции, вычислимые по Тьюрингу
- •11.3. Машины произвольного доступа и вычислимые функции
- •Частично рекурсивные функции и их вычислимость
- •Вычислимость суперпозиции
- •Вычислимость рекурсии
- •Вычислимость минимизации
- •Нумерация наборов чисел и слов
- •Нормальные алгоритмы
- •Нумерация алгоритмов
- •1. Нумерация машин Тьюринга
- •2. Нумерация мпд-программ
- •Универсальные функции
- •Алгоритмически неразрешимые проблемы
- •16.1. Алгоритмически неразрешимые проблемы
- •16.2. Примечательные алгоритмически неразрешимые проблемы
- •Характеристики сложности вычислений
- •Характеристика сложности вычислительных задач
- •18.1. Классы сложности p и np и их взаимосвязь
- •18.3. Основные np-полные задачи. Сильная np-полнота
- •Список Литературы
Универсальные функции
Пусть F — некоторый класс функций от k переменных. Функцию U(n, x1, …, xk) от k + 1 переменных называют универсальной для класса F, если выполнимы условия:
а) для всякого n N0 выполняется
fn(x1, …, xk) = U(n, x1, …, xk) F;
б) для всякой f(x1, …, xk) F существует n N0 такое, что f(x1, …, xk) = U(n, x1, …, xk).
Теорема 15.4. Для класса Ч1 — одноместных частично рекурсивных функций существует универсальная частично рекурсивная функция U(n, x).
Доказательство. Определим U(n, x) =, точнее
U(n, x) = (15.1)
Данное соотношение определяет частичную функцию. Функция U(n, x) является частично рекурсивной. Действительно, для произвольных (n, x) нужно найти программу Pn (эффективная процедура) и применить Pn к начальной конфигурации (x, 0, …, 0, …). Если Pn , то положить U(n, x) = r1, где r1 — содержимое регистра R1 в заключительной конфигурации. Если Pn , то считать значение U(n, x) неопределенным. По тезису Черча функция U(n, x) частично рекурсивна. Покажем, что функция U(n, x) универсальна. Поскольку U(n, x) частично рекурсивна, то и fn = U(n, x) для всякого n N0 частично рекурсивна, так как fn получена подстановкой константы вместо первого аргумента. Пусть теперь f(x) — произвольная одноместная частично рекурсивная функция. Тогда по доказанному она может быть вычислена некоторой МПД-программой Р. Пусть n = (P). Следовательно, f = и значит f = U(n, x), что и требовалось доказать.
Следствие 15.5. Для всякого k 1 существует частично рекурсивная функция Uk(n, x1, …, xk) универсальная для всех k-местных частично рекурсивных функций.
Это делается с использованием нумерационных функций. Полагаем
и так далее.
Покажем, например, что функция удовлетворяет нужным условиям. Во-первых, функцияU2 — частично рекурсивна, так как является суперпозицией частично рекурсивных функций. Во-вторых, функция частично рекурсивна, так как получается из частично рекурсивной подстановкой константы. Пусть теперьf(x1, x2) — произвольная частично рекурсивная функция. Образуем функцию g(x) = f(l(x), r(x)), где l, r — нумерационные функции. Так как g(x) — частично рекурсивна, то существует n такое, что g(x) = U(n, x). Теперь положим x = p(x1, x2), и тогда имеем
f(x1, x2) = g(p(x1, x2)) = U(n, p(x1, x2)) = ,
что и требовалось доказать.
Представляет интерес вопрос о существовании универсальной функции для других рассмотренных выше классов Ч0 и Чпр — общерекурсивных и примитивно рекурсивных функций соответственно.
Теорема 15.6. Не существует общерекурсивной функции Uk(n, x1, …, xk), универсальной для класса Чk0 — k-местных общерекурсивных функций при любом k 1.
Доказательство. Пусть, наоборот, существует такая функция Uk(n, x1, …, xk) для некоторого k. Образуем функцию f(x1, …, xk) = = Uk(x1, x1, …, xk) + 1. Согласно свойству универсальности существует n0 такое, что
Uk(n0, x1, …, xk) = f(x1, …, xk) = Uk(x1, x1, …, xk) + 1.
Поскольку данные функции всюду определены, то они определены и при x1, x1 = … = xk = n0. Тогда получаем противоречивое равенство Uk(n0, n0, …, n0) = Uk(n0, n0, …, n0) + 1. Значит, предположение о существовании универсальной функции ложно, что и требовалось доказать.
В то же время справедлива следующая теорема.
Теорема 15.7. Для каждого k N класс всех k-местных примитивно рекурсивных функций имеет общерекурсивную универсальную функцию.
Доказательство данной теоремы приведено в [11, § 5].
Заметим, что из данной теоремы следует, что класс общерекурсивных функций шире класса примитивно рекурсивных функций, так как универсальная функция не может быть примитивно рекурсивной и является общерекурсивной.
Дадим еще одно применение универсальной функции. Пусть f:N0 N0 — частичная функция. Функцию f0 будем называть доопределением f, если f0 всюду определена и совпадает с f в ее области определения. Покажем, что рассмотрение частичных вычислимых функций вызвано существом дела, а именно — существуют частичные вычислимые функции, любое доопределение которых делает их невычислимыми.
Теорема 15.8. Существует частично рекурсивная функция f(x), которая не может быть доопределена до общерекурсивной.
Доказательство. Рассмотрим функцию f(x) = , где U — универсальная функция. Данная фунция частично рекурсивна, так как она получается суперпозицией частично рекурсивных функций. Предположим, что существует общерекурсивная функция f0(x), которая является доопределением для f(x). По свойству универсальности U существует n такое, что f0(x) = U(n, x). Поскольку f0(x) всюду определена, то она определена при x = n, и тогда значение U(n, n) определено, и, следовательно, определено значение . Поскольку f0(x) есть доопределение f(x), то в области определения их значения должны совпадать. Поэтому имеем U(n, n) = f0(x). Однако последнее равенство дает противоречие, так как, если U(n, n) = 0, то , если U(n, n) 0, то . Значит, допущение о существовании рекурсивного доопределения для функции f(x) приводит к противоречию, что и требовалось доказать.
Л е к ц и я 16