- •Ф.К. Алиев, и.А. Юров
- •Введение
- •Основные способы задания двоичных функций
- •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-полнота
- •Список Литературы
Вычислимость суперпозиции
Теорема 12.3. Пусть функции ,, …,вычислимы на МПД. Тогда вычислима и функция.
Доказательство. Пусть — программы стандартного вида для вычисления функций,, …,соответственно. Напишем программуН для вычисления h. Положим . Запомнимв регистрах, в регистрахзапоминаем значения, …,соответственно. Указанные регистры не затрагиваются вычислениями по программам. Теперь дадим программуР вычисления h:
…
…
.
Ясно: вычисление останавливается тогда и только тогда, когда заканчиваются вычисления каждой,и вычисление, что и требовалось доказать.
Следствие 12.4. Пусть — вычислимая на МПД функция и— последовательностьn переменных из (возможно с повторениями). Тогда функциявычислима.
Доказательство. Если , то, и потому функцияh — вычислима, что и требовалось доказать.
Вычислимость рекурсии
Теорема 12.5. Пусть функции ,вычислимы на МПД. Тогда функциявычислима.
Доказательство. Пусть G и Н — программы стандартного вида для вычисления функций g и h. Построим программу F, вычисляющую функцию . По начальной конфигурациипо программеG вычисляется . Теперь, еслиy 0, то применяем (многократно) программу Н для нахождения ,, …,. Положим. Запоминаемв регистрах. Номер циклаk, где k = 0, 1, …, y помещаем в . Промежуточное значениепомещаем в. ПрограммаF для вычисления f (здесь t =m+n):
T(1, m + 1)
…
T(n + 1, m + n + 1)
G[1, 2, …, n à m + n + 3]
Iq: J(t + 2, t + 1, p)
H[m + 1, … m + n, t + 2, t + 3 à t + 3]
S(t + 2)
J(1, 1, q)
Ip: T(t + 3, 1)
Следовательно, функция f вычислима, что и требовалось доказать.
Вычислимость минимизации
Теорема 12.6. Пусть функция вычислима на МПД. Тогда вычислима и функция
.
Доказательство. Пусть G — программа стандартного вида, вычисляющая функцию g. Пусть . Построим программуF для вычисления функции f по следующему алгоритму: вычислять приy = 0, 1, 2, … до тех пор, пока не найдется y, такой, что , тогдаy будет требуемым выходом. Помещаем в регистры . Полагаем в началеy = 0. Промежуточное значение помещаем в . Программа для вычисленияf:
…
Ip:
Iq:
Следовательно, функция f вычислима, что и требовалось доказать.
Следствие 12.6. Частично рекурсивные функции вычислимы на МПД, т.е. Ч Е.
Покажем теперь частичную рекурсивность вычислимых функций.
Теорема 12.7. Всякая вычислимая на МПД функция является частично рекурсивной.
Доказательство. Пусть — вычислимая на МПД функция и пустьP = I1I2…Is — соответствующая программа. Будем называть шагом вычисления выполнение одной команды программы. Для произвольных иопределим следующие функции, связанные с вычислением:
Таким образом, ,. Очевидно, что функции,всюду определены. Найдем теперь выражение длячерез введенные функции. Если значениеопределено, тоостанавливается послеt0 шагов, где , поэтому. Если же значениене определено, тоне останавливается, и тогдадля любых, поэтомуне определено. Следовательно, во всех случаях.
Теперь, если убедиться, что функции ичастично рекурсивны, то таковой будет и функция. Ясно, что существует неформальный алгоритм вычисления значений функцийи. Для этого нужно по заданным,t написать последовательность конфигураций K0 K1 … Kt и выписать содержимое регистра R1 и номер выполняемой на шаге t + 1 команды. По тезису Черча функции ичастично рекурсивны и, значит, функцияявляется частично рекурсивной, что и требовалось доказать.
Замечание 12.8. Более точный анализ показывает, что функции иявляются примитивно-рекурсивными.
Следствие 12.9. Классы функций Ч и Е совпадают.
Рассмотрим теперь вопрос о соотношении введенных классов Чпр, Ч0 и Ч.
Поскольку класс Ч содержит частично определенные функции, то ясно, что Ч0 Ч. Кроме того, очевидно, что Чпр Ч0. Вопрос о том, является ли включение Чпр Ч0 собственным решается несколько сложнее.
Первый пример общерекурсивной функции, не являющейся примитивно рекурсивной, был дан Аккерманом (1928).
Функция Аккермана задается соотношениями:
;
;
.
Можно доказать, что данные соотношения однозначно определяют функцию . Результаты вычислений убеждают, что имеется алгоритм вычисления функции.
В то же время доказывается, что функция не является примитивно рекурсивной, так как растет быстрее, чем любая одноместная примитивно рекурсивная функция. Доказательство, ввиду его громоздкости, опускается1.
Л е к ц и я 13