計算の理論 I －講義についてー

計算の理論 II
時間量と領域量
月曜5校時
大月美佳
2015/10/1
佐賀大学理工学部知能情報システム学科
1
今日の講義
1. 領域量と時間量
1. 復習：space(x), time(x)
2. T(n)時間限定、S(n)領域限定
2. ミニテスト
2015/10/1
佐賀大学理工学部知能情報システム学科
2
多テープTuring機械の例
 1テープTuring機械
(DTM) M
M= (Q, Σ, Γ, δ, q0, B, F)
Q={q0, q1, q2, q3},
Σ={0, 1, #},
Γ={B, 0, 1},
F= {q3}, δは右表
2015/10/1
q
a
X
δ(q, a, X)
q0
0
B
(q0, 0, R, R)
q0
1
B
(q0, 1, R, R)
q0
#
B
(q1, B, N, L)
q1
#
0
(q1, 0, N, L)
q1
#
1
(q1, 1, N, L)
q1
#
$
(q2, $, R, R)
q2
0
0
(q2, 0, R, R)
q2
1
1
(q2, 1, R, R)
q2
$
B
(q3, B, N, N)
佐賀大学理工学部知能情報システム学科
3
時間量（ステップ数）
 timeM(x)
xを受理するMの最小ステップ。
timeM(x)=min{ t | ある受理計算状態D(x)に
対してC0(x)├tM D(x)}
timeM(x)≧|x|
入力ヘッドは全ての入力記号を読んで
右エンドマーカに到達するから。
始点
入力テープ
2015/10/1
終点
￠| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | $
佐賀大学理工学部知能情報システム学科
4
領域量（ます目の量）
 space(x)
xを受理するMの計算
α: C0(x)├ C1(x) …├ Ct(x)
space(α)=max{hi(j)| 0≦j≦t, 1≦i≦k }
ただし、 Cj(x): (pj , (h(j), ￠x$), (h1(j), ξ1(j)), …, (hk(j), ξk(j)))
(0≦j≦t)
spaceM(x)=min{ space(α) | ある受理計算状態
D(x)に対してα: C0(x)├*M D(x)}
spaceM(x)≧1
∵作業テープの始点つまりhi(0)は1
2015/10/1
佐賀大学理工学部知能情報システム学科
5
領域sで受理
 Mがxを領域sで受理
ある自然数sに対して、 s≧spaceM(x)
2015/10/1
佐賀大学理工学部知能情報システム学科
6
カウンタ
作業用テープをカウンタとして使用
2進数x=b1…bm→$bm…b1BB…
1加える動作
(初期状態p, 終了状態q) →(p, add1, q)
1引く動作動作
(初期状態p, 終了状態q(x>0), r(x=0))
→(p, sub1, q, r)
2015/10/1
佐賀大学理工学部知能情報システム学科
7
(p, add1, q)
2015/10/1
s1
X
s2
Y
D
p
$
p1
$
R
足す
p1
0/B
p2
1/1
L
p1
1
p1
0
R
戻る
p2
0/1
p2
0/1
L
p2
$
q
$
N
佐賀大学理工学部知能情報システム学科
8
(p, sub1, q, r)
引けない
借りる
s1
X
s2
Y
D
p
$
p1
$
R
p1
B
r
B
L
p1
0
p1
1
R
p1
1
p2
0
引けた
p2
0
p2
0
先頭探し中
p2
1
p4
1
戻れる
p2
B
p3
B
先頭発見
p3
0
p3
B
0削除
p3
1
p4
1
戻れる
p3
$
q
$
終了
戻り中
p4
0/1
p4
0/1
2015/10/1
終了佐賀大学理工学部知能情報システム学科
p4
$
q
$
R
R
L
L
L
L
N
L
N
9
カウンタによる領域量減少
￠| 0 | 0 | 1 | 0 | # | 0 | 0 | 1 | 0 | $
カウンタ不使用
$|0|0|1|0|B|B|B|B|…
￠| 0 | 0 | 1 | 0 | # | 0 | 0 | 1 | 0 | $
カウンタ使用
$|1|1|B|B|B|B|B|B|…
$|1|1|B|B|B|B|B|B|…
$|1|B|B|B|B|B|B|B|…
$|1|B|B|B|B|B|B|B|…
2015/10/1
佐賀大学理工学部知能情報システム学科
10
T(n)時間限定
T(n)を関数とし、MをkテープNTMとする。
言語Lに対して以下の(1)(2)が成り立つとき、
MはLを時間T(n)で受理するという。
また、MはT(n)時間限定(T(n)-time bounded)
であるという。
(1) L=L(M)
(2) 有限個を除いてすべてのx∈Lに対して
timeM(x)≦T(|x|)
2015/10/1
佐賀大学理工学部知能情報システム学科
11
S(n)領域限定
S(n)を関数とし、MをkテープNTMとする。
言語Lに対して以下の(1)(2)が成り立つとき、
MはLを領域S(n)で受理するという。
また、MはS(n)領域限定(S(n)-space bounded)
であるという。
(1) L=L(M)
(2) 有限個を除いてすべてのx∈Lに対して
spaceM(x)≦S(|x|)
2015/10/1
佐賀大学理工学部知能情報システム学科
12
NTIME(T(n)), NSPACE(S(n))
NTIMEk(T(n))
={L|LはあるkテープNTMによって時間T(n)によって受
理される}
NSPACEk(S(n))
={L|LはあるkテープNTMによって領域S(n)によって受
理される}
NT IME(T (n))   NT IMEk (T (n))
k 1
NSP SCE ( S (n))   NSP ACEk ( S (n))
k 1
2015/10/1
佐賀大学理工学部知能情報システム学科
13
DTIME(T(n)), DSPACE(S(n))
DTIMEk(T(n))
={L|LはあるkテープDTMによって時間T(n)によって受
理される}
DSPACEk(S(n))
={L|LはあるkテープDTMによって領域S(n)によって受
理される}
DT IME(T (n))   DT IMEk (T (n))
k 1
DSP ASCE( S (n))   DSP ACEk ( S (n))
k 1
2015/10/1
佐賀大学理工学部知能情報システム学科
14
正規言語
Lを正規言語とする。
このとき、以下の(1), (2)が成立する。
(1) L∈DTIME(n)
(2) L∈DSPACE(1)
∵すべての文字を一度だけ読み込む
＆状態のみ使用してメモリは使用しない
2015/10/1
佐賀大学理工学部知能情報システム学科
15
領域構成可能
関数S(n)は、
{ε, 1, 11, 111, 1111, …}
L(M)={1}*かつ
有限個を除いてすべてのx∈{1}*に対して
spaceM(x)=|_S(|x|)_|となるDTM Mが
存在するとき、
領域構成可能(fully space constructible)である。
このときMはS(n)を、
領域構成する。
2015/10/1
佐賀大学理工学部知能情報システム学科
16
時間構成可能
関数T(n)は、
L(M)={1}*かつ
有限個を除いてすべてのx∈{1}*に対して
timeM(x)=|_T(x)_|≧xとを満たすDTM Mが
存在するとき、
時間構成可能(fully time constructible)である。
このときMはT(n)を、
時間構成する。
2015/10/1
佐賀大学理工学部知能情報システム学科
17
線形領域圧縮定理
関数S(n)は、
lim S (n)  
n 
を満たしているとする。このとき任意の定数
c>0に対して、次の(1), (2)がすべてのk≧1
について成立する
(1) DSPACEk(S(n))=DSPACEk(cS(n))
(2) NSPACEk(S(n))=NSPACEk(cS(n))
2015/10/1
佐賀大学理工学部知能情報システム学科
18
線形加速定理
関数T(n)は、
lim T ( n) / n  
n 
を満たしているとする。このとき任意の定数
c>0に対して、次の(1), (2)がすべてのk≧1
について成立する
(1) DTIMEk(T(n))⊆DTIMEk(cT(n))
(2) NTIMEk(T(n))⊆NTIMEk(cT(n))
2015/10/1
佐賀大学理工学部知能情報システム学科
19
最後に
開始
 ミニテストを提出して帰ること
 次回は
言語のクラス
2015/10/1
佐賀大学理工学部知能情報システム学科
20

Download Report