Класс рекурсивных множеств

Теперь можно показать, что класс рекурсивных множеств является собственным подклассом класса рекурсивно перечислимых множеств. То есть существует множество, слова которого могут быть распознаны машиной Тьюринга, которая не останавливается на некоторых словах, не принадлежащих множеству, но не может быть распознано никакой машиной Тьюринга, которая останавливается на всех словах. Примером такого множества является дополнение к L₁.

Лемма 2.1. Если множество рекурсивно, то и его дополнение рекурсивно.

Доказательство. Если L - рекурсивное множество, , то существует Tm допускающая L и гарантированно останавливающаяся. Можно считать, что после допуска Tm не делает больше шагов. Построим Tm₁ по Tm, добавив новое состояние q как единственное допускающее состояние Tm₁. Правила Tm₁ включают все правила Tm, так что Tm₁ симулируетTm. Кроме того, для каждой пары, составленной из недопускающего состояния и ленточного символа Tm, для которых у Tmпереход не определен, Tm₁ переходит в состояние q и затем останавливается.

Таким образом Tm₁ симулирует Tm вплоть до остановки. Если Tm останавливается в одном из допускающих состояний, Tm₁останавливается без допуска. Если Tm останавливается в одном из недопускающих состояний, значит не допускает вход. ТогдаTm₁ делает еще один переход в состояние q и допускает. Ясно, что Tm₁ допускает T^*\L.

Лемма 2.2. Пусть - нумерация всех слов некоторого конечного алфавита - и T₁, T₂, ...- нумерация всех машин Тьюринга с ленточными символами, выбранными из некоторого конечного алфавита, включающего -. Пусть . L₂ - рекурсивно перечислимое множество, дополнение которого не рекурсивно перечислимо.

Доказательство. Слова L₂ допускаются некоторой Tm, работающей следующим образом. Отметим, что Tm не обязательно останавливается на словах не из L₂.

1. Если дано x,Tm перечисляет предложения x₁, x₂,... пока не найдет x_i = x, определяя тем самым, что x - это i -е слово в перечислении.

2. Tm генерирует Tm_i и передает управление универсальной машине Тьюринга, которая симулирует Tm_i со входом x.

3. Если Tm_i останавливается со входом x_i и допускает, Tm останавливается и допускает; если Tm_i останавливается и отвергает x_i, то Tm останавливается и отвергает x_i. Наконец, если Tm_i не останавливается, то Tm не останавливается.

4. Таким образом L₂ рекурсивно перечислимо, поскольку L₂ - это множество допускаемое Tm. Но дополнение к не может быть рекурсивно перечислимо, поскольку если T_j - машина Тьюринга, допускающая тогда и только тогда, когда x_j не допускается Tm_j. Это противоречит утверждению, что - это язык, допускаемый T_j.

Теорема 2.3. Существует рекурсивно перечислимое множество, не являющееся рекурсивным.

Доказательство. Доказательство. По лемме 2.2 L₂ - рекурсивно перечислимое множество, дополнение которого не рекурсивно перечислимо. Если бы L₂ было рекурсивно, по лемме было бы рекурсивно, и следовательно рекурсивно перечислимо, что противоречит второй половине леммы 2.2.