2.5.3. Частично рекурсивные функции

Оператор минимизации ставит в соответствиеn+1-местной частичной функцииn-местную частичную функциютак, что

и

или определены и не равны 0,

а

В этом случае введем обозначение:

Частичная функция называетсячастично рекурсивной(ЧРФ), если существует последовательность частичных функций, в которойи всякаяявляется либо базисной функцией, либо получается из предыдущих функций с помощью оператора суперпозиции, примитивной рекурсииили минимизации.

Пример 4. Нигде не определенная функцияявляется ЧРФ:

.

Пример 5. Функция

является ЧРФ:

2. Содержание

   • Введение
   • Программа курса математическая логика и терия алгоритмов
   • Логическое следствие в алгебре высказываний
   • 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. Дополнительная литература
   • Содержание