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

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

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

Доказательство. Если L - рекурсивное множество,

, то существует Tm допускающая L и гарантированно останавливающаяся. Можно считать, что после допуска Tm не делает больше шагов. Построим Tm1 по Tm, добавив новое состояние q как единственное допускающее состояние Tm1. Правила Tm1 включают все правила Tm, так что Tm1

симулирует Tm. Кроме того, для каждой пары, составленной из недопускающего состояния и ленточного символа Tm, для которых у Tm переход не определен, Tm1 переходит в состояние q и затем останавливается.

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

Лемма 2.2. Пусть

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

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

1. Если дано x,Tm перечисляет предложения x1, x2,... пока не найдет xi = x, определяя тем самым, что x - это i-е слово в перечислении.
2. Tm генерирует Tmi и передает управление универсальной машине Тьюринга, которая симулирует Tmi со входом x.
3. Если Tmi останавливается со входом xi и допускает, Tm останавливается и допускает; если Tmi останавливается и отвергает xi, то Tm останавливается и отвергает xi.
   Наконец, если Tmi не останавливается, то Tm не останавливается.
4. Таким образом L2 рекурсивно перечислимо, поскольку L2 - это множество допускаемое Tm. Но дополнение к
   
   не может быть рекурсивно перечислимо, поскольку если Tj - машина Тьюринга, допускающая
   
   
   
   тогда и только тогда, когда xj не допускается Tmj . Это противоречит утверждению, что
   
   - это язык, допускаемый Tj .

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

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


Содержание раздела

---

---