計算の理論 II
Turing機械の合成その2
月曜4校時
大月美佳
2015/10/1
佐賀大学理工学部知能情報システム学科
1
講義の前に
今後の日程(再掲)
– 休講・補講について
• 1/26は休講（学会関連）
• 1/21と1/22(と他1日)が補講
– レポートについて
• 12/22に大レポート(20点配点)
– 試験
• 2/9が試験(40点配点)
2015/10/1
佐賀大学理工学部知能情報システム学科
2
今日の講義
1. 前回のおさらい
1. Turing機械(TM)合成の基礎
2. T, S, C, Kn
2. 帰納的関数を計算するTMの合成
1. 初期関数を表すTM
2. 合成と帰納を表すTM
3. ミニテスト・前回テスト回収
2015/10/1
佐賀大学理工学部知能情報システム学科
3
Turing機械の作り方
Turing機械を合成して作る
1. 単純なTuring機械
B, 1, r, l, <a>
2. 1から基本的なTuring機械を合成
R, L, R, T, S, C, Kn
3. 初期関数に対応するTuring機械を合成
Z(x), S(x), Uni(x1,…, xn)
4. 原始帰納的関数関数の操作I, II
2015/10/1
佐賀大学理工学部知能情報システム学科
4
Turing機械 B
ヘッドが置かれてい
ます目に空白記号Bを
書き込む。
B=({q0, qh}, {B, 1}, K,
q0, {qh})
K= { q01BNqh,
q0BBNqh }
2015/10/1
B
B
B1 B
BBB
有限
制御部
有限
制御部
q0→qh
q0→qh
佐賀大学理工学部知能情報システム学科
5
Turing機械 1
ヘッドが置かれてい
ます目に1を書き込む。
B=({q0, qh}, {B, 1}, K,
q0, {qh})
K= { q011Nqh,
q0B1Nqh }
2015/10/1
1
1
B1 B
BBB
有限
制御部
有限
制御部
q0→qh
q0→qh
佐賀大学理工学部知能情報システム学科
6
Turing機械 r
ヘッドを1こま右へ移す。
B=({q0, qh}, {B, 1}, K,
q0, {qh})
K= { q011Rqh,
q0BBRqh }
1
B
B1 B
BBB
有限有限
制御部
制御部
q0→qh
2015/10/1
佐賀大学理工学部知能情報システム学科
有限有限
制御部
制御部
q0→qh
7
Turing機械 l
ヘッドを1こま左へ移す。
B=({q0, qh}, {B, 1}, K,
q0, {qh})
K= { q011Lqh,
q0BBLqh }
1
B
B1 B
BBB
有限有限
制御部
制御部
q0→qh
2015/10/1
佐賀大学理工学部知能情報システム学科
有限有限
制御部
制御部
q0→qh
8
Turing機械 <a>
読み取られた記号がaで
あるか否かを判定する。
a
aであればqhで停止し、
aでなければq1で停止する。 B a B
B=({q0, q1, qh}, {B, 1}, K,
q0, {q1 , qh})
有限
制御部
K= { q0aaNqh, q0bbNq1 }
q0→qh
ここで、a≠b
2015/10/1
佐賀大学理工学部知能情報システム学科
b
BbB
有限
制御部
q0→q1
9
合成
2つのTuring機械
M1=(Q1, Σ, K1, q01, F1), M2=(Q2, Σ, K2, q02, F2)
Q1∩Q2 ＝Φと仮定できる。
（できない場合は状態の名前を付け替える）
q∈F1 とq02 ∈Q2 を同一視して得られる
以下のTuring機械
M1ーq→M2 =(Q1∪Q2, Σ, K, q01, F1∪F2 －{q})
K=K1∪K2∪{qaaNq02 | a∈Σ}
をqにおけるM1とM2 の結合と呼ぶ。
2015/10/1
佐賀大学理工学部知能情報システム学科
10
結合のバリエーション
Turing機械M, M1, M2
(Q, Σ, K, q0, F－{q})
p
M
q
K=K∪{qaaNq0 | a∈Σ}
M1
M
q
M2
(Q∪Q1∪Q2, Σ, K, q0, F∪F1 ∪F2 －{p, q})
K=K∪K1∪K2∪{paaNq01, qbbNq02 | a, b∈Σ}
2015/10/1
佐賀大学理工学部知能情報システム学科
11
簡易表記
F1={q}であるとき、
単にM1M2と書ける。 M1
q
M2 → M1 M2
Mが<a>のとき、
qh, q1をyes, noのように書ける。
<a>
qh
q1
2015/10/1
M1
M2
→
<a>
yes
no
佐賀大学理工学部知能情報システム学科
M1
M2
12
Turing機械 R
ヘッドの右側にある最初の
Bを探し、そこで止まる。
Turing機械rと<B>から合成。
r=({q0, qh}, {B, 1}, K1, q0, {qh})
K1={q0BBRqh, q011Rqh}
r<B>
no
<B>=({p0, p1, ph}, {B, 1}, K2, p0,
{p1, ph})
K2={p0BBNph, p011Np1}
2015/10/1
佐賀大学理工学部知能情報システム学科
13
Turing機械 R つづき
R=(Q, {B, 1}, K, q0, F)
Q={q0, qh}∪{p0, p1, ph}={q0, qh, p0, p1, ph}
K=K1∪K2∪{qhBBNp0, qh11Np0, p111Nq0}
= {q0BBRqh, q011Rqh, p0BBNph, p011Np1,
qhBBNp0, qh11Np0, p111Nq0}
F= {qh}∪ {p1, ph}－{qh}－{p1}={ph}
2015/10/1
佐賀大学理工学部知能情報システム学科
14
Turing機械 L
ヘッドの左側にある最初の
Bを探し、そこで止まる。
Turing機械lと<B>から合成。
l=({q0, qh}, {B, 1}, K1, q0, {qh})
K1={q0BBLqh, q011Lqh}
l<B>
no
<B>=({p0, p1, ph}, {B, 1}, K2, p0,
{p1, ph})
K2={p0BBNph, p011Np1}
2015/10/1
佐賀大学理工学部知能情報システム学科
15
Turing機械 L つづき
R=(Q, {B, 1}, K, q0, F)
Q={q0, qh}∪{p0, p1, ph}={q0, qh, p0, p1, ph}
K=K1∪K2∪{qhBBNp0, qh11Np0, p111Nq0}
= {q0BBLqh, q011Lqh, p0BBNph, p011Np1,
qhBBNp0, qh11Np0, p111Nq0}
F= {qh}∪ {p1, ph}－{qh}－{p1}={ph}
2015/10/1
佐賀大学理工学部知能情報システム学科
16
Turing機械 R
ヘッドの右側にある最初の
連続したBBを探し、
その左側のBの位置で止まる。
Turing機械Rとr, lと<B>から合成。
r=({q0, qh}, {B, 1}, K1, q0, {qh})
Rr<B>
K1={q0BBRqh, q011Rqh}
no
yes
l
<B>=({p0, p1, ph}, {B, 1}, K2, p0,
{p1, ph})
K2={p0BBNph, p011Np1}
R=(Q, {B, 1}, K, q0, F)
2015/10/1
佐賀大学理工学部知能情報システム学科
17
*Turing機械 T
1の連続したかたまりを1こまづつ左へ移す。
～BWB├*T ～WBB
ここで、
～：任意の記号
W：1の連続したかたまり
（下線）：ヘッドの位置
～BWB=q0～BWB
～WBB=～WqhBB
2015/10/1
rr<B>
no
yes
Bl1
l
佐賀大学理工学部知能情報システム学科
18
Tの計算例
～B11B
rr<B>
yes
l
2015/10/1
no
Bl1
├* ～B11B
├* ～1B1B
├* ～1B1B
├* ～11BB
├* ～11BB
├* ～11BB
佐賀大学理工学部知能情報システム学科
(rr<B>)
(Bl1)
(rr<B>)
(Bl1)
(rr<B>)
(l)
19
*Turing機械 S
1のかたまりW1, W2に対して以下の処理を
行う。
BW1BW2B├*S BW2BB…B
ここで、
W1, W2：1の連続したかたまり
（下線）：ヘッドの位置
Ll<B>
yes
no
BT
T
2015/10/1
佐賀大学理工学部知能情報システム学科
20
Sの計算例
B11B111B ├* B11B111B
├* B1B111BB
├* B1B111BB
├* BB111BBB
no
Ll<B>
BT ├* BB111BBB
yes
├* B111BBBB
T
2015/10/1
佐賀大学理工学部知能情報システム学科
(Ll<B>)
(BT)
(Ll<B>)
(BT)
(Ll<B>)
(T)
21
*Turing機械 C
1のかたまりW1, W2, …, Wn, Wに対して
以下の処理を行う。
～BBW1BW2B…BWnBWB ├*c ～WBB…B
Ll<B>
no
yes
rRS
TLlT
2015/10/1
佐賀大学理工学部知能情報システム学科
22
Cの計算例
～BB11B1B111B
Ll<B>
no
yes
rRS
├* ～BB11B1B111B (Ll<B>)
├* ～BB11B111BBB (rRS)
├* ～BB11B111BBB (Ll<B>)
├* ～BB111BBBBBB (rRS)
├* ～BB111BBBBBB (Ll<B>)
├* ～111BBBBBBBB (TLlT)
TLlT
2015/10/1
佐賀大学理工学部知能情報システム学科
23
*Turing機械 Kn
n個の1のかたまりW1, W2, …, Wnに対して
以下の処理を行う。
BW1BW2B…BWnB ├*kn BW1BW2B…BWnBW1B
no
n
L r<B>
yes
BRn+11Ln+11
Rn
2015/10/1
佐賀大学理工学部知能情報システム学科
24
Knの計算例
(n=2の場合)
B11B111B
2015/10/1
├* B11B111B (L2r<B>)
├* BB1B111B1
(BR31)
├* B11B111B1
(L31)
├* B11B111B1
(r<B>)
├* B1BB111B11
(BR31)
├* B11B111B11
(L31)
├* B11B111B11
(r<B>)
├* B11B111B11B
(R2)
佐賀大学理工学部知能情報システム学科
25
帰納的関数とTuring機械
帰納的関数を計算するTuring機械の合成
1. 初期関数を計算するTuring機械
Z(x), S(x), Uni(x1, …, xn)
2. 合成関数とTuring機械
f(x1, …, xn)=g(h1(x1, …, xn), …, hr(x1, …, xn))
3. 原始帰納で定義される関数とTuring機械
f(x1, …, xn)=g(x1, …,xn-1) (xn=0のとき)
f(x1, …, xn)=h(x1, …, xn-1, xn-1, f(x1, …, xn-1))
(xn＞0のとき)
2015/10/1
佐賀大学理工学部知能情報システム学科
26
初期関数のTuring機械
Z(x)
→r1r
BWB├* BWB1B
S(x)
→K11r BWB├* BWBW1B
Uni (x1, …, xn)
→Kn-i+1
BW1B…BWiB…BWnB├* BW1B…BWiB…BWnBWiB
2015/10/1
佐賀大学理工学部知能情報システム学科
27
合成関数とTuring機械
合成関数
f(x1, …, xn)=g(h1(x1, …, xn), …, hr(x1, …, xn))
→r1rKn+1nLnlBRH1Kn+1nH2…Kn+1nHrKr+(r-1)n
Kr+(r-2)n…KrGC
ここで、g, h1, …, hr を計算するTuring機械を
それぞれG, H1, …, Hr とする。
2015/10/1
佐賀大学理工学部知能情報システム学科
28
原始帰納で定義される関数と
Turing機械
原始帰納
f(x1, … , xn, 0)=g(x1, …,xn)
f(x1, …, xn , y´)=h(x1, …, xn, y, f(x1, …, xn, y))
ここで、g, hを計算するTuring機械をそれぞれG, Hとする。
↓
n n+1
r1rK2Kn+3 L lBR GKn+2lBl<B>yes
no
rKn+2nr1rKn+3HKn+4lBl<B>
2015/10/1
佐賀大学理工学部知能情報システム学科
no
C
yes
rKn+4n+1
29
原始帰納関数の例
x+y (plus(x, y))
plus(x, 0)=g(x)
plus(x, y)=h(x, y-1, plus(x, y-1))
g(x)=U11(x)
h(x, y, z)=S(U33(x, y, z))
2015/10/1
佐賀大学理工学部知能情報システム学科
30
g(x)とh(x, y, z)
g(x)を計算するTuring機械をGとする。
g(x) = U11(x)であるから、
Gはn=1, i=1としてK1
h(x, y, z)を計算するTuring機械をHとする。
h(x, y, z) = S(U33(x, y, z))であるから、
U33(x, y, z)に対するTuring機械 K1と
S(x)に対するTuring機械K11rを合成して、
r1rK43L3lBRK1K1K11rC
2015/10/1
佐賀大学理工学部知能情報システム学科
31
合成関数Hの計算
xByBzB
├* xByBzB1B (r1r) 引数と分離する準備
├* xByBzB1BxByBzB (K43) 引数をコピーする
├* xByBzB1BxByBzB (L3) 戻る
├* xByBzBBBxByBzB (lBR) 分離の完了
├* xByBzBBBxByBzBzB (K1) H1適用
├* xByBzBBBxByBzBzBzB (K1) H1結果の取り出し
├* xByBzBBBxByBzBzBzB(z+1)B (K11r) G適用
├* xByBzB(z+1)B (C) 計算過程クリア
2015/10/1
佐賀大学理工学部知能情報システム学科
32
求めるTuring機械は
さっき定義したGとHを使用して、
n=1より、以下のように書ける。
2
r1rK2K4L lBR GK3lBl<B>
no
rK3r1rK4HK5lBl<B>
2015/10/1
no
佐賀大学理工学部知能情報システム学科
yes
C
yes
rK52
33
ミニテスト
配布・お持ち帰り
次回に回収
講義終了時に前回の分を回収
2015/10/1
佐賀大学理工学部知能情報システム学科
34
© Copyright 2024 ExpyDoc
