Пусть А – подмножество множества натуральных чисел. Характеристической функцией множества А называется функция определяемая условиями
Определение: Множество А называется разрешимым, если его характеристическая функция ХА вычислима.
Теорема 1. Если А и В – разрешимые множества, то множества разрешимы.
Полухарактеристическая функция множества А:
, такая что
Определение: множество А называется полуразрешимым, если его полухарактеристическая функция вычислима.
Теорема 2. Всякое разрешимое множество полуразрешимо.
Теорема 3. (теорема Поста). Множество разрешимо тогда и только тогда, когда оба множества А и N\A полуразрешимы.
Определение: Множество называется перечислимым, если или А является множеством значений некоторой вычислимой функции.
Теорема 4. Всякое перечислимое множество полуразрешимо.
Теорема 5. (теорема о графике). Частичная функция f из А в В вычислима тогда и только тогда, когда ее график Гf перечислим.
Формальная теория вычислимости. Исходные функции. Частично рекурсивные функции. Рекурсивные предикаты
|
|
Простейшие функции:
Основные вычислительные операторы: оператор суперпозиции частичных функций, оператор примитивной рекурсии.
Примитивно рекурсивные функции. Примеры примитивно рекурсивных функций.
Оператор минимизации. Частично рекурсивные функции. Общерекурсивные функции.
Рекурсивные предикаты. Пусть Р – n- местный предикат на множестве натуральных чисел N. Функция называется характеристической для предиката Р, если эта функция удовлетворяет условиям
Определение: Предикат Р называется рекурсивным (примитивно рекурсивным) если его характеристические функция общерекурсивна(примитивно рекурсивна).