Рекурсивно перечислимые и рекурсивные множества

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

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

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

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

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

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

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

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

Доказательство:

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

(2)-(3). Пусть М1 - машина, вычисляющая функцию f, для которой является областью определения. Построим машину М2, перечисляющую . Обозначим М1ts - высказывание «М1 останавливается за s шагов, начиная работу с t из множества {0,...,s}». Схема 1.

(3)-(4). Пусть , , М2 - машина, перечисляющая . Построим машину М3, вычисляющую всюду определенную функцию g с областью значений . Обозначим М2s - высказывание «М2 выдает результат на шаге s». Схема 2.

(4)-(1). Нигде не определенная функция является частично рекурсивной, поэтому для утверждение доказано. Пусть и М3 - машина, вычисляющая некоторую рекурсивную функцию g, для которой является областью значений. Обозначим М3km - высказывание «М3 выдает m, начиная работать с k». Схема 3.

Теорема доказана.

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