3.3. Универсальные машины Тьюринга 149
над N
u
∪ T
u
, которая обладает таким свойством: для каждой
грамматики G = (N, T
u
, S, P ) типа 0 существует такая строка
w(G), что L
G
u
, w(G)
= L(G).
Итак, универсальная грамматика моделирует любую напе-
ред заданную грамматику G при условии, что код w(G) послед-
ней берется в качестве аксиомы универсальной грамматики.
Универсальные грамматики типа 0 в описанном выше смыс-
ле существуют. Так как это утверждение лежит в основе после-
дующих рассмотрений, приведем его полное доказательство.
Пусть G = (N, T, S, P ) — гр амматика типа 0. Без огра-
ничения общности можно предполагать, что нетерминальных
символов всего три, N = {S, A, B}. (Если их больше, скажем
N = {S, X
1
, X
2
, . . . , X
n
}, где n > 3, то заменим каждое вхо-
ждение X
i
в правила из P на AB
i
A, 1 6 i 6 n, для каких-то
новых символов A, B. Очевидно, что полученная грамматика
будет эквивалентна исходной.)
Построим грамматическую схему
G
u
= (N
u
, T, P
u
),
в которой
N
u
= {A, B, C, D, E, F, H, R, Q, S, X, Y }
∪ {[a, i] | a ∈ T, 1 6 i 6 9},
а множество P
u
состоит из следующих правил:
(I) (1) C → BQ,
(2) Qα → αQ для α ∈ N ∪ T ∪ {D, E},
(II) (3) QDα → [α, 2]D[α, 1] для α ∈ N ∪ T ,
(4) α[β, 2] → [β, 2]α для α ∈ N ∪ T ∪ {D, E}, β ∈ N ∪ T ,
(5) B[α, 2] → [α, 3]B для α ∈ N ∪ T ,
(6) α[β, 3] → [β, 3]α для α, β ∈ N ∪ T ,
(7) α[α, 3] → [α, 4] для α ∈ N ∪ T ,
(III) (8) [α, 1]β → [β, 5][α, 1][β, 1] для α, β ∈ N ∪ T ,
(9) α[β, 5] → [β, 5]α для α ∈ N ∪ T ∪ {D, E}, β ∈ N ∪ T ,
(10) B[α, 5] → [α, 6]B для α ∈ N ∪ T ,