Составители:
113
Tm T тоже останавливается, отвергая. Наконец, если Tm T
i
не останавливается,
то Tm T тоже не останавливается.
Таким образом, множество L
2
— рекурсивно перечислимо, поскольку оно
принимается Tm T.
Кроме того, множество не может быть рекурсивно перечислимым, так
как если T
j
— машина Тьюринга, принимающая множество , то предложение
x
j
принадлежит множеству тогда и только тогда, когда предложение x
j
не
принимается Tm T
j
. Это противоречит утверждению, что — язык, который
принимается Tm T
j
.
Что и требовалось доказать.
Теорема 7.2. Существует рекурсивно перечислимое множество, которое
не является рекурсивным.
Доказательство. Согласно лемме 7.2 L
2
— рекурсивно перечислимое
множество, дополнение которого не является рекурсивно перечислимым.
Теперь, если бы L
2
было рекурсивным, то по лемме 7.1 его дополнение, т. е. ,
тоже было бы рекурсивным и, следовательно, рекурсивно перечислимым, что
противоречило бы утверждению леммы 7.2.
Что и требовалось доказать.
§ 7.4. Машины Тьюринга
и грамматики типа 0
В этом параграфе мы докажем, что язык распознается машиной Тьюринга
тогда и только тогда, когда он порождается грамматикой типа 0.
Чтобы доказать достаточность, мы построим недетерминированную
машину Тьюринга, которая недетерминированно выбирает вывод в грамматике
и смотрит, совпадает ли результат этого вывода с входной цепочкой. Если да,
то машина принимает её.
Чтобы доказать необходимость, мы строим грамматику, которая
порождает представление терминальной строки, а затем моделирует машину
Тьюринга на этой строке. Если строка принимается машиной, то строка
преобразуется к терминальным символам, которые она представляет.
Теорема 7.3. Если язык L порождается грамматикой типа 0, то язык L
распознается машиной Тьюринга.
Доказательство.
Пусть G =(V
N
, V
T
, P, S) — грамматика типа 0 и L = L(G).
Опишем неформально машину Тьюринга T, принимающую язык L. Машина T
будет недетерминированной.
Пусть T =(Q,
V
T
, Γ, δ, q
0
, F), где Γ = V
N
∪ V
T
∪ {B, #, X}, причём B,#,X∉
V
N
∪ V
T
. Мы не перечисляем всех состояний во множестве Q, но назначаем
некоторые из них, как только в них возникает потребность. Мы разрешаем Tm
T печатать пробел B, если необходимо.
Сначала Tm T имеет ввод w∈V
T
*
на её ленте. Затем, сдвигая цепочку w на
одну ячейку вправо, вставляет на освободившееся перед ней место символ #.
Следом за w печатается цепочка #S#. Содержание ленты в этот момент имеет
вид #w# S#. С этого момента Tm T будет недетерминированно моделировать
2
L
2
L
2
L
2
L
2
L
Страницы
- « первая
- ‹ предыдущая
- …
- 112
- 113
- 114
- 115
- 116
- …
- следующая ›
- последняя »
