Морозов А.С. Введение в вычислимость
Подождите немного. Документ загружается.
A = {a
0
, . . . , a
m
}
a
0
= 0
Q = {q
0
, q
1
, . . . , q
n
} Q ∩
A = ∅ n > 0
q
i
a
j
→ q
k
a
l
S, q
i
, q
k
∈ Q, a
j
, a
l
∈ A, S ∈ {Λ, R, L},
q
i
a
j
q
i
a
j
→ q
k
a
l
S
. . . a
i
a
l
a
k
. . .
@
@
¡
¡
q
j
q
i
a
j
q
i
a
j
→ q
k
a
l
S
q
k
a
j
a
l
S = R
a
0
S = L
a
0
q
i
a
j
→ q
k
a
l
S
q
0
q
1
q
0
q
j
c
1
, . . . , c
j
, . . . , c
p
c
1
. . . qc
j
. . . c
p
Q ∩ A = ∅
M
v w
v ⇒
M
w
v
w
v V
M
w
M
M
{0, 1} a
0
= 0 {q
0
, q
1
, q
2
, q
3
}
q
1
0 → q
2
0R q
3
1 → q
3
0L
q
2
1 → q
2
1R q
3
0 → q
0
0Λ
q
2
0 → q
3
0L
q
1
011 ⇒
M
0q
2
11 ⇒
M
01q
2
1 ⇒
M
011q
2
0 ⇒
M
⇒
M
01q
3
10 ⇒
M
0q
3
100 ⇒
M
q
3
0000 ⇒
M
q
0
0000.
q
1
011 V
M
q
0
0000.
n q
1
01
n
V
M
q
0
0
n+2
.
f N
k
N
M
x
1
, . . . , x
k
∈ N f(x
1
, . . . , x
k
)
0q
1
1
x
1
+1
0 . . . 01
x
k
+1
0 V
M
0q
0
1
f(x
1
,...,x
k
)+1
0 . . . 0.
x
1
, . . . , x
k
∈ N f(x
1
, . . . , x
k
)
M
0q
1
1
x
1
+1
0 . . . 01
x
k
+1
0
M M
f(x) = x + 1
q
1
1 → q
1
1R, q
1
0 → q
2
1L, q
2
1 → q
2
1L, q
2
0 → q
0
0R.
S, R, M
(Λ) = 0, (L) = 1, (R) = 2
(q
i
a
j
→ q
k
a
l
S) = hi, j, k, l, (S)i .
c
1
, . . . , c
s
h (c
1
), . . . , (c
s
)i
a
i
1
, . . . , q
j
a
i
p
, . . . , a
i
r
hi
1
, . . . , i
p
, . . . , i
r
, j, pi
w
0
, w
1
, . . . , w
u
M
w
0
⇒
M
w
1
⇒
M
. . . ⇒
M
w
u
w
u
q
0
w
u
w
0
, w
1
, . . . , w
u
h (w
0
), (w
1
), . . . , (w
u
)i .
T
0
k
(e, x
1
, . . . , x
k
, y) y
e 0q
1
1
x
1
+1
0 . . . 01
x
k
+1
0
U
1
(y) y
0q
0
1
z+1
0β
z
U
1
(y) y
e
f : N
k
→ N
f(x
1
, . . . , x
k
) ' U
1
(µyT
0
k
(e, x
1
, . . . , x
k
, y)).
¤
R
0
R
1
L
0
L
1
x ∈ N
q
1
1
x
0 V
R
0
1
x
q
0
0
q
1
0
x
1 V
R
1
0
x
q
0
1
10
x
q
1
0 V
L
1
q
0
10
x
0
01
x
q
1
1 V
L
0
q
0
01
x
1
M
+
q
1
M
−
q
1
M
0
M
1
M
α
0
α
1
β
0
β
1
γ
0
γ
1
α
0
q
1
α
1
V
M
0
β
0
q
0
β
1
β
0
q
1
β
1
V
M
1
γ
0
q
0
γ
1
,
α
0
q
1
α
1
V
M
γ
0
q
0
γ
1
.
M
M M
0
M
1
M
0
· M
1
M
1
q
1
q
2
. . . q
0
q
0
1
, q
0
2
, . . . M
0
M
0
q
0
q
0
1
M
0
M
0
q
0
q
0
1
M
1
q
i
q
0
i
q
0
M
1
M
0
M
1
M
2
M
α
0
α
1
M
0
α
0
q
1
α
1
α
0
q
1
α
1
V
M
0
β
0
q
0
β
1
M
1
β
0
q
1
β
1
M
2
M
M
∗
x ∈ N
0q
1
1
x+1
0 V 0q
0
1
x+1
01
x+1
0.
∗
x, y ∈ N
0q
1
1
x+1
01
y+1
0 V 0q
0
1
y+1
01
x+1
0.
∗
S R M
∗
A
0, 1, (, ), ∗, ¤ /∈ A.
A
0
= A ∪ {0, 1, (, ), ∗, ¤}
M A
w ∈ (A
0
)
∗
A
q
1
¤w¤ V
M
q
0
1,
w ∈ (A
0
)
∗
A
q
1
¤w¤ V
M
q
0
0.
A
α → β
α →• β α, β ∈ A
∗
w ∈ A
∗
α → β α →• β
α w
w w
0
w
α w β
w →
A
w
0
w
A = 00 → 1 002200 →
A
12200
A w ∈ A
A w
w
0
A
w
0
A
w
∗
A w A(w) = w
∗
A w
A = 0 → 11; 2 →• 0 0020 →
A
11020 →
A
111120 →
A
111100 A(0020) = 111100
A = Λ → 1 Λ →
A
1Λ →
A
11Λ →
A
111Λ →
A
. . . A(Λ)
A = 0 → 1 A(22) = 22
f : N
k
→
N A
x
1
, . . . , x
k
∈ N f(x
1
, . . . , x
k
)
A(1
x
1
01
x
2
0 . . . 01
x
k
) = 1
f(x
1
,...,x
k
)
f(x
1
, . . . , x
k
) A(1
x
1
01
x
2
0 . . . 01
x
k
)
f : N
k
→ N
s(x) = x + 1
Λ →• 1
f(x) = 0
x
˙
−1
x − 1
x
˙
−y
x − y
f(x) = x
I
m
n
(x
1
, . . . , x
m
) = x
n
A
A
A(w) = Λ w ∈ A
∗
A(w) = 1
|w|
w ∈ A
∗
A(w) = w
0
w ∈ A
∗
∗
A(w) =
½
w
0
w = w
0
Λ
w ∈ A
∗
w
0
f(w) = aw a
∗
f(w) = wa a
∗
A(w) =
½
1 w
0
