Лекции - Машины Тьюринга. Основы теории вычислимости. Булевы функции и пропозициональные формулы
Подождите немного. Документ загружается.
•
poly
•
f ∈ poly k ∈ N f = O(n
k
)
•
poly
•
exp
•
f ∈ exp g ∈ poly f = O(2
g(n)
)
•
exp
poly
•
log
•
f ∈ log f = O(logn)
•
poly
•
f ∈ poly k ∈ N f = O(n
k
)
•
poly
•
exp
•
f ∈ exp g ∈ poly f = O(2
g(n)
)
•
exp
poly
•
log
•
f ∈ log f = O(logn)
•
poly
•
f ∈ poly k ∈ N f = O(n
k
)
•
poly
•
exp
•
f ∈ exp g ∈ poly f = O(2
g(n)
)
•
exp
poly
•
log
•
f ∈ log f = O(logn)
•
•
•
λ
•
•
•
λ
Σ
Σ
Σ
∗
Σ = {a, b} Σ
∗
= {λ, a, b, aa, ab, ba, bb, aaa, . . . }
λ
Σ Σ
∗
Σ
∗
→ Σ
∗
•
.
•
Q q
0
∈ Q
q
f
∈ Q
•
Σ
., ” ” ∈ Σ
•
•
δ : Σ × Q → Σ × Q × {→, ←, •}
•
•
q
0
q
f
•
(q
0
,
0
1
) 7→ (q
0
,
0
1
, →)
•
(q
0
, ) 7→ (q
1
, , ←)
•
(q
1
, 0) 7→ (q
2
, , ←)
•
(q
1
, 1) 7→ (q
3
, , ←)
•
(
q
2
q
3
,
0
1
) 7→ (
q
2
q
3
, , ←)
•
(
q
2
q
3
, .) 7→ (
q
2
q
3
, ., →)
•
(q
2
, ) 7→ (q
f
, 0, •)
•
(q
3
, ) 7→ (q
f
, 1, •)
•
(q
0
, 0) 7→ (q
0
, 0, →)
•
(q
0
, 1) 7→ (q
1
, 1, →)
•
(q
1
, 0) 7→ (q
2
, 0, →)
•
(q
1
, 1) 7→ (q
0
, 1, →)
•
(q
2
, 0) 7→ (q
1
, 0, →)
•
(q
2
, 1) 7→ (q
2
, 1, →)
•
(q
0
, ) 7→ (q
yes
, , •)
•
(q
1
, ) 7→ (q
no
, , •)
•
(q
2
, ) 7→ (q
no
, , •)