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

難易度 1教科書の例題レベル大学数学オートマトン・形式言語

右方向に無限に続くテープを 1 本もつ決定性チューリング機械 $M$ を考える。

入力アルファベット: $Σ = {1, +}$
テープ記号の集合: $Γ = {1, +, ⊔}$ （ $⊔$ は空白記号）
状態の集合: ${q_{0}, q_{1}, q_{2}, h}$ 。初期状態は $q_{0}$ 、停止状態は $h$ である。 $h$ からの遷移はなく、 $M$ は状態 $h$ に入った時点で停止する。
遷移関数 $δ$ は次の表のとおりである。 $δ (q, s) = (q^{'}, s^{'}, D)$ は「状態 $q$ でヘッドが記号 $s$ を読んでいるとき、そのマスに $s^{'}$ を書き、ヘッドを $D$ の向き（ $R$ は右へ 1 マス、 $L$ は左へ 1 マス）に動かし、状態を $q^{'}$ にする」という意味である。表にない組は、以下の計算では現れない。

状態	読む記号	書く記号	ヘッドの移動	次の状態
$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$

最初、テープの左端から順に入力 $11 + 111$ が書かれ、それより右のマスはすべて $⊔$ である。ヘッドは左端のマス（入力の 1 文字目）にあり、状態は $q_{0}$ である。遷移を 1 回行うことを 1 ステップと数えるとき、 $M$ が停止するまでのステップ数を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

チューリング機械の動作の追跡を使います。DFA で状態をたどったのと同じように、「状態・テープの内容・ヘッドの位置」を 1 ステップずつ書き出しましょう。

ヒント 2

各ステップでは、今の状態とヘッドが読んでいる記号の組で遷移表の行を 1 つ選びます。 $q_{0}$ は $1$ を読む間は右へ進み続け、 $+$ を読むと $1$ に書きかえて $q_{1}$ に移ります。

ヒント 3

ステップ 3 で $+$ が $1$ に変わり、状態 $q_{1}$ ・ヘッドはマス $3$ になります。その後 $q_{1}$ は $1$ を 3 個読んで右へ進み、マス $6$ の $⊔$ に着きます。そこから先の遷移を数えましょう。

答えと解説

答えを見る

8

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

解説を読む

テープのマスに左端から番号 $0, 1, 2, \dots$ をつける。最初のテープは
$0111 2 + 314151 6 ⊔ \dots$
であり、様相（状態・テープの内容・ヘッドの位置）は「状態 $q_{0}$ 、ヘッドはマス $0$ 」である。

各ステップでは、「今の状態」と「ヘッドが読んでいる記号」の組で遷移表の行を 1 つ選び、書く・動く・状態を変える、を行う。

ステップ 1: $q_{0}$ でマス $0$ の $1$ を読む。 $δ (q_{0}, 1) = (q_{0}, 1, R)$ より、 $1$ を書いて右へ。状態 $q_{0}$ 、ヘッドはマス $1$ 。
ステップ 2: $q_{0}$ でマス $1$ の $1$ を読む。同じく右へ。状態 $q_{0}$ 、ヘッドはマス $2$ 。
ステップ 3: $q_{0}$ でマス $2$ の $+$ を読む。 $δ (q_{0}, +) = (q_{1}, 1, R)$ より、 $+$ を $1$ に書きかえて右へ。テープは $111111 ⊔ \dots$ 、状態 $q_{1}$ 、ヘッドはマス $3$ 。
ステップ 4: $q_{1}$ でマス $3$ の $1$ を読む。 $δ (q_{1}, 1) = (q_{1}, 1, R)$ より右へ。ヘッドはマス $4$ 。
ステップ 5: $q_{1}$ でマス $4$ の $1$ を読む。右へ。ヘッドはマス $5$ 。
ステップ 6: $q_{1}$ でマス $5$ の $1$ を読む。右へ。ヘッドはマス $6$ 。
ステップ 7: $q_{1}$ でマス $6$ の $⊔$ を読む。 $δ (q_{1}, ⊔) = (q_{2}, ⊔, L)$ より、 $⊔$ のまま左へ。状態 $q_{2}$ 、ヘッドはマス $5$ 。
ステップ 8: $q_{2}$ でマス $5$ の $1$ を読む。 $δ (q_{2}, 1) = (h, ⊔, L)$ より、 $1$ を $⊔$ に書きかえて左へ。状態は $h$ になる。

状態 $h$ に入ったので $M$ は停止する。このときテープは $11111 ⊔ \dots$ （ $1$ が 5 個）で、ヘッドはマス $4$ にある（この機械は $1$ の個数で表した $2 + 3 = 5$ を計算している）。

したがって、停止するまでのステップ数は $8$ である。

別解

テープの内容は 11+111（位置 1〜6）で、位置 7 以降は空白。ヘッドは位置 1、状態は $q_{0}$ 。

ステップごとの動作:
1. 位置1で $q_{0}$ 、読む記号 1。1 を書いて R、位置2、 $q_{0}$ 。
2. 位置2で $q_{0}$ 、読む記号 1。位置3、 $q_{0}$ 。
3. 位置3で $q_{0}$ 、読む記号 +。1 を書いて R、位置4、 $q_{1}$ 。テープは 111111。
4. 位置4で $q_{1}$ 、読む記号 1。位置5、 $q_{1}$ 。
5. 位置5で $q_{1}$ 、読む記号 1。位置6、 $q_{1}$ 。
6. 位置6で $q_{1}$ 、読む記号 1。位置7、 $q_{1}$ 。
7. 位置7で $q_{1}$ 、読む記号空白。空白を書いて L、位置6、 $q_{2}$ 。
8. 位置6で $q_{2}$ 、読む記号 1。空白を書いて L、位置5、状態 $h$ 。停止。

停止するまでのステップ数は 8。

検算: $q_{0}$ で入力の 1 と + を読むのに 3 ステップ、 $q_{1}$ で右の 1 を 3 個読むのに 3 ステップ、空白で 1 ステップ、 $q_{2}$ で 1 ステップなので、3+3+1+1=8。最終テープは 11111 の後に空白（位置6が空白）で、2+3 の和 5 個の 1 になり、正しく加算している。

この問題の確認

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

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

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

状態	読む記号 $0$	読む記号 $1$	読む記号 $⊔$
$q_{0}$	$(q_{0}, 0, R)$	$(q_{0}, 1, R)$	$(q_{1}, ⊔, L)$
$q_{1}$	$(h, 1, L)$	$(q_{1}, 0, L)$	$(h, 1, L)$

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

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

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