チューリングマシン
Turing Mathine, TM
つまり、物理的な機械があるわけではない
有限オートマトンでは判定できないものも判定できる
有限オートマトンに無限に読み書き可能なテープがあるような感じ
受理状態または拒否状態で停止するか、もしくは停止しない
レジスタの状態($ q_n)と、テープの状態($0011__)を持っている
できる、というかそうすることが多い
チューリングマシンの定義
7つ組$ M=\left\langle Q, \Gamma, b, \Sigma, \delta, q_{\mathrm{init}}, q_{\mathrm{acc}}\right\rangleで定義される ref $ Q: 状態の有限集合
初期状態$ q_{\mathrm{init}}\in Q
受理状態$ q_{\mathrm{acc}}\in Q
$ \Gamma: 記号の有限集合
テープ上に現れる記号
空白も、終端記号$も含む
空白記号$ b\in\Gamma
brankのbmrsekut.icon
$ \Sigma:入力記号の集合
$ \Gamma-\{b\}の部分集合
空白は含めない
$ Q\times\Gamma\rightarrow Q\times\Gamma\times\{\mathrm{left}, \mathrm{right}\}の部分関数 左か右かに加えて、「その場に留まる」を表す記号を含めることもあるmrsekut.icon
$ \delta(q,a)=(q',a',m)
$ qは状態
$ aは$ qにかかれている文字
$ mは方向。左か右
引数が入力、出力が書き込み
物理的なチューリングマシン作るときの構成要素
有限制御部
有限個の状態を持ち、現在どの状態であるかを記憶
内部状態qを保持する
テープ
複数のセルに分割されており、1つのセルに1つの記号が格納される
任意の長さに拡張できる一次元配列のイメージ
ストレージと入力の役割を果たす
任意の順序で任意の回数の読み込み、書き込み、上書きができる
ヘッド
現在指しているセルの内容の、読み取り、書き込み、左右への移動が可能
1回で移動できるのは1セルのみ
動作開始時は入力記号列wの左端
つまり一文字目
テープと状態を形式的に表す表記
例えばテープが以下のようなとき
code:state
テープ: 0 1 2 3 4 5 6 _ _ _
↑
q3
こう表記する「$ 0q_3 123456」
つまりヘッダより左側の文字を$ q_nの左に、ヘッダが指しているものとそれより右側のものを$ q_nの右に書く
終端記号$は書かない
遷移している感じは以下のように書く
$ q_0 01\vdash X q_11\vdash q_2XY\vdash Xq_0Y\vdash XYq_3\Box\vdash XY\Box q_\mathrm{accept}\Box
$ \vdashで状態の切れ目、$ \Boxは空白記号を表す
まじで1個でもミスると詰む
移動の具体例
http://www.akita-pu.ac.jp/system/elect/ins/kusakari/japanese/teaching/InfoMath/2005/note/5/Slide07.gif
入力が$ \Sigma=\{0,0,1,1\}のとき
様相は以下のようになる
$ q_00011\vdash Xq_1011\vdash X0q_111\vdash Xq_20Y1\vdash q_2X0Y1\vdash Xq_00Y1\vdash XXq_1Y1\vdash XXYq_11\vdash \\XXq_2YY\vdash Xq_2XYY \vdash XXq_0YY\vdash XXYq_3Y\vdash XXYYq_3\vdash XXYYBq_4
このマシンの受理言語は$ L(M)=\{0^n,1^n\}
無限ループ
様相に過去に出てきたものが再び出てくると無限ループになる
例えば$ XY q_3 1\vdash Xq_4Y1\vdash XY q_31となると、$ XYq_31が2回目出てきている
停止しない
受理しない
チューリングマシン同士の結合
チューリングマシン$ M,Nを結合するとする
いくつかの状態を追加して以下のような動作をする機械を作る
$ Mの開始状態から$ Mの動作を行い、それが停止したらヘッドをテープ状の文字列の左端まで移動させてから、$ Nの開始状態へ進んで$ Nの動作を行う
正規表現の$ 0^n1^n
0と1がn個並んでいる入力
任意の自然数nに対し、$ 0^n1^nを受理し、それ以外の入力は受理しない
ことが証明されている(?)
$ \{w|w=w^R\}
wは0と1で構成されたビット列
$ w^Rはビット列wを逆転させたビット列
回文みたいな
ちょっとよくわからんmrsekut.icon
チューリングマシンは入力$ wに対して、以下のいずれかの動作を行う
$ q_{\mathrm{accept}}に到達し、停止。=受理
$ q_{\mathrm{reject}}に到達し、停止。=拒否
永遠に停止しない=無限ループ
計算できる」の定義
問題に対して、解を答える、または解がないと答えるアルゴリズムが存在する
語$ wの言語$ L(M)の所属判定問題の場合、$ wが$ L(M)に属するときは$ wを受理し、そうでないときは$ wを拒否して停止するチューリングマシンが存在
チューリングマシンの種類
Decider
ある言語$ Lが存在し、任意の入力$ wに対し、$ w\in Lのときは、$ q_{\mathrm{accept}}に到達して停止し、$ w\notin Lのときは$ q_{\mathrm{reject}}に到達して停止するチューリングマシン
つまり、絶対に「受理」か「拒否」のいずれかの状態に到達する
Recognizerでもある
Recognizer
ある言語$ Lが存在し、任意の入力$ wに対し、$ w\in Lのとき$ q_{\mathrm{accept}}に到達して停止するチューリングマシン
属していないときは、停止しない、かもしれない
つまり「受理」か「拒否」か「それ以外」のいずれかになる
「それ以外」は無限ループとか、行き詰まり状態(該当する規則がない)になる、とか
Decider $ \subset Recognizerなのかmrsekut.icon
ある言語$ LのDeciderが存在するとき$ Lは決定可能であると言う 「ある言語」が「決定可能」なのね。主語と述語は。
これって一つでも存在すればいいのか？
ある言語$ LのRecognizerが存在するとき$ Lは半決定可能であると言う $ Lが決定可能であるとき、$ Lは半決定可能である
Decider $ \subset Recognizerなので。
だから、決定可能$ \subset半決定可能になるのかmrsekut.icon
問. $ Lを「"01"を含む語の集合」とするとき、$ Lは半決定可能であることを示せ
$ LがRecognizerであることを示せばいい
$ LのRecognizerを実際に作る
状態遷移図を書いて示せばいい
思考の手順としては
acc,rejが必要かどうかを考えた上で
問を満たす適当な凡例を挙げて
それを満たすように図を書けばいい
今回は$ Lは半決定可能であればいいので、accは必須だが、rejはどっちでもいい
https://gyazo.com/493e0f4019bfc583e80a3e07c9d4d892
問."1"で始まる語の集合が決定可能であることを示せ
Deciderであることを示せばいい
https://gyazo.com/0ec22179d0713ad0cad87f912f78c614
問. "0"で終わる語の集合が決定可能であることを示せ
https://gyazo.com/445642d1806650f85de646fe923b67b4
チューリングマシンは入れ子にできる
小さいチューリングマシンを組み合わせて大きなチューリングマシンを作ることができる
例えばその中身の全てのチューリングマシンがacceptしたら、その大きなものもaccespt
中身のチューリングマシンの一つでもがrejectすれば、その大きなものもreject
とか。
チューリングマシンの変種
テープの本数を増やしたもの
テープが1本のものに比べて少ないステップ数で作業ができるようになる
チューリングマシンの作りやすさ、計算時間に対して寄与する
しかし、計算可能性は1本のときと変わらない
計算可能なものが増えるわけではない
0, 1, X以外の文字の使用を禁止したもの
通常のものより使用できる文字数を制限する
しかし、計算可能性は変わらない
計算可能なものが減るわけではない
例えば、2つのチューリングマシンと、その使える文字を以下とすると
$ M=\{0,1,X,a,b,c\}
$ M'=\{0,1,X\}
以下のように表せばいい
table:MとM'の対応
Mの文字 0 1 X a b c
M'での表現 00 01 0X 10 11 1X
$ M'のテープ上の2個のセルを、$ Mのテープ上の1個のセルとみなす
$ Mの動作を模倣するように$ M'を作ればいい
この例ではステップ数は2倍になるが、同じものを計算できる
各時点の状態とヘッドが指している文字に対して、次の動作の候補が複数あっても良い
関連
参考