Теорема 2 (о рекурсивных множествах)

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

(1). - рекурсивное множество

(2). Существует алгоритм, распознающий в .

(3). Множество рекурсивно.

(4). Множества и - рекурсивно перечислимы.

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

(1)-(2). Характеристическая функция - рекурсивна, поэтому машина, вычисляющая ее, будет искомым алгоритмом.

(2)-(3). Ответ на вопрос о принадлежности числа к является и ответом на вопрос о принадлежности к . Это означает, что функция вычислима (а по тезису Черча и рекурсивна), а рекурсивное множество.

(3)-(4). Всякое рекурсивное множество является рекурсивно перечислимым. Из характеристической функции всегда можно получить частичную характеристическую функцию. Схема 4.

(4)-(1). По предыдущей теореме имеются две машины М1 и М2, перечисляющие и , соответственно. Функция, алгоритм которой показан на схеме 5, вычисляет является характеристической для .

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

Утверждение 1: Существует множество натуральных чисел, не являющееся рекурсивно перечислимым.

Доказательство: Множество всех множеств натуральных чисел несчетно. Множество всех машин Тьюринга счетное число.

Утверждение 2: Существует рекурсивно перечислимое множество, не являющееся рекурсивным.

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

Перенумеруем все машины Тьюринга, как некоторые слова в некотором алфавите. Можно построить алгоритм, который среди всех слов распознает слова, соответствующие какой-то машине Тьюринга. Следовательно, множество V номеров всех машин Тьюринга рекурсивно перечислимо. Пусть - машина, перечисляющая множество V.

Каждая машина Тьюринга задает некоторую одноместную функцию . - частично рекурсивна по определению. По теореме о рекурсивно перечислимых множествах , где Don f - область определения f, рекурсивно перечислимое множество и существует машина , его перечисляющая.

Обозначим .

Обозначим .

Тогда алгоритм (*) перечисляет множество W.

Итак, W - рекурсивно перечислимое множество. Допустим, что W - рекурсивно.

Тогда по пункту (4) теоремы 2 P-W - рекурсивно перечислимо.

По пункту (2) теоремы 1 существует частично рекурсивная f(x), что P-W=Don f(x).

f(x) вычисляется некоторой машиной Тьюринга M_k, следовательно f(x)=f_k(x).

Число k принадлежит Don f_k(x) = P-W тогда и только тогда, когда k принадлежит W. Противоречие.

Следовательно, допущение о рекурсивности W неверно.

(*) Доказательсьво перечислимости W

M – перечисляет машины Тьюринга,

то есть соответствующие функции.

f1(1) – на 1 шаг,

f1(1),f2(2) – на 2 шага,

f1(1),f2(2),f3(3) – на 3 шага,

и так далее.

Этот алгоритм перечисляет множество W.

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