- •Введение
- •Программа курса математическая логика и терия алгоритмов
- •Логическое следствие в алгебре высказываний
- •2.1.3. Эквивалентные формулы алгебры высказываний
- •2.1.4. Дизъюнктивные и конъюнктивные нормальные формы в алгебре высказываний
- •2.1.5. Совершенные дизъюнктивные и конъюнктивные нормальные формы
- •Исчисление высказываний
- •Определение формального исчисления
- •Система аксиом и правил вывода
- •Теорема о дедукции в исчислении высказываний
- •Теорема о замене в исчисления высказываний
- •Свойства выводимых и эквивалентных формул исчисления высказываний
- •Основные эквивалентности исчисления высказываний
- •Полнота и непротиворечивость исчисления высказываний
- •Логика предикатов
- •Алгебраические системы
- •Пример 3. Построить подсистему алгебраической системы , порожденную множествомХ:
- •Формулы логики предикатов
- •Истинность формулы логики предикатов в алгебраической системе
- •2.3.4. Логическое следствие в логике предикатов
- •2.3.5. Эквивалентные формулы логики предикатов
- •2.3.6. Пренексная нормальная форма в логике предикатов
- •X(φ∧ψ)≡xφ∧ψ, X(φ∨ψ)≡xφ∨ψ,
- •X(φ∧ψ)≡xφ∧ψ, X(φ∨ψ)≡xφ∨ψ,
- •Xφ≡X(φ)xφ≡X(φ)
- •2.4. Исчисление предикатов
- •2.4.1. Система аксиом и правил вывода
- •2.4.2. Эквивалентные формулы исчисления предикатов
- •2.4.3. Теорема Геделя о полноте. Непротиворечивость исчисления предикатов
- •Элементы теории алгоритмов
- •2.5.1. Машины Тьюринга
- •2.5.2. Примитивно рекурсивные функции
- •2.5.3. Частично рекурсивные функции
- •Задания для домашних и контрольных работ
- •3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы
- •3.2. Логическое следствие в алгебре высказываний
- •Логическое следствие в логике предикатов
- •Частично рекурсивные функции
- •Список литературы
- •Основная литература
- •4.2. Дополнительная литература
- •Содержание
Элементы теории алгоритмов
2.5.1. Машины Тьюринга
Машина Тьюринга – это система, работающая в дискретные моменты времении состоящая из следующих частей:
конечная лента, разбитая на конечное число ячеек. В каждый момент временив ячейках записаны буквы из некоторого алфавита(где,), называемого внешним алфавитом машины. Ячейка, в которой записан символ, называетсяпустой. Если в какой–то момент времени лента имеетячеек, тосостояние ленты полностью описывается словом, где– состояние первой (слева) ячейки,– состояние второй ячейки и т.д.
Управляющая головка, представляющая собой устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится напротив определенной ячейки и имеет некоторое состояниеиз конечногомножества внутренних состояний,. Состояниеназываетсязаключительными означает завершение работы машины. Состояниеназываетсяначальными означает начало работы машины.
Программа Π, т.е. совокупность выражений(где), называемыхкомандами, каждое из которых имеет один из следующих видов:
сдвиг головки, находящейся в состоянии напротив ячейки с буквой, на одну ячейку влево с заменой состоянияна;
сдвиг головки, находящейся в состоянии напротив ячейки с буквой, на одну ячейку вправо с заменой состоянияна;
замена буквы в текущей ячейке на букву, а также замена состоянияголовки на состояние
Замечание 1. 1) Команды не могут начинаться со слов.
2) .
Таким образом, машина Тьюринга – это пятерка.
Машинным словомназывается слово, где– состояние ленты,– состояние головки, находящейся напротив ячейки с состоянием, занимающей то же положение среди других ячеек, что и буквав слове.
Пустое слово обозначим через .
Опишем преобразованиемашинного словав машинное словоза один шаг работы машины:
если , топриипри;
если , топриипри;
если , то.
Машинное словополучается из машинного словас помощью машины Тьринга, если существует последовательность преобразований,, для которой,.
Пусть – множество натуральных чисел с нулем,.
Отображение , где, называетсяn–местнойчастичной функцией. Если, то частичная функцияназываетсявсюду определенной.Если, то частичная функцияназываетсянигде не определенной.
Для любого числа черезобозначим слово, состоящее изчисла единиц:. Для любой–кисловоназывается записью этой–ки.
Частичная функция , где, называетсявычислимой по Тьюрингу, если существует машина Тьюрингатакая, что
1) ;
2) машина применима к записnиn-ки;
3) дляи.
Пример 1. Построим машину Тьюринга, вычисляющую функцию. Пусть, где,, программа Π состоит из команд:
2.5.2. Примитивно рекурсивные функции
Базисными функцияминазываются следующие функции:– нулевая функция;– функция следования;– функция выбора.
Оператор суперпозиции (подстановки)ставит в соответствиеm-местной частичной функциииn-местным частичным функциямn-местную частичную функцию, удовлетворяющую тождеству:
Оператор примитивной рекурсииставит в соответствиеn+2-местной частичной функциииn-местной частичной функцииn+1-местную частичную функцию, удовлетворяющую схеме примитивной рекурсии:
Частична функция называетсяпримитивно рекурсивной(ПРФ), если существует последовательность частичных функций, в которойи всякаяявляется либо базисной функцией, либо получается из предыдущих функций с помощью оператора суперпозицииили примитивной рекурсии.
Пример 2. Функция сложенияявляется ПРФ:
Пример 3. Функция умноженияявляется ПРФ: