チューリング機械の形式的定義および計算状況
こんばんは。前回は講義の概略をお話ししましたが、今回はチューリング機械の導入をしていこうと思います。今回の話は形式的定義および計算状況に限ったものなので、計算可能性にかかわる本質的(と思われる)な話は次回以降の記事になります。
注意
現状、 二年前の名残から図などを自前で用意しない記事構成になっていますが後ほど追加する予定です。当時はスライドの補完的な立ち位置として書いていたものなので、授業スライドを併せて見るといいかと思います。
まず、チューリング機械とはどんなものでしょうか。両側無限単一テープチューリング機械の特徴としては、
- 読み書き用の無限長のテープを持つ
- テープには無限個のマス目が存在し、入力記号列はテープ状に存在している
- 計算の初期状態として、入力記号列の書かれたマス以外は で埋められている
- 現在地のマス目を示すヘッドが存在する
- ヘッドは左右に1マスずつ動ける
- この動きを制御するための、有限状態を持つ制御部が存在する
あくまで制御部はヘッドの動きを制御するものであり、ヘッドの具体的な位置を保持しているわけではないことに注意しましょう。
非決定性チューリング機械 は以下のように形式的に記述されます。
・: 状態の有限集合 ・: 初期状態
・: テープ記号の有限集合
・: 入出力記号の集合
・: 次動作関数: (非決定性ゆえに冪集合の形となる。
決定性チューリング機械なら )
・ \ : 空白記号
・: 受理状態の集合
この中で最も馴染みのない表記は次動作関数 だと思うので、具体例を示します。
に対する次動作関数 の値が「 に遷移し、 を に書き換えた後、ヘッドを左に動かす」か、「 に遷移し、 を に書き換えた後、ヘッドを右に動かす」といった動作のとき、以下のように表現できます。
チューリングマシンの計算状況
ここからは計算状況について書きます。
記述の仕方は様々なものがありますが、ここではある瞬間での計算状況 を以下のように表すこととします。
は 以外でテープ上の一番左の文字から一番右の文字までを繋げた文字列を指し、 は を 番目と見た時のヘッド位置を示します。例えば であれば の文字が書かれているマス目をヘッドが指していることになります。
また、 はテープを左から見た時、 以外の文字が出てくる最初の位置の文字となります。 の間に が入っていても、間を詰めるようなことはしません。
において、 を に書き換えると何が起こるのでしょうか。この場合は、添え字の 番目の位置が変わります。具体的には、 が になります。それに伴い があった位置の添え字は となります。つまり新たな計算状況 は、チューリング機械の状態が となるとすると になります。
ところで に関してですが、確かにスライドでは入出力記号と書かれていますが(現在はどうなんでしょう)、 ということなので個人的にはぼんやりしてる印象を受けます。
さて、上記のような添え字の急激なジャンプを防ぎたいとします。問題となっているのは を新たに書き込める点なので、
とすると防げることが分かります(この辺りをどう定義するかは自由だと思います、本質的には後の話に関わってこないので)。
最後に停止や受理など細々したお話をします。チューリング機械は、
- ある計算状況について次の動作が定義されない時、はで停止する
- で停⽌するとき、はを受理するという
- チューリング機械が認識(受理)する⾔語 とは、に受理される記号列全体のなす⾔語
- チューリング機械は永遠に停止しないこともある
最後はかなり重要で、これがいわゆる決定可能というところに深く関わってきます。
今回はここまでにします。次回はチューリング機械の様々なモデルを扱います。
2018/12/03, 22:36 それに伴いがあった位置の添え字はとなります。
→それに伴いがあった位置の添え字はとなります。
次動作関数の定義に言及した文脈の「~とすれば防げます。」の後にに関する補足説明を追加
2018/1/19, 18:46 それに伴いがあった位置の添え字はとなります。→それに伴いがあった位置の添え字はとなります。
2020/10/07, 19:36 全体的に文章や表現を見直しました