Рекурсивно перечислимые и рекурсивные множества. Функция называется частичной, если она не всюду определена

Лекция 11

Функция называется частичной, если она не всюду определена.

Всюду определенная функция тоже является частичной.

Частичная функция вычислима, если существует некоторый алгоритм, который ее вычисляет.

Частичная функция называется частично рекурсивной, если она вычислима некоторой машиной Тьюринга.

Функция называется рекурсивной, если она всюду определена и частично рекурсивна.

Тезис Черча .

Множество рекурсивно перечислимо, если частично рекурсивна его частичная характеристическая функция .

Множество рекурсивно, если рекурсивна его характеристическая функция

.

Теорема 1 (о рекурсивно перечислимых множествах).

Для любого множества следующие условия эквивалентны:

(1). - рекурсивно перечислимо.

(2). является областью определения для некоторой частично рекурсивной функции f.

(3). Существует машина, перечисляющая элементы множества .

(4). Либо пусто, либо является областью значений некоторой рекурсивной функции g.

Доказательство было проведено на прошлой лекции.

Дата добавления: 2013-12-13