チューリング機械の動作の追跡

遷移表で与えられた 1 テープ決定性チューリング機械について、状態・テープの内容・ヘッドの位置（様相）を 1 ステップずつ追跡し、停止するまでのステップ数・停止時のテープの内容・受理か拒否かを求められる

前提

決定性有限オートマトンの動作と受理判定（大学数学オートマトン・形式言語）

説明

チューリング機械は、DFA に「テープへの書き込み」と「ヘッドの左右への移動」を加えた計算のモデルです。この技能では、遷移表に従って機械の様子（状態・テープの内容・ヘッドの位置）を 1 ステップずつ書き出します。これにより、停止するまでのステップ数、停止時のテープの内容、受理か拒否かを求められるようになります。機械が何を計算しているのかを確かめるときや、計算量（ステップ数）を数えるときの基本になります。

なぜそうしてよいのか

DFA では、入力を左から 1 文字ずつ読み、そのたびに $δ (q, a)$ で状態を更新しました。1 テープ決定性チューリング機械も、「今の状態 $q$ と、ヘッドが読んでいる記号 $a$ だけで次の動作が 1 通りに決まる」という点は同じです。違うのは、遷移が $δ (q, a) = (p, b, D)$ の形をしていることです。これは「状態を $p$ に変え、今いるマスの $a$ を $b$ に書き換え、ヘッドを $D$ の向きに 1 マス動かす」という意味で、 $D = L$ なら左へ、 $D = R$ なら右へ動きます。テープは右に無限に続き、入力のあとのマスには空白記号 $⊔$ が並んでいます。ヘッドは最初、入力の最も左の文字の上にあります。以下ではこの流儀を使います。

ある時点の機械の様子は、状態、テープの内容、ヘッドの位置の 3 つで完全に表せます。この 3 つの組を様相と呼びます。ここでは様相を $u q v$ と書きます。これは「テープの内容が $uv$ （右に続く空白は省略）で、状態が $q$ 、ヘッドは $v$ の先頭の文字の上にある」という意味です。決定性なので、1 つの様相から次の様相はただ 1 つに決まります。そのため、初期様相 $q_{0} w$ から遷移表を繰り返し当てはめていけば、計算の全体を機械的に再現できます。

DFA は入力を読み終えた時点で止まりました。これに対してチューリング機械は、入力の端に来ても止まりません。空白 $⊔$ を読む遷移があれば、そのまま動き続けます。止まるのは、受理状態 $q_{a cc}$ か拒否状態 $q_{r e j}$ に入った瞬間だけです（流儀によっては、遷移が定義されていない組に出会ったときも拒否として止まります）。どちらにも入らず、永遠に止まらないこともあります。ステップ数とは、遷移を適用した回数のことです。

手順

初期様相 $q_{0} w$ を書き、これを第 0 ステップとする。ヘッドは $w$ の最初の文字の上にある。
今の状態 $q$ と、ヘッドの下の記号 $a$ を読み取る（入力の外なら $a = ⊔$ ）。遷移表で $δ (q, a) = (p, b, D)$ を探す。
まず今いるマスの $a$ を $b$ に書き換え、次にヘッドを $D$ の向きに 1 マス動かし、状態を $p$ にする。こうして次の様相を書き、ステップ数を 1 増やす。左端で $D = L$ のときは、ヘッドはその場に留まる。
新しい状態が $q_{a cc}$ または $q_{r e j}$ なら停止する。そうでなければ手順 2 に戻る。
停止したら、次の 3 つをまとめる：ステップ数、そのときのテープの内容（空白を除いた部分）、受理か拒否か（停止した状態が $q_{a cc}$ か $q_{r e j}$ か）。

例題

次の 1 テープ決定性チューリング機械 $M$ を考える。
- 状態の集合： ${q_{0}, q_{1}, q_{a cc}, q_{r e j}}$ （初期状態 $q_{0}$ 、受理状態 $q_{a cc}$ 、拒否状態 $q_{r e j}$ ）
- 入力アルファベット： ${0, 1}$
- テープ記号： ${0, 1, ⊔}$ （ $⊔$ は空白）

テープは右に無限に続き、初めヘッドは入力の最も左の文字の上にある。 $q_{a cc}$ または $q_{r e j}$ に入った時点で停止する。左端で左へ動こうとしたときは、その場に留まる。遷移 $δ (q, a) = (p, b, D)$ は次の表のとおりである（ $D$ は $L$ か $R$ ）。

状態	$0$	$1$	$⊔$
$q_{0}$	$(q_{0}, 0, R)$	$(q_{0}, 1, R)$	$(q_{1}, ⊔, L)$
$q_{1}$	$(q_{a cc}, 1, R)$	$(q_{1}, 0, L)$	$(q_{r e j}, ⊔, R)$

