Разрешимы и неразрешимые множества. График вычислимой функции

Пусть А – подмножество множества натуральных чисел. Характеристической функцией множества А называется функция определяемая условиями

Определение: Множество А называется разрешимым, если его характеристическая функция Х_А вычислима.

Теорема 1. Если А и В – разрешимые множества, то множества разрешимы.

Полухарактеристическая функция множества А:

, такая что

Определение: множество А называется полуразрешимым, если его полухарактеристическая функция вычислима.

Теорема 2. Всякое разрешимое множество полуразрешимо.

Теорема 3. (теорема Поста). Множество разрешимо тогда и только тогда, когда оба множества А и N\A полуразрешимы.

Определение: Множество называется перечислимым, если или А является множеством значений некоторой вычислимой функции.

Теорема 4. Всякое перечислимое множество полуразрешимо.

Теорема 5. (теорема о графике). Частичная функция f из А в В вычислима тогда и только тогда, когда ее график Г_f перечислим.

Формальная теория вычислимости. Исходные функции. Частично рекурсивные функции. Рекурсивные предикаты

Простейшие функции:

Основные вычислительные операторы: оператор суперпозиции частичных функций, оператор примитивной рекурсии.

Примитивно рекурсивные функции. Примеры примитивно рекурсивных функций.

Оператор минимизации. Частично рекурсивные функции. Общерекурсивные функции.

Рекурсивные предикаты. Пусть Р – n- местный предикат на множестве натуральных чисел N. Функция называется характеристической для предиката Р, если эта функция удовлетворяет условиям