Turing機械

C
n 
Turing
n 
uring
Information
Science
Turing
2
Turing
n 
n 
n 
n 
n 
l 
l 
l 
3
$ 1 0 1 1 0 0 0 0 0 B B B B B B
Turing
Turing
q0
q1
$ 1 0 1 1 0 0 0 0 0 B B B B B B
$ 1 0 1 1 0 0 0 0 0 B B B B B B
B
δ(q1,0)=(q2,x,R)
• 
• 
• 
q2
x
q2
B
$ 1 x 1 1 0 0 0 0 0 B B B B B B
Turing
n 
Turing
Turing
(q, b, D)
Turing
Q, Σ, Γ
3
(D=L
D=R)
n 
q
b
n 
n 
3
n 
n 
(Q, Σ, Γ, δ, q0, qaccept, qreject)
n 
Q
n 
Σ
B, $
n 
Γ
Σ
n 
δ: Q’ × Γ → Q × Γ × {L, R}
{B, $} Γ
Q’ = Q−{qaccept , qreject }
(q, b, D)
p
7
a
(p, a)
n 
q0 Q
n 
qaccept
Q
n 
qreject
Q
qreject ≠ qaccept
Turing
δ: Q’ × Γ → Q × Γ × {L, R}
n 
Turing
M
q Q
δ(p, a) = (q, b, D)
δ
δ(p, a) = (q, b, D)
u 
a=$
b=$
u 
a=$
D=R
n 
q
a
n 
n 
D
b
{L, R}
n 
Turing
w=w1w2…wn
M=(Q, Σ, Γ, δ, q0, qaccept, qreject)
l 
q0
0
n+1
l 
$
i =1,…,n
qaccept
i
wi
B
1
l 
q0
$ 1 0 1 1 0 0 0 0 0 B B B B B B
B
Turing
qreject
δ
a
M
Γ
l 
l 
l 
Turing
C0C1…Ck
C0
w
M
Ci
Ck
w
M
w
l 
Ci+1
l 
Turing
M
M
w L
M
w
w L
M
w
L
Turing
L
w
Turing
L
l 
l 
l 
l 
l 
Turing
M
M
w L
M
w
w L
M
w
L
Turing
L
w
L
Turing
G
L
Turing
L
Turing
Turing
n 
L={ w | |w|a=|w|b }
Turing
n 
δ(p, a)=(q, b, D)
p
n 
w=aabbba
a,x→R
q2
x→R
b→x,R
a→x,R
qaccept
B→L
→R
q1
a,b,x,B→L
q4
$→R
b→x,R
B, $→R
a→x,R
q3
b,x→R
qreject
q
δ(p, a)=(q, a, D)
p
B,$→R
a→b, D
a→D
q
1-1
L={ anbn | n≥0 }
n 
Turing
n 
L={ w#w | w
{0,1}* }
Turing
{0,1}* }
Turing
1-2
x→R
0,1→R
x,$,B→R
n 
1,#,$,B→R
0,1→R
0,1→R
0,1,x,#→L
q6
0→x,L
q1
→R
q2
B→L
B,x,$→R
,x,$→R
q5
1→x,L
q9
x→R
x→R
0→x,R
→R
q3
B→R
→R
q4
1→x,R
→R
q8
#→R
$, B→R
q7
B→R
qaccept
0,1,#,$→R
x,$,B→R
0,#,$,B→R
x→R
0,1→R
qreject
L={ wwR | w
1-3
n 
L={ 0n | m ≥ 0
Turing
n=2m}