オートマトン・形式言語の問題

難易度 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$ と一致するとは限らない。

この問題で使うもの

チューリング機械の動作の追跡（説明と入口の問題）

この問題を解けるようになるまで（2 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$M$ の動作を「右端まで進む段階」と「右から繰り上がりを処理する段階」に分け、それぞれの段階で何ステップ後に状態・ヘッド位置・テープがどうなっているかを帰納法で示すとよい。

ヒント 2

不変条件の例： $k$ ステップ後（ $0 \leq k \leq n$ ）は状態 $q_{0}$ ・ヘッドはセル $k + 1$ ・テープは不変。 $n + 1 + j$ ステップ後（ $0 \leq j \leq t$ ）は状態 $q_{1}$ ・ヘッドはセル $n - j$ ・セル $n - j + 1, \dots, n$ だけが $0$ に変わっている。

ヒント 3

$n + 1$ ステップ目で空白を読んで $q_{1}$ に移り、その後は末尾の $t$ 個の $1$ を $0$ に変えながら左へ進む。 $n + t + 1$ ステップ後にヘッドが読む記号は、 $t < n$ なら $0$ 、 $t = n$ ならセル $0$ の $⊔$ である。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$t$ の定義から、 $w_{n - t + 1}, \dots, w_{n}$ がすべて $1$ で、 $t < n$ なら $w_{n - t} = 0$ であることを確認している（1 点）
$0 \leq k \leq n$ について、 $k$ ステップ後の状態 $q_{0}$ ・ヘッド位置 $k + 1$ ・テープ不変を帰納法で示し、 $n + 1$ ステップ目に $⊔$ を読んで $q_{1}$ ・ヘッドがセル $n$ に移ることを述べている（3 点）
$0 \leq j \leq t$ について、 $n + 1 + j$ ステップ後に状態 $q_{1}$ ・ヘッドがセル $n - j$ にあり末尾 $j$ 個が $0$ に変わっていることを、読む記号が $1$ であることを根拠に帰納法で示している（3 点）
$t < n$ と $t = n$ の場合に分け、それぞれ $0$ またはセル $0$ の $⊔$ を読んで $1$ を書き、 $n + t + 2$ ステップ目で初めて停止することを示している（1 点）
停止時のテープの文字列（セル $1$ 〜 $n$ の $u 1 0^{t}$ 、またはセル $0$ 〜 $n$ の $1 0^{n}$ ）の値を計算して $N + 1$ に等しいことを示し、空白でない記号が連続していることを述べている（2 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

$t$ の定義から $0 \leq t \leq n$ であり、 $w_{n - t + 1} = \dots = w_{n} = 1$ である。さらに $t < n$ のときは $w_{n - t} = 0$ である（ $w_{n - t} = 1$ なら末尾に連続する $1$ が $t + 1$ 個以上となり $t$ の定義に反する）。

補題 1（右へ走査する段階）　 $0 \leq k \leq n$ を満たす整数 $k$ について、 $k$ ステップ後の時点で $M$ は停止しておらず、状態は $q_{0}$ 、ヘッドはセル $k + 1$ にあり、テープの内容は初期状態から変わっていない。

$k$ についての帰納法で示す。 $k = 0$ のときは初期設定そのものである。 $0 \leq k < n$ で成り立つと仮定する。このときヘッドのあるセル $k + 1$ は $1 \leq k + 1 \leq n$ を満たすので、そこには $w_{k + 1} \in {0, 1}$ が書かれている。表より $δ (q_{0}, 0) = (q_{0}, 0, R)$ 、 $δ (q_{0}, 1) = (q_{0}, 1, R)$ なので、次のステップでは同じ記号を書き戻し（テープは変わらない）、ヘッドはセル $k + 2$ に動き、状態は $q_{0}$ のままである（ $q_{h}$ に入らないので停止しない）。よって $k + 1$ でも成り立つ。

$n + 1$ ステップ目　補題 1 で $k = n$ とすると、 $n$ ステップ後は状態 $q_{0}$ 、ヘッドはセル $n + 1$ にあり、そこは $⊔$ である。 $δ (q_{0}, ⊔) = (q_{1}, ⊔, L)$ より、 $n + 1$ ステップ後は状態 $q_{1}$ （停止していない）、ヘッドはセル $n$ 、テープは初期状態のままである。

