Морозов А.С. Введение в вычислимость
Подождите немного. Документ загружается.
n n
n 0 9
10
n
n
n
n + 1
n = 11
n = 15
n = 20
p(n)
n
q
i
a
j
q
i
a
j
→ . . . q
i
a
j
A ¤, 0, 1 /∈ A
A∪{¤, 0, 1}
A
p(x)
w ∈ A
∗
q
1
¤w¤
q
0
p(|w|)
M
L A L ⊆ A
∗
w ∈ A
∗
M q
1
¤w¤
w ∈ L . . . q
0
1 . . .
w /∈ L . . . q
0
0 . . .
M L
A L
A L
A
M L A L ⊆ A
∗
w ∈ A
∗
M
q
1
¤w¤ w ∈ L
. . . q
0
1 . . . M
L
A L
A L
A
A
L
A ¤, 0, 1 /∈ A A
0
L
L
A
L
A
0
→
→ M
L A
0
A
0
= {a
1
, . . . , a
k
} A \ A
0
= {c
1
, . . . , c
m
}
M
L A
q
1
¤w¤ w ∈ A
∗
w
c
1
, . . . , c
m
. . . q
0
0 . . .
¤ M
M
0
q
1
¤ → r
1
¤R
r
1
a
1
→ r
1
a
1
R
···
r
1
a
k
→ r
1
a
k
R
r
1
¤ → r
2
¤L
r
2
a
1
→ r
2
a
1
L
···
r
2
a
k
→ r
2
a
k
L
r
2
¤ → q
0
¤
r
1
c
1
→ q
0
0
···
r
1
c
m
→ q
0
0
r
0
r
1
M
q
0
q
1
w ∈ A
∗
0
M
0
2(|w|+ 1)
q
0
¤w¤
2(|w| + 1) . . . q
0
0 . . .
M
0
M q
0
→ q
0
0
M
00
= M
0
· M
0
L A
M p(x)
M
00
M
00
q
1
¤w¤ M
0
2(|w|+1)
M
0
p(|w|) + 1
2(|w|+1)+p(|w|)+1
¤
P = {L | L
},
NP = {L | L
}
P
M
L A M
0 1 1 0
A
∗
\ L A ¤
E
P
α = q
i
a
j
→ q
k
a
m
S S ∈ {Λ, L, R}
bα
q |. . . |
|{z}
i
a |. . . |
|{z}
j
→ q |. . . |
|{z}
k
a |. . . |
|{z}
j
S,
q a | → Λ L R
M α
1
α
p
c
M
cα
1
; cα
2
; . . . ; cα
p
;
E = {
c
M | M q
1
¤
c
M¤
. . . q
0
1 . . .
2
|
c
M|
}
E
{q, a, |, →, Λ, L, R, ; }
c
M
M
c
M M
q
1
¤
c
M¤
. . . q
0
1 . . . 2
|
c
M|
E
E ∈ P
E M
p(x)
M
p(|
c
M|) < 2
|
c
M|
.
p(n)
2
n
→ ∞ n → ∞
n
0
n > n
0
p(n) < 2
n
|
c
M|
M q
i
a
j
→ q
k
a
m
S
q
i
M i
q
i
M
M q
1
¤
c
M¤
p(|
c
M|) < 2
|
c
M|
c
M E
c
M ∈ E
M q
1
¤
c
M¤
. . . q
0
1 . . .
M E
M q
1
¤
c
M¤
. . . q
0
1 . . .
c
M /∈ E
E
M q
1
¤
c
M¤
. . . q
0
1 . . .
E ∈ P ¤
A
A ⊆ A
∗
B ⊆ B
∗
A, B p(x)
M
w ∈ A
∗
p(|w|) w
0
w ∈ A ⇔ w
0
∈ B
2
100
2
100
60·60·24·365
10
22
{1, . . . , n}
& ∨ ¬
→
U S
S
0
⊆ S
U
