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

UptoLike

ВУЗ: 

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

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

Рубрика: 

меняется.
Пусть команды машины имеют вид:
q
j
a
i
→ a
α
(j,i)
D
j,i
q
β
(j,i)
(0≤i≤k-1, 0≤j≤r-1).
Обозначим через
δ
(j,i) перемещение головки для команды с левой
частью q
j
a
i
:
-1, если D
j,i
=Л,
δ
(j,i) = 0, если D
j,i
=Н,
1, если D
j,i
=П.
Тогда
F
i,j j i
s,t
=(v
t
u
s,t
w
s,t
→ v
β
(j,i)
t+1
u
α
(j,i) i i
w )&(u
s,t+1 s+
δ
(j,i),t+1 s,t
⎯
w → u ).
s,t s,t+1
Выразим импликацию через дизъюнкцию и отрицание, используем
закон де-Моргана и дистрибутивный закон, чтобы получить
окончательное выражение:
F
i,j j i
s,t
=(⎯v
t
\/⎯u
s,t
\/⎯w
s,t
\/ v
β
(j,i)
u
α
(j,i)
w )&
t+1 s,t+1 s+
δ
(j,i),t+1
&(⎯u
i i
\/ w \/ u )=
s,t s,t s,t+1
j i
=(⎯v
t
\/⎯u
s,t
\/⎯w
s,t
\/ v
β
(j,i) j i
t+1
)&(⎯v
t
\/⎯u
s,t
\/⎯w \/ u
α
(j,i)
)&
s,t s,t+1
j i i i
&(⎯v
t
\/⎯u \/⎯w \/ w )&(⎯u \/ w \/ u ).
s,t s,t s+
δ
(j,i),t+1 s,t s,t s,t+1
Сложность F
i,j
s,t
равна 15, поэтому сложность F выражается
полиномом compl(F)=15(2T+1)(T+1)kr.
Высказывание G означает, что на шаге T машина окажется в
конфигурации q
1:
0
1 1 1Λ
G=[(&
(u \/ u (⎯u \/⎯u))( &
-T≤s≤T s,t s,t -T≤s<q≤T s,t q,t
))]&
& v
0 1
(⎯w \/ u {& )}.
T -T≤s≤T s,T s,T
В формуле для G:
• выражение в квадратных скобках означает, что в момент
времени T на ленте записаны символы Λ и 1, причем 1 – не более чем
в одной ячейке;
0
означает, что машина находится в состоянии q• v ;
T 0
• выражение в фигурных скобках обеспечивает наличие 1 в
обозреваемой ячейке.
Сложность формулы для G можно оценить выражением
177

Страницы