Математическая логика и теория алгоритмов. Анкудинов Г.И - 92 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

compl(D)=(T+1)(r+C
2
r
)=r(r+1)(T+1)/2.
&E
Высказывание E состоит из двух высказываний: E = E
1 2
.
Высказывание E
1
утверждает, что в начальной конфигурации (при
t=0) головка обозревает ячейку 1 в состоянии q
1
, а в ячейках
1,…,n+1записано задание z = z(1)…z(n) с разделителем * (для
упрощения записи вместо u
i
пишем ):
i
a
ts
u
,
s,t
z(m)1 *Λ
=v w u u ) u
E
(& )(& .
-T≤s≤0 s,0 1≤m≤n m,0 n+1,01 0 1,0
Сложность этой формулы compl(E
)=2+(T+1)+n+1=T+n+3.
1
Пусть A′⊆ A \ {Λ} – алфавит, в котором представляются
допустимые слова y. Для упрощения будем считать, что
допустимыми словами являются все слова в алфавите A′,
располагающиеся правее z*, т.е. такие, что 1≤l(y)≤T-n-1.
Высказывание E
2
означает, что, начиная с ячейки n+2, записано
некоторое слово в алфавите A′, за которым идут подряд пробелы:
a Λ Λ Λ
E
2
=[&
n+2≤s≤T
(\/
a∈A′∪{Λ}
u )]⎯u (⎯u \/ u {& )}.
s,0 n+2,0 n+2≤s≤T-1 s,0 s+1,0
В формуле для E
2
член в квадратных скобках означает условие
заполнения ячеек s (n+2≤s≤T) символами алфавита A′ или пробелами
Λ, сомножитель⎯u
Λ
n+2,0
указывает на то, что символ в ячейке n+2 не
является пробелом. Часть формулы для E
2
, заключенная в фигурные
скобки, выражает условие того, что после записи y идут ячейки,
содержащие только пробелы (u
Λ Λ Λ Λ
→ u =⎯u \/ u ).
s,0 s+1,0 s,0 s+1,0
Сложность формулы E : compl(E )=(T-n-1)(k-1)+1+(T-n-2)*2.
2 2
)+ compl(E
Следовательно, сложность compl(E)= compl(E
).
1 2
Высказывание F утверждает, что машина работает в
соответствии с программой:
F=&
F
i,j
& & & ,
-T≤s≤T 0≤t≤T 0≤i≤k-1 0≤j≤r-1 s,t
где F
i,j
s,t
– высказывание, утверждающее, что если в момент t в
ячейке s находится символ a
i
, машина находится в состоянии q
j
, а
головка обозревает ячейку s, то конфигурация машины меняется в
соответствии с программой, причем содержимое остальных ячеек не
176

Страницы