計算の理論 II 時間量と領域量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科

今日の講義 領域量と時間量 ミニテスト 復習：space(x), time(x) T(n)時間限定、S(n)領域限定 2019/4/10 佐賀大学理工学部知能情報システム学科

多テープTuring機械の例 1テープTuring機械(DTM) M M= (Q, Σ, Γ, δ, q0, B, F) Q={q0, q1, q2, q3}, Σ={0, 1, #}, Γ={B, 0, 1}, F= {q3}, δは右表 q a X δ(q, a, X) q0 B (q0, 0, R, R) 1 (q0, 1, R, R) # (q1, B, N, L) q1 (q1, 0, N, L) (q1, 1, N, L) $ (q2, $, R, R) q2 (q2, 0, R, R) (q2, 1, R, R) (q3, B, N, N) 2019/4/10 佐賀大学理工学部知能情報システム学科

時間量（ステップ数） timeM(x) xを受理するMの最小ステップ。 timeM(x)=min{ t | ある受理計算状態D(x)に 対してC0(x)├tM D(x)} timeM(x)≧|x| 入力ヘッドは全ての入力記号を読んで 右エンドマーカに到達するから。 始点 終点 入力テープ ￠| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | $ 2019/4/10 佐賀大学理工学部知能情報システム学科

領域量（ます目の量） 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 2019/4/10 佐賀大学理工学部知能情報システム学科

領域sで受理 Mがxを領域sで受理 ある自然数sに対して、 s≧spaceM(x) 2019/4/10 佐賀大学理工学部知能情報システム学科

カウンタ 作業用テープをカウンタとして使用 2進数x=b1…bm→$bm…b1BB… 1加える動作 1引く動作動作 (初期状態p, 終了状態q) →(p, add1, q) 1引く動作動作 (初期状態p, 終了状態q(x>0), r(x=0)) →(p, sub1, q, r) 2019/4/10 佐賀大学理工学部知能情報システム学科

(p, add1, q) 足す 戻る s1 X s2 Y D p $ p1 R 0/B p2 1/1 L 1 0/1 q N 0/1 q N 足す 戻る 2019/4/10 佐賀大学理工学部知能情報システム学科

(p, sub1, q, r) 引けない 借りる 引けた 先頭探し中 戻れる 先頭発見 0削除 戻れる 終了 戻り中 終了 s1 X s2 Y D p $ p1 R B r L 1 p2 p4 p3 q N 0/1 引けない 借りる 引けた 先頭探し中 戻れる 先頭発見 0削除 戻れる 終了 戻り中 2019/4/10 終了 佐賀大学理工学部知能情報システム学科

カウンタによる領域量減少 カウンタ不使用 カウンタ使用 ￠| 0 | 0 | 1 | 0 | # | 0 | 0 | 1 | 0 | $ $ | 0 | 0 | 1 | 0 | B | B | B | B | … $ | 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 | … 2019/4/10 佐賀大学理工学部知能情報システム学科

T(n)時間限定 T(n)を関数とし、MをkテープNTMとする。 言語Lに対して以下の(1)(2)が成り立つとき、 MはLを時間T(n)で受理するという。 また、MはT(n)時間限定(T(n)-time bounded) であるという。 L=L(M) 有限個を除いてすべてのx∈Lに対して timeM(x)≦T(|x|) 2019/4/10 佐賀大学理工学部知能情報システム学科

S(n)領域限定 S(n)を関数とし、MをkテープNTMとする。 言語Lに対して以下の(1)(2)が成り立つとき、 MはLを領域S(n)で受理するという。 また、MはS(n)領域限定(S(n)-space bounded) であるという。 L=L(M) 有限個を除いてすべてのx∈Lに対して spaceM(x)≦S(|x|) 2019/4/10 佐賀大学理工学部知能情報システム学科

NTIME(T(n)), NSPACE(S(n)) NTIMEk(T(n)) ={L|LはあるkテープNTMによって時間T(n)によって受理される} NSPACEk(S(n)) ={L|LはあるkテープNTMによって領域S(n)によって受理される} 2019/4/10 佐賀大学理工学部知能情報システム学科

DTIME(T(n)), DSPACE(S(n)) DTIMEk(T(n)) ={L|LはあるkテープDTMによって時間T(n)によって受理される} DSPACEk(S(n)) ={L|LはあるkテープDTMによって領域S(n)によって受理される} 2019/4/10 佐賀大学理工学部知能情報システム学科

正規言語 Lを正規言語とする。 このとき、以下の(1), (2)が成立する。 ∵すべての文字を一度だけ読み込む L∈DTIME(n) L∈DSPACE(1) ∵すべての文字を一度だけ読み込む 　＆状態のみ使用してメモリは使用しない 2019/4/10 佐賀大学理工学部知能情報システム学科

領域構成可能 関数S(n)は、 このときMはS(n)を、 {ε, 1, 11, 111, 1111, …} L(M)={1}*かつ 有限個を除いてすべてのx∈{1}*に対して spaceM(x)=|_S(|x|)_|となるDTM Mが 存在するとき、 領域構成可能(fully space constructible)である。 このときMはS(n)を、 領域構成する。 2019/4/10 佐賀大学理工学部知能情報システム学科

時間構成可能 関数T(n)は、 このときMはT(n)を、 L(M)={1}*かつ 有限個を除いてすべてのx∈{1}*に対して timeM(x)=|_T(x)_|≧xとを満たすDTM Mが 存在するとき、 時間構成可能(fully time constructible)である。 このときMはT(n)を、 時間構成する。 2019/4/10 佐賀大学理工学部知能情報システム学科

線形領域圧縮定理 関数S(n)は、 を満たしているとする。このとき任意の定数 c>0に対して、次の(1), (2)がすべてのk≧1 について成立する DSPACEk(S(n))=DSPACEk(cS(n)) NSPACEk(S(n))=NSPACEk(cS(n)) 2019/4/10 佐賀大学理工学部知能情報システム学科

線形加速定理 関数T(n)は、 を満たしているとする。このとき任意の定数 c>0に対して、次の(1), (2)がすべてのk≧1 について成立する DTIMEk(T(n))⊆DTIMEk(cT(n)) NTIMEk(T(n))⊆NTIMEk(cT(n)) 2019/4/10 佐賀大学理工学部知能情報システム学科

最後に 開始 ミニテストを提出して帰ること 次回は 言語のクラス 2019/4/10 佐賀大学理工学部知能情報システム学科