補題 2（繰り上がりの段階）　 $0 \leq j \leq t$ を満たす整数 $j$ について、 $n + 1 + j$ ステップ後の時点で $M$ は停止しておらず、状態は $q_{1}$ 、ヘッドはセル $n - j$ にあり、テープはセル $n - j + 1, \dots, n$ が $0$ に書き換わっている以外は初期状態と同じである。

$j$ についての帰納法で示す。 $j = 0$ は直前に示したとおりである（書き換わったセルはない）。 $0 \leq j < t$ で成り立つと仮定する。ヘッドのあるセル $n - j$ は、 $j < t \leq n$ より $n - t + 1 \leq n - j \leq n$ を満たし、まだ書き換えられていないので $w_{n - j} = 1$ が書かれている。 $δ (q_{1}, 1) = (q_{1}, 0, L)$ より、次のステップでセル $n - j$ は $0$ に書き換わり、ヘッドはセル $n - j - 1$ に動き、状態は $q_{1}$ のままである（停止しない）。よって $n + 1 + (j + 1)$ ステップ後に $j + 1$ についての主張が成り立つ。

停止のステップ　補題 2 で $j = t$ とすると、 $n + t + 1$ ステップ後は状態 $q_{1}$ 、ヘッドはセル $n - t$ にあり、セル $n - t + 1, \dots, n$ は $0$ 、ほかのセルは初期状態のままである。 $t < n$ か $t = n$ かで場合分けする（ $0 \leq t \leq n$ なのでこれで尽きる）。

(i) $t < n$ のとき：セル $n - t$ は $1 \leq n - t \leq n$ の範囲にあり、書き換えられていないので $w_{n - t} = 0$ が書かれている。 $δ (q_{1}, 0) = (q_{h}, 1, L)$ より、次のステップでそこに $1$ を書いて $q_{h}$ に入り停止する。停止時のテープは、セル $1, \dots, n$ に $x = w_{1} \dots w_{n - t - 1} 1 0^{t}$ が書かれ、ほかはすべて $⊔$ である。 $u = w_{1} \dots w_{n - t - 1}$ の 2 進数としての値を $U$ （ $u$ が空、すなわち $t = n - 1$ なら $U = 0$ ）とすると、
$N = U \cdot 2^{t + 1} + 0 \cdot 2^{t} + (2^{t - 1} + \dots + 2 + 1) = U \cdot 2^{t + 1} + 2^{t} - 1$
であり（ $t = 0$ のとき括弧内は空の和で $0$ ）、 $x$ の値は $U \cdot 2^{t + 1} + 1 \cdot 2^{t} = N + 1$ である。 $u$ の先頭に $0$ があれば $x$ の先頭にも $0$ が並ぶが、それらの桁は値に寄与しない。

(ii) $t = n$ のとき：ヘッドはセル $0$ にあり、そこは初期状態のまま $⊔$ である。 $δ (q_{1}, ⊔) = (q_{h}, 1, L)$ より、次のステップでセル $0$ に $1$ を書いて停止する。このとき $w = 1^{n}$ なので $N = 2^{n} - 1$ であり、停止時のテープはセル $0, 1, \dots, n$ に $x = 1 0^{n}$ が書かれ、ほかはすべて $⊔$ である。 $x$ の値は $2^{n} = N + 1$ である。

どちらの場合も、 $M$ は $n + t + 1$ ステップ後の次の 1 ステップ、すなわちちょうど $n + t + 2$ ステップ目で初めて $q_{h}$ に入って停止する（補題 1, 2 と $n + 1$ ステップ目の考察より、それ以前には停止していない）。また停止時の $⊔$ でない記号は連続したセル（(i) ではセル $1$ 〜 $n$ 、(ii) ではセル $0$ 〜 $n$ ）に並び、その文字列 $x$ を 2 進数として読んだ値は $N + 1$ である。以上で証明が終わる。 $■$

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる

関連する問題

状態	読んだ記号 $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})$

難易度 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$ の式で求めよ。

難易度 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 回と数える）を求めよ。