入力 $1011$ を与えたとき、 $M$ が停止するまでのステップ数を求めよ。

例題の解答

手順 1：初期様相は $q_{0} 1011$ で、これを第 0 ステップとする。

手順 2〜4 を繰り返す。
- 第 1 ステップ： $q_{0}$ で $1$ を読む。 $δ (q_{0}, 1) = (q_{0}, 1, R)$ なので、 $1$ はそのままで右へ動く。様相は $1 q_{0} 011$ 。
- 第 2 ステップ： $q_{0}$ で $0$ を読む。 $δ (q_{0}, 0) = (q_{0}, 0, R)$ より、様相は $10 q_{0} 11$ 。
- 第 3 ステップ： $q_{0}$ で $1$ を読み、右へ動く。様相は $101 q_{0} 1$ 。
- 第 4 ステップ： $q_{0}$ で $1$ を読み、右へ動く。様相は $1011 q_{0} ⊔$ 。ヘッドは入力の外に出たが、状態が $q_{a cc}$ でも $q_{r e j}$ でもないので停止しない。
- 第 5 ステップ： $q_{0}$ で $⊔$ を読む。 $δ (q_{0}, ⊔) = (q_{1}, ⊔, L)$ より、様相は $101 q_{1} 1$ 。
- 第 6 ステップ： $q_{1}$ で $1$ を読む。 $δ (q_{1}, 1) = (q_{1}, 0, L)$ なので、今のマスを $0$ に書き換えてから左へ動く。様相は $10 q_{1} 10$ 。
- 第 7 ステップ： $q_{1}$ で $1$ を読む。 $0$ に書き換えて左へ動く。様相は $1 q_{1} 000$ 。
- 第 8 ステップ： $q_{1}$ で $0$ を読む。 $δ (q_{1}, 0) = (q_{a cc}, 1, R)$ なので、 $1$ に書き換えて右へ動く。様相は $11 q_{a cc} 00$ 。

手順 4：状態が $q_{a cc}$ になったので停止する。

手順 5：遷移を適用した回数は 8 回である。停止時のテープは $1100$ で、結果は受理である。この入力に限っていえば、 $101 1_{(2)} = 11$ が $110 0_{(2)} = 12$ に変わっている。ただし、どの入力でも 1 を足すわけではない。たとえば入力 $11$ では、停止時のテープは $10$ になる。

よって答えは 8 ステップである。

答え: $8$

よくある誤り

初期様相 $q_{0} 1011$ も 1 ステップと数えてしまう誤り。正しくは、ステップ数は遷移を適用した回数なので、初期様相は第 0 ステップである。例題の答えは $9$ ではなく $8$ 。
ヘッドを先に動かし、移動先のマスに書き込んでしまう誤り。正しくは、 $δ (q, a) = (p, b, D)$ では「今いるマスに $b$ を書く → $D$ の向きに動く」の順である。例えば $101 q_{1} 1$ に $δ (q_{1}, 1) = (q_{1}, 0, L)$ を適用する場合を考える。正しくは 4 マス目を $0$ にしてから左へ動くので $10 q_{1} 10$ になる。先に左へ動いて 3 マス目に $0$ を書くと $10 q_{1} 01$ になってしまう。
DFA と同じように、入力を読み終えた時点で止まると考えてしまう誤り。正しくは、チューリング機械は $⊔$ を読んでも遷移があれば動き続け、止まるのは $q_{a cc}$ か $q_{r e j}$ に入ったときだけである。例題では $1011 q_{0} ⊔$ のあとも 4 ステップ続く。
受理か拒否かを、停止時のテープの内容で判断してしまう誤り。正しくは、停止したときの状態が $q_{a cc}$ なら受理、 $q_{r e j}$ なら拒否であり、テープに何が書いてあるかは関係ない。また、どちらの状態にも入らずに永遠に動き続ける場合もあり、そのときは停止しない。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

状態	読む記号	書く記号	ヘッドの移動	次の状態
$q_{0}$	$1$	$1$	$R$	$q_{0}$
$q_{0}$	$+$	$1$	$R$	$q_{1}$
$q_{1}$	$1$	$1$	$R$	$q_{1}$
$q_{1}$	$⊔$	$⊔$	$L$	$q_{2}$
$q_{2}$	$1$	$⊔$	$L$	$h$

状態	$1$	$+$	$⊔$
$q_{0}$	$(q_{0}, 1, R)$	$(q_{1}, 1, R)$	—
$q_{1}$	$(q_{1}, 1, R)$	—	$(q_{2}, ⊔, L)$
$q_{2}$	$(h, ⊔, L)$	—	—

この技能を使う問題

難易度 3（期末試験の応用レベル）

次の 1 テープ決定性チューリング機械 $M$ を考える。

状態の集合: ${q_{0}, q_{1}, q_{2}, q_{3}, q_{acc}, q_{rej}}$ 。初期状態は $q_{0}$ 、受理状態は $q_{acc}$ 、拒否状態は $q_{rej}$
入力アルファベット: ${a, b}$ 、テープアルファベット: ${a, b, X, Y, ⊔}$ （ $⊔$ は空白記号）
遷移関数 $δ$ は次の表のとおり。表の「 $(p, c, D)$ 」は「状態を $p$ に変え、いま読んでいるマスに $c$ を書き、ヘッドを $D$ の向き（ $R$ は右、 $L$ は左）に 1 マス動かす」ことを表す。表にない（状態, 記号）の組では、 $M$ は $q_{rej}$ に移って停止する。

状態	読む記号	遷移
$q_{0}$	$a$	$(q_{1}, X, R)$
$q_{0}$	$Y$	$(q_{3}, Y, R)$
$q_{1}$	$a$	$(q_{1}, a, R)$
$q_{1}$	$Y$	$(q_{1}, Y, R)$
$q_{1}$	$b$	$(q_{2}, Y, L)$
$q_{2}$	$a$	$(q_{2}, a, L)$
$q_{2}$	$Y$	$(q_{2}, Y, L)$
$q_{2}$	$X$	$(q_{0}, X, R)$
$q_{3}$	$Y$	$(q_{3}, Y, R)$
$q_{3}$	$⊔$	$(q_{acc}, ⊔, R)$

テープは右に無限に続き、はじめは入力文字列が左端のマスから書かれ、残りのマスはすべて $⊔$ である。ヘッドははじめ左端のマス（入力の 1 文字目）にあり、状態は $q_{0}$ である。 $M$ は $q_{acc}$ または $q_{rej}$ に入った時点で停止する。

入力 $aaabbb$ に対して $M$ を動かしたとき、 $M$ が停止するまでに適用される遷移の回数（停止状態に入る遷移も 1 回と数える）を求めよ。

難易度 3（期末試験の応用レベル）
両側に無限に続く 1 本のテープをもつ決定性チューリング機械 $M$ を考える。テープの各セルを整数で番号付けする（セル $i$ の右隣はセル $i + 1$ ）。入力記号の集合は ${0, 1}$ 、テープ記号の集合は ${0, 1, ⊔}$ （ $⊔$ は空白記号）、状態の集合は ${q_{0}, q_{1}, q_{h}}$ で、初期状態は $q_{0}$ 、停止状態は $q_{h}$ である。遷移関数 $δ$ は次の表で与えられる（ $δ (q, s) = (q^{'}, s^{'}, D)$ は、状態 $q$ でヘッドが記号 $s$ を読んだとき、そのセルに $s^{'}$ を書き、ヘッドを $D$ の向き（ $L$ は左、 $R$ は右）に 1 セル動かし、状態 $q^{'}$ に移ることを表す）。
状態記号 $0$ 記号 $1$ 記号 $⊔$
$q_{0}$ $(q_{0}, 0, R)$ $(q_{0}, 1, R)$ $(q_{1}, ⊔, L)$
$q_{1}$ $(q_{h}, 1, L)$ $(q_{1}, 0, L)$ $(q_{h}, 1, L)$
$q_{h}$ からの遷移はなく、 $M$ は状態 $q_{h}$ に入った時点で停止する。遷移関数を 1 回適用することを 1 ステップと数える。
$n$ を正の整数とし、入力 $w = w_{1} w_{2} \dots w_{n}$ （各 $w_{i} \in {0, 1}$ ）を、セル $1, 2, \dots, n$ に $w_{1}, \dots, w_{n}$ を書き、それ以外のセルをすべて $⊔$ とし、ヘッドをセル $1$ に置いて状態 $q_{0}$ から動かす。 $w$ を左端を最上位の桁とする 2 進数として読んだ値を $N = \sum_{i = 1}^{n} w_{i} 2^{n - i}$ とし、 $w$ の末尾に連続して並ぶ $1$ の個数（ $w_{n} = 0$ なら $0$ ）を $t$ とする。
このとき、 $M$ はちょうど $n + t + 2$ ステップで停止し、停止時のテープ上の $⊔$ でない記号は連続したいくつかのセルに並んで 1 つの文字列 $x$ をなし、 $x$ を左端を最上位の桁とする 2 進数として読んだ値が $N + 1$ であることを証明せよ。ここで $x$ の先頭に $0$ が並んでいてもよく（たとえば $w = 0010$ なら $x = 0011$ ）、 $x$ が置かれるセルの範囲は入力が置かれたセル $1, \dots, n$ と一致するとは限らない。

難易度 4（大学院入試の標準レベル）

入力アルファベット $Σ = {a, b}$ 、テープ記号の集合 $Γ = {a, b, X, Y, ⊔}$ （ $⊔$ は空白記号）をもつ 1 テープ決定性チューリング機械 $M$ を考える。

状態の集合は ${q_{0}, q_{1}, q_{2}, q_{3}, q_{acc}, q_{rej}}$ であり、初期状態は $q_{0}$ 、受理状態は $q_{acc}$ 、拒否状態は $q_{rej}$ である。 $M$ は $q_{acc}$ または $q_{rej}$ に入った時点で停止する。
テープのマスには左から順に番号 $1, 2, 3, \dots$ が付いており、入力 $w$ はマス $1$ から $∣ w ∣$ に 1 文字ずつ書かれ、ほかのマスはすべて $⊔$ である。最初、ヘッドはマス $1$ にある。
遷移関数 $δ$ は次の表で与えられる。表の $(p, c, D)$ は「状態 $p$ に移り、いまのマスに記号 $c$ を書き、ヘッドを $D$ の向きに 1 マス動かす（ $R$ は右、 $L$ は左）」ことを表す。

状態	$a$	$b$	$X$	$Y$	$⊔$
$q_{0}$	$(q_{1}, X, R)$	$(q_{rej}, b, R)$	$(q_{rej}, X, R)$	$(q_{3}, Y, R)$	$(q_{acc}, ⊔, R)$
$q_{1}$	$(q_{1}, a, R)$	$(q_{2}, Y, L)$	$(q_{rej}, X, R)$	$(q_{1}, Y, R)$	$(q_{rej}, ⊔, R)$
$q_{2}$	$(q_{2}, a, L)$	$(q_{rej}, b, R)$	$(q_{0}, X, R)$	$(q_{2}, Y, L)$	$(q_{rej}, ⊔, R)$
$q_{3}$	$(q_{rej}, a, R)$	$(q_{rej}, b, R)$	$(q_{rej}, X, R)$	$(q_{3}, Y, R)$	$(q_{acc}, ⊔, R)$

遷移関数を 1 回適用することを 1 ステップと数える（ $q_{acc}$ や $q_{rej}$ に移る遷移も 1 ステップと数える）。

$m, n$ を $m > n \geq 1$ を満たす整数とする。入力 $w = a^{m} b^{n}$ （ $a$ を $m$ 個並べた後に $b$ を $n$ 個並べた文字列）に対して $M$ を動かしたとき、 $M$ が停止するまでのステップ数を $m, n$ の式で求めよ。

難易度 4（大学院入試の標準レベル）
両側に無限に続くテープを 1 本もつ決定性チューリング機械 $M$ を考える。
- 状態の集合: ${q_{0}, q_{1}, q_{2}, q_{3}, h}$ 。初期状態は $q_{0}$ 、停止状態は $h$ （ $h$ からの遷移はなく、 $h$ に入った時点で $M$ は停止する）
- 入力アルファベット: ${1}$ 、テープ記号の集合: ${1, ⊔}$ （ $⊔$ は空白記号）
- 遷移関数 $δ$ は次の表で与えられる。表の「(書く記号, ヘッドの移動, 次の状態)」で、 $R$ は右へ 1 マス、 $L$ は左へ 1 マス動くことを表す。
状態読んだ記号 $1$ 読んだ記号 $⊔$
$q_{0}$ $(⊔, R, q_{1})$ $(⊔, R, h)$
$q_{1}$ $(1, R, q_{1})$ $(⊔, L, q_{2})$
$q_{2}$ $(⊔, L, q_{3})$ $(⊔, R, h)$
$q_{3}$ $(1, L, q_{3})$ $(⊔, R, q_{0})$
$n$ を 0 以上の整数とする。はじめ、テープには連続する $n$ マスに $1$ が書かれ（入力 $1^{n}$ ）、それ以外のマスはすべて $⊔$ である。ヘッドは入力の左端のマス（ $n = 0$ のときは任意の 1 マス）にあり、状態は $q_{0}$ である。
遷移関数を 1 回適用することを 1 ステップと数える（ $h$ に入る遷移も 1 ステップに数える）。入力 $1^{n}$ に対して $M$ が停止するまでのステップ数を $n$ の式で求めよ。

状態	読んだ記号 $1$	読んだ記号 $⊔$
$q_{0}$	$(⊔, R, q_{1})$	$(⊔, R, h)$
$q_{1}$	$(1, R, q_{1})$	$(⊔, L, q_{2})$
$q_{2}$	$(⊔, L, q_{3})$	$(⊔, R, h)$
$q_{3}$	$(1, L, q_{3})$	$(⊔, R, q_{0})$

この技能の次に学べること

多項式時間多対一帰着の性質（大学院数学計算理論・ラムダ計算）