- •Исчисления высказываний
- •Определение формального исчисления
- •Исчисление высказываний генценовского типа
- •Эквивалентность формул
- •Нормальные формы
- •Семантика исчисления секвенций
- •Исчисление высказываний гильбертовского типа
- •Алгоритмы проверки общезначимости и противоречивости в ив
- •Логика и исчисления предикатов
- •Алгебраические системы. Формулы сигнатуры σ. Истинность формулы на алгебраической системе
- •Секвенциальное исчисление предикатов
- •Эквивалентность формул в
- •Нормальные формы
- •Теорема о существовании модели
- •Исчисление предикатов гильбертовского типа
- •Скулемизация алгебраических систем
- •Метод резолюций в исчислении предикатов
- •Некоторые проблемы аксиоматического исчисления предикатов
- •Разрешимость
- •Непротиворечивость и независимость
- •Полнота в узком смысле
- •Полнота в широком смысле
- •Элементы теории алгоритмов
- •Машины Тьюринга
- •Функции, вычислимые на машинах Тьюринга.
- •Рекурсивные функции и отношения
- •Примитивно рекурсивные функции.
- •Примитивно рекурсивные отношения.
- •Частично рекурсивные функции.
- •Рекурсивно перечислимые отношения
- •Неразрешимость исчисления предикатов. Теорема Геделя о неполноте. Разрешимые и неразрешимые теории.
Функции, вычислимые на машинах Тьюринга.
Для любого натурального числа обозначим через слово, состоящее из n + 1 числа единиц: 11... 1.
Функция , где ,, называется вычислимой на машине Тьюринга Tf = <A, Q, П, q0, q1>, если выполняются следующие условия:
из следует ;
из следует
т.е. начиная со слова машина Tf работает неограниченно долго, не приходя в заключительное состояние q0.
Таким образом, вычислимость функции f на машине Тьюринга Tf означает, что по любому набору из области определения (закодированному в виде наборов единиц длин n + 1, разделенных нулями) машина Tf выдает значение (закодированное в виде набора единиц длины ), а для любого набора машина Tf не завершает работу за конечное время.
Функция f называется правильно вычислимой на машине Тьюринга Tf = <A, Q, П, q0, q1>, если выполняются следующие условия:
из следует ;
из следует
т.е. начиная со слова машина Tf работает неограниченно долго, не приходя в заключительное состояние q0. и при этом не достраиваются ячейки слева.
Функция f называется правильно вычислимой (сокращенно ПВФ), если f правильно вычислима на некоторой машине Тьюринга.
Преимущество правильной вычислимости по сравнению с обычной вычислимостью на машинах Тьюринга состоит в том· что левее ячейки, напротив которой стоит головка в начальном состоянии, можно записывать информацию, которая не изменяется в процессе "правильного вычисления".
Пример 1. Нуль-функция 0-Функция о : N —> N, для которой о(х) =0, , правильно вычислима на машине ЛS.
Функция следования s : Ν —> Ν, для которой s(x) = х + 1, , правильно вычислима на машине S.
n-Местная функция проекции на т-ую координату , для которой правильно вычислима на композиции машин Тьюринга.
4. Функции + : Ν2 —> Ν, +(х, у) = х +y, и · : Ν2 —> Ν, , правильно вычислимы на машинах Сложение и Умножение соответственно.
Теорема 1. Если функции ,... и правильно вычислимы, то функция
правильно вычислима.
Рекурсивные функции и отношения
Примитивно рекурсивные функции.
Рассмотрим сначала всюду определенные числовые функции , т.е не нуль-местные операции на множестве Ν, и определим понятие примитивно рекурсивной функции (сокращенно ПРФ).
Функции о(х), s(x), , называются простейшими примитивно рекурсивными функциями.
Пусть f— m-местная операция, g1,...,gm - n-местные операции на множестве N. Оператор S, ставящий в соответствие операциям f и g1,...,gm n-местную операцию h, удовлетворяющую тождеству
называется оператором суперпозиции (подстановки). При этом всюду определенная функция
h = S(f, g1,...,gm)
является, очевидно, суперпозицией функций f и g1,...,gm.
Оператор примитивной рекурсии R каждой (п + 2)-местной операции f и n-местной операции g на множестве N ставит в соответствие (п + 1)-местную операцию
h=R(f,g)
удовлетворяющую следующей схеме примитивной рекурсии:
Для n = 0 схема примитивной рекурсии имеет следующий вид:
,
где a — постоянная одноместная функция, равная числу а.
Схема примитивной рекурсии образует некоторый индукционный процесс построения функции h, при котором на нулевом шаге используется функция g, а на каждом последующем шаге значение функции f от аргументов x1,... ,хm,, номера у предыдущего шага и значения функции h, вычисленного на предыдущем шаге.
Функция f называется примитивно рекурсивной, если существует последовательность функций f0, · · ·, fn ,в которой fn = f и всякая функция fi является простейшей ПРФ или получается из предыдущих функций с помощью оператора суперпозиции S или оператора примитивной рекурсии R.
Пример 1. Функция сложения χ + у примитивно рекурсивна в силу схемы примитивной рекурсии
2. Схема примитивной рекурсии
обосновывает примитивную рекурсивность функции умножения .
Доказательство примитивной рекурсивности следующих функций оставляется в качестве упражнения.
3. ху, где 00 = 1, — функция возведения в степень.
4. х!, где 0! = 1, — Х-факториал.
5.
знак числа х
6.
дополнение знака числа х
7. \х — у\ — модуль разности.
8. max(x, у) — максимум чисел x и у. \
9 min(x,y) — минимум чисел x и у.
10 [х/у], где [х/0] = x — частное от деления x на у.
11. rest(:r, у), где rest(x, 0) = x, — остаток от деления x на у.
Пусть f(x1,... ,xn,i) — (n + 1)-местная операция на множестве N. Определим операторы суммирования и произведения:
Предложение 1. Если f — примитивно рекурсивная функция, то функции g1,g2, примитивно рекурсивны