Элементы теории алгоритмов - 168 стр.

UptoLike

ВУЗ: 

ЯрГУ | Ярославль

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

Рубрика: 

M
M
1
q
1
010 ...0 |
T
q
0
000 ...0,
q
1
000 ...0 |
T
q
0
010 ...0.
q
1
0 −→ q
2
0R, q
2
1 −→ q
0
0L,
q
2
0 −→ q
0
1L.
p(n)
E T
m T q
1
01
m
0
p(m)
q
0
0ε0 ...0 ε =1 n ∈ E n/∈ E ε =0 n/∈ E n ∈ E
s n>s p(s) < 2
s
q
i
T
q
i
a
j
→ q
i
a
j
S,
T
1
q
1
01
m
0
T n(T
1
) >s
T
1
T
n(T ) >s p(n(T )) < 2
n(T )
n
0
= n(T )
n
0
∈ E n
0
/∈ E T
q
1
01
n
0
0 q
1
01
n(T )
0 p(n
0
)=
p(n(T ))
q
0
010 ...0
p(n(T )) < 2
n(T )
n
0
= n(T ) ∈ E
n
0
/∈ E n
0
∈ E
T q
1
01
n
0
0
q
1
01
n(T )
0 p(n
0
)=p(n(T )) < 2
n(T )
q
0
000 ...0
T q
1
01
n
0
0 q
1
01
n(T )
0
2
n(T )
q
0
010 ...0
E
P
M
NP
P
k

Страницы