Составители:
112
§ 7.3. Класс
рекурсивных множеств
Мы можем теперь показать, что класс рекурсивных множеств является
собственным подмножеством рекурсивно перечислимых множеств. Другими
словами, существует множество, предложения которого могут быть распоз-
наны машиной Тьюринга, которая не останавливается на некоторых
предложениях не из этого множества, но не могут быть распознаны никакой
машиной Тьюринга, которая останавливается всегда. Примером такого множе-
ства является дополнение множества L
1
, о котором шла речь в предыдущем
параграфе. Прежде, чем доказать это, дадим две леммы.
Лемма 7.1. Если множество рекурсивно, то его дополнение тоже рекурсивно.
Доказательство. Если L ⊆Σ
∗
— рекурсивное множество, то существует
машина Тьюринга T, гарантированно останавливающаяся, которая принимает
язык L. Можно предполагать, что после принятия входной цепочки Tm T не
делает больше никаких движений.
Построим другую машину Тьюринга — T
1
, у которой одно принимающее
состояние q. Правила Tm T
1
включают все правила машины T, так что Tm T
1
моделирует Tm T. Кроме того, функция δ Tm T
1
доопределяется для неприни-
мающих состояний и допустимых символов ленты, для которых дальнейшее
движение не определено, движением, переводящим Tm T
1
в принимающее
состояние q. В состоянии q машина T
1
останавливается, принимая входную
цепочку, которая первоначальной машиной T не принимается.
Так Tm T
1
моделирует Tm T до тех пор, пока Tm T не останавливается. Если
машина T останавливается в непринимающем состоянии, она, конечно, не
принимает свою входную цепочку, но Tm T
1
делает ещё одно движение в
состояние q и принимает. Ясно, что Tm T
1
принимает язык Σ
∗
\ L.
Что и требовалось доказать.
Лемма 7.2. Пусть x
1
, x
2
, ... — эффективное перечисление всех предложений
над некоторым конечным алфавитом Σ, а T
1
, T
2
, ... — эффективное перечисление
всех машин Тьюринга с символами ленты, выбранными из некоторого конечного
алфавита, включающего Σ. Пусть L
2
={ x
i
| x
i
принимается машиной T
i
}.
Утверждается, что L
2
— рекурсивно перечислимое множество, дополнение
которого не является рекурсивно перечислимым.
Доказательство. Предложения языка L
2
могут приниматься машиной
Тьюринга T, которая не обязательно останавливается на предложениях, не при-
надлежащих языку L
2
, и действует следующим образом.
Для данного предложения x машина T перечисляет цепочки x
1
, x
2
, ... до тех
пор, пока она не находит цепочку x
i
= x, тем самым определяя, что x является
i-й цепочкой в перечислении.
Затем Tm T генерирует Tm T
i
и передаёт управление универсальной
машине Тьюринга, которая моделирует Tm T
i
с входной цепочкой x
i
.
Если Tm T
i
с входой цепочкой x
i
останавливается и принимает, то Tm T
тоже останавливается, принимая. Если Tm T
i
останавливается и отвергает x
i
, то
Страницы
- « первая
- ‹ предыдущая
- …
- 111
- 112
- 113
- 114
- 115
- …
- следующая ›
- последняя »
