形式言語と計算論入門

形式言語と計算論入門
水谷 正大
2015 年 7 月 14 日
version 0.01
目次
第1章
Turing 機械
1
1.1
Turing 機械の定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Turing 機械の計算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3
万能機械と停止問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
参考文献
10
i
第1章
Turing 機械
1.1 Turing 機械の定義
A.Turing は On computable numbers, with an application to the Entscheidungsproblem(1936)
において計算する機械装置を提案した [5]。今日ではこれを Turing 機械と呼んでいる。
定義 1.1 (Turing 機械) T M = (Q, Σ, δ, q0 , qH ) を Turing 機械 という。TM は有限制御部、
ヘッド (head) および無限長のテープからなっている。ヘッドはテープのマス目の記号を読み、こ
れを書き換えて左右に移動する。
(1) Q は有限の空でない内部状態集合、Σ は有限アルファベットで、特別な記号として空白
（blank） ⊔ (B と表記することもある) が含まれているとする。
(2) テープの移動方向*1 の集合 M = {L, R}.
(3) 状態遷移関数 δ : Q × Σ → Q × Σ × {L, R} は部分関数であって
δ(q, a) = (b, p, m) a, p ∈ Q, a, b ∈ Σ, m ∈ M
(1.1)
によって、状態 q にあるとき記号 a を読んだヘッドはこれを b に書き換え状態を p に遷移
してヘッドを m 方向に 1 マス分移動する。δ は Q × Σ × Σ × Q × {L, R} の部分集合*2 と
して表すことができ、式 (1.1) を
∆ = {q ab p m | δ(q, a) = (p, b, m)}
と表し、TM を M = (Q, Σ, ∆, q0 , qH ) で表すことがある。q ab p m かつ q ab′ p′ m′ のとき
は、b = b′ , q = q ′ , m = m′ とする。
(4) q0 を開始状態（start）、qH を受理状態（accepting state）という*3 。
*1
テープの移動方向として、左（L）右（R）に加えて中立（N ）を加える考え方もある。テープの本数などを変更し
ても、同等な TM を構成することができる。
*2 状態遷移関数 δ : Q × Σ → Q × Σ × M を部分関数としたためである。
*3 停止状態を 1 つ qH とするのでなく、Q の部分集合 H を指定し、H のいずれかに到達すると停止とするやり方も
考えられるが、これらも同等である。
1
定義 1.2 (TM の計算情況) TM において、Σ と Q の要素を有限個並べた列で、Q の要素を 1 つ
だけ含む形 Σ∗ · Q · Σ∗ の要素
a1 a2 . . . ai−1 qai . . . an
(1.2)
を TM の計算情況（configuration）または時点表示（instantanenou description）
、計算情況から
Q の要素を取り除いたものをテープ表示という*4 。
式 (1.2) の計算情況において、テーク記号列 a1 a2 . . . an に対して TM の現在状態は q であって、
ヘッドはテープ記号 ai のあるマス目に置かれているが記号内容はまだ読み取っていないと考える。
定義 1.3 (TM の動作表示) TM M = (Q, Σ, δ, d0 .qH ) とし、v, w ∈ Σ∗ , a, b, c ∈ Σ, q, p ∈ Q と
する。ある計算情況 α から次の計算情況 β へ移行（yield）することを TM の動作
α ⊢M β
と書いて、つぎで定義する。
(1) if δ(q, a) = (p, b, R) のとき、 uc q aw ⊢M ucb p w
(2) if δ(q, a) = (p, b, L) のとき、 uc q aw ⊢M u p cbw
ここでは、わかり易さのために、各時点表示においてヘッドが置かれているマス目にある記号の下
にアンダーライン _ を添えた（1. の w は文字列 w の左端の記号と理解する）。
定義 1.4 (TM の受理と停止) TM の動作 ⊢M は計算情況の集合上の 2 項関係で、その反射的推
移閉包を ⊢∗M で表す。つまり、時点表示の列 α1 , α2 , . . . , αn が存在して
α = α1 ,
α 1 ⊢M α 2 ,
αn−1 ⊢M αn ,
αn = β
であるとき、α ⊢∗M β で表す。
初期状態 q0 を含む時点表示（そのテープ記号が入力記号列とする）から始めて動作を繰り返し
たとき、次の場合が考えられる。
(1) TM の状態が受理状態 qH に入る。このとき、TM は動作を停止（halt）して入力列を受理
する*5 。
(2) 動作 α ⊢M β となる時点表示 β が存在しない（δ による遷移が定義されていない）計算情
況 α に到達する*6 。このとき TM は計算情況 α で TM の動作を止めて、入力を拒否したと
する。この拒否状態の記述は、状態遷移の記述を簡素化したために生じたもので、状態集合
*4
計算情況 a1 a2 . . . ai−1 qai . . . an では、テープ記号 a1 a2 . . . an で埋められたテープのマス目以外はすべて空白で
あるとしている。
*5 停止状態 qH に到達した段階で TM は停止するとしているので、テープ記号列が残っていても入力を受理すると考
えている。
*6 テープに最左端が設けてあって右側に無限に伸びているようなテープ装置の場合には、テープ左端からさらにヘッ
ド左側に移動させる動作 L となってもヘッドは同じ場所に留まるとする。
2
Q に拒否状態を導入して「拒否状態に達したら入力を拒否したとして TM を停止する」と
してよい。
(3) 動作がいつまでも続く（同じ処理群を永久に繰り返す無限ループ）。このときも、TM は入
力を受理しない*7 。
定義 1.5 (TM の状態遷移図) TM M = (Q, Σ, δ, d0 .qH ) において、
δ(q, a) = (p, b, m),
q, p ∈ Q, a ∈ Σ, m ∈ M ⇐⇒ q ab p m
a → b, m
q
q1
⇐⇒
状態 q から p への矢印で遷移を表す。矢印のラベルは a b m はヘッドが記号 a を b に書き換え、
ヘッドを m 方向に移動すると読む。
例 1.1 次の TM M を右図の状態遷移を持つ。
1 → B, R
({q0 , qH }, {1, ⊔}, {q0 1⊔q0 R, q0 ⊔qH R}, q0 , qH ))
q0
⊔ → 1, R
qH
この TM を初期時点表示 ⊔q0 11
. . . 1} ⊔ で動作させてみる。
| {z
n
. . . 1} ⊔
⊔q0 11
. . . 1} ⊔ ⊢M ⊔⊔q0 11
. . . 1} ⊔ ⊢M ⊔⊔⊔q0 11
| {z
| {z
| {z
n
n−1
⊢∗M
n−2
⊔ ⊔⊔
. . . ⊔} 1qH ⊔
| {z
n
となって停止状態に入って TM は停止するので入力テープ 11
. . . 1} を受理する。また、入力テープ
| {z
n
11
. . . 1} ⊔ 11
. . . 1} で動作させても
| {z
| {z
n
m
⊔q0 11
. . . 1} ⊔ 11
. . . 1} ⊢∗M ⊔ ⊔⊔
. . . ⊔} 1qH 11
. . . 1}
| {z
| {z
| {z
| {z
n
m
n
m
となって停止状態に入って TM は停止するので、11
. . . 1} ⊔ |11 {z
. . . 1} も受理する。この TM は 1 を
| {z
n
m
見つけると ⊔ に書き換えて左から右方向にヘッドを移動させて、⊔ を見つけると 1 に書き換えて
停止する。1 と ⊔ からなる入力記号を受理する。誤解がない場合には、時点表におかるテープ両側
のブランク ⊔ を省略して書くことが多い。
*7
待っていても TM の動作が止まらないために受理しないのであるが、もっと立ち続けると TM は動作を停止する
かもしれない。個々の入力データのそれぞれについて TM が無限ループに陥ってしまうかどうかを検査することは
可能であるが、任意の入力データについて TM の動作がいつかは止まってしまうかどうかをどうやって知るか、つ
まり停止するか停止しないかを判定する（そのどちらかしかない）ことが問題になる。
3
演習 1.1 次の TM M = ({q0 , q1 , qH }, {0, 1, ⊔}, ∆, q0 , qH ))
∆ = {q0 0⊔q0 R, q0 1⊔q1 R, q1 0⊔q1 R, q1 1⊔q0 R, q0 ⊔0qH R, q1 ⊔1qH R}
を考えよう。M は次の状態遷移を持つ。
1 → ⊔, R
0 → ⊔, R
q0
q1
0 → ⊔, R
を与えて、初期時点表示 ⊔q0 w⊔ と
1 → ⊔, R
⊔ → 0, R
M に 0 と 1 からなる列 w ∈ {0, 1}∗
⊔ → 1, R
する。⊔q0 101010⊔、⊔q0 11010⊔ を
動作させてみなさい。この TM は
どのような機械かを説明しなさい。
qH
1.2 Turing 機械の計算
定義 1.6 (TM の計算) TM M = (Q, Σ, δ, q0 , qH ) において、x, y ∈ Σ∗ とする。
時点表示 q0 x ⊢∗M yqH であるとき、この過程を TM の計算という。テープ表示 y を x に関する
M の計算結果といい、ComptM (x, y) と表す。
例 1.2 演習 1.1 の TM M では、q0 11010⊔ ⊢∗M 1qH である。実際、
⊔q0 11010⊔ ⊢M ⊔⊔q1 1010⊔ ⊢M ⊔⊔⊔q0 010⊔ ⊢M ⊔⊔⊔⊔q0 10⊔ ⊢M ⊔⊔⊔⊔⊔q1 0⊔
⊢M ⊔⊔⊔⊔⊔⊔q1 ⊔ ⊢M ⊔⊔⊔⊔⊔⊔1qH ⊔.
これより、計算 ComptM (11010, 1) を得る。同様にして ComptM (110101101, 0) である。
定理 1.1 M = (Q, Σ, δ, q0 , qH ) を TM とする。α, β を時点表示意、x, y ∈ Σ とする。
(1) α ⊢M β となる β は、存在したとしても高々 1 つである。
(2) ComptM (x, y) であるような y は、存在したとしても高々 1 つである。
自然数 N 上の関数の解散を考えるために、数の組みの符号化（テープ表現）を考える。ここでは
1 進数（unary）を使う。1 ∈ Σ であるとして、数 n ≥ 0 を
n = 11
. . . 1} = 1n+1
| {z
(1.3)
n+1
とする。k 個の自然数の組み (n1 , n2, . . . , nk ) に対するテープ表現を
(n1 , n2, . . . , nk ) = n1 ⊔ n2 ⊔ . . . ⊔ nk
(1.4)
で定義する。
4
定義 1.7 自然数上の関数 f : Nk → N は、次のような 2 条件を満たす TM M = (Q, Σ, δ, q0 , qH )
が存在するとき、部分的に計算可能（partially computable）という。
(1) 任意の (x1 , . . . , xk ) ∈ D(f ) に対して、あるテープ表現 α が存在して
ComptM (n1 ⊔ n2 ⊔ . . . ⊔ nk , α ⊔ f (x1 , . . . , xk )).
(2) (x1 , . . . , xk ) ̸∈ D(f ) に対して, n1 ⊔ n2 ⊔ . . . ⊔ nk をテープの初期記号列とする計算が定義
されない。
関数 f を計算する TM M が存在するとき、f は M で計算可能（computable）という。機械 M
がある k-変数関数を計算するとき、M の計算する関数を FM (x1 , . . . , xk ) で表す。
1.2.1 帰納的関数の計算可能性
補題 1.2 原始関数は計算可能である。
補題 1.3 関数 g(x1 , . . . , xr ), hj (x1 , . . . , xn ), (j = 1, . . . , r) が計算可能であれば
f (x1 , . . . , xn ) = g(h1 (x1 , . . . , xn ), . . . , hr (x1 , . . . , xn ))
も計算可能である。
補題 1.4 関数 g(x1 , . . . , xn ), h(x1 , . . . , xn , y, z) が計算可能であれば
f (x1 , . . . , xn , 0) = g(x1 , . . . , xn )
f (x1 , . . . , xn , y + 1) = h(x1 , . . . , xn , y, f (x1 , . . . , xn , y))
によって定義される関数も計算可能である。
補題 1.5 関数 g(x1 , . . . , xn , y) が計算可能かつ正則*8 であれば、µ 作用素によって定義される関数
f (x1 , . . . , xn ) = µy(g(x1 , . . . , xn , y) = 0)
も計算可能である。
以上の補題から、次の結果を得る。
定理 1.6 帰納的関数は計算可能である。
1.2.2 Gödel 数
数学上の論理命題や TM 自身を符号化することを考えてみよう。このことが可能になれば、こ
れらの対象をテープ上に表現することが可能になる。さらにいうと、テープ記号を数に対応させる
*8
関数 f (x1 , . . . , xn , y) は、任意の (x1 , . . . , xn ) に対して f (x1 , . . . , xn , y) = 0 となる y が存在するとき正則であ
る。
5
ことができれば、数学的な対象を数として表すことができる。ただし、こうして得られた数は元の
対象と一対一対応が付けられている必要がある。こうして、Gödel 数の概念が導入される。
必ずしも有限でない集合 Ω から得られる全体 Ω∗ は自然数関数や述語を記述している。この各種
表現 x ∈ Ω∗ を自然数に 1 対 1 で対応させることを Gödel の符号化（Gödel’s numbering）とい
う。
gn : Ω∗ → N
(1.5)
考えるべきことは、任意の n ∈ N に対して gn(x) = n であるような x ∈ Ω∗ が存在するか否かを
判定し、存在するときは x を求めるアルゴリズムが具体的に与えられていなければならないことで
ある（gn(x) を計算する有限手続きはもちろん与えられていなければならない）。
Gödel による方法は次のようである。可算集合 Σ = {s1 , s2 , s3 , . . . } とする。まず、関数
a:Σ→Nを
a(si ) = 2si + 1
とする。pi を i + 1 番目の素数
p0 = 2, p1 = 3, p2 = 5, p3 = 7, p4 = 11, p5 = 13, . . .
として、x ∈ Ω∗ の Gödel 数を次のように定める。
gn(ε) = 1
a(s )
gn(xsi ) = gn(x) · p|x| i
このとき、gn(si ) = 22i+1 , gn(s2 s5 s3 ) = 25 · 213 · 27 などのように計算できる。
有限個の語の列 x0 , x1 , . . . , xn ∈ Ω∗ についても、(x0 , x1 , . . . , xn ) に対する Gödel 数を
gn(x0 )
gn((x0 , x1 , . . . , xn ) = p0
gn(x1 )
· p1
gn(x )
· · · · · pn−1 n
Gödel の符号化によって、すべての述語や公理に自然数（または自然数の集合）を 1 対 1 に対応さ
せることができ、関数計算や論理計算は自然数の計算に帰着される。
TM M = (Q, Σ, δ, q0 , qH ) における記号は、Q, Σ の各要素とヘッドの方向 L, R がある。
Q = {q0 , qH , q1 , . . . , qn }, Σ = {⊔, a0 , a1 , . . . , ak }
であることから、ヘッドの方向記号から置いて、Q と Σ の記号を交互に並べるようにして基本記
号の列
L, R, q0 , ⊔ , qH , a0 , q1 , a1 , q2 , a2 , . . .
を考え、基本記号には先頭から 3 以上の奇数を与えていく。
ˆ ← 11, q̂H ← 13, â0 ← 15, q̂1 ← 17, â1 ← 19, q̂2 ← 23, â2 ← 29, . . .
L̂ ← 3, R̂ ← 5, q̂0 ← 7, ⊔
6
δ 遷移を与える 5 つ組の Q × Σ × Σ × Q × M の要素や時点表示を表す記号列
xi ∈ (Q ∪ Σ ∪ M )
α = x0 x1 . . . xn ,
に対して数
gn(α) = px̂0 0 px̂1 1 · · · px̂nn = 2k(奇数) · ℓ
に対応づける。TM においては、5 つ組集合を扱うため、それらを表す記号列の集合 α0 , α1 , . . . , αm
に対して、数
gn(α0 )
px̂0 0 p1
′
m)
· · · pgn(α
= 2k (偶数) · ℓ
m
を対応させる。
こうした TM に関する数による符号化を以下のように行ったことになる。
(1) 基本記号列には奇数
(2) 記号列には 2k(奇数) · ℓ
′
(3) 記号列の列には 2k (偶数) · ℓ
割り当ての方法から、異なる記号、記号列、記号列の列にはっ子となる数が対応しており、すべて
の TM を自然数と 1 対 1 に対応させることができた。
1.2.3 計算可能な関数の帰納性
Gödel 数が z である TM M によってテープ入力を (x1 , . . . , xn ) としたとき
q0 (x1 , . . . , xn ) ⊢∗M wqH
となって計算を終わるときの時点表示の Gödel 数が y となることを
Tn (z, x1 , . . . , xn , y)
と表す。
定理 1.7 TM で計算可能関数は帰納的である。
定理 1.8 任意の部分的に計算可能な関数 f (x1 , . . . , xn ) に対して
f (x1 , . . . , xn ) ≃ U (µyTn (k, x1 , . . . , xn , y))
となるような数 k 、その結果としてある TM が存在する。ここで U (x) は x が計算の Gödel 数で
あるときに、その最後の Gödel 数に対して計算された値を取り出す部分関数である（部分関数ゆえ
に = でなく ≃ で表した）。
7
1.3 万能機械と停止問題
1.3.1 万能 Turing 機械
ある TM U において、任意の TM M 定義とそれに入力するテープ記号列 x をそれぞれ符号化
e(M ), e(x) し、U に入力テープ記号列 e(M )e(x) として入力することができて、U の動作として
M が x に対して実行すべき動作を模倣（simulate）するようなことができるかを考えてみよう。
このような TM U は任意の TM の動作を真似ることができるために万能 Turing 機械（universal
Turing machine）という。
任意の TM M とその入力 x がテープ記号化 e(M )e(x) が可能で（その方法が具体的に記述でき
る）こと、その M のテープ記号 x の動作を模倣する TM U を構成することができる。
定理 1.9 任意の TM M とその x の様子を模倣する万能 TMU が存在する。
機械 M が受理する文字列の集合 L(M ) を M が認識する言語という。
定義 1.8 任意の言語 L に対して、L を認識する TM が存在するとき、その言語は Turing 認識可
能（Turing recoginizable）または帰納的可算（recursively enumerable）という。
既に述べたように、入力記号に対して TM を起動した時には。受理、拒否（いずれの場合も TM
は有限時間内で停止する）または無限ループ（TM は停止することなく、いつまでたっても停止状
態には至らない）の 3 つの場合がありえる。3 ページの脚注*7 で触れたように、TM 機械において
は与えた入力に対して TM が（入力を受理するしないに関わらず）停止するか停止しないかは大
きな問題となる。任意の入力に対して（受理または拒否にもかからわずに）停止して、決して無限
ループに陥らない TM を判定装置といい、ある言語を認識する判定装置 TM はその言語を判定す
る（decide）という。
定義 1.9 言語 L が帰納的（recursive）または判定可能であるとは、任意の入力 x に対して、x ∈ L
なら 1 を、x ̸∈ L なら 0 をテープに書き出す TM M が存在することである。この M は L を判定
する。
決定問題（decision problem）とは、無限の多くの値を取る 1 つ以上のパラメータを持つ 2 値問
題について、その解が常に “yes” または “no” である問題である。決定問題が可解（solvable）で
あるとは、関連する言語 L が帰納的、つまち TM M が L を決定する（問題のインスタンスが有限
時間で停止して yes または no を結果する有限手数の決定論的手続きが存在する）ときである。
定理 1.10 (Turing(1936)) 与えられた任意の TM T と任意の入力 w について、T が w につい
て停止するかという決定問題（停止問題）は非可解である。
証明
この停止問題が可解として矛盾を導く。
8
与えられた t と w の符号化 e(T )e(w) を入力として受け取り、T が入力 w について停止し 1 を
出力し、そうでない（停止しない）ときには 0 を出力して停止するような TM MT が存在すると
仮定する。
このとき、次のようにして MT を使った TM MS を作ってみよう：ML は, e(T )e(w) を入力と
して、MT を模倣して得られた後のテープ出力を調べる。テープに 1 があれば MS は無限ループ
に入る（テープ記号について右に際限なく移動し続ける）。テープが 0 であれば MS は停止する。
さらに、M LS を使って新たに MC を次のように作る：MC は入力 e(T ) を受け取り、e(T ) を符
号化 e(e(T )) して e(T ) の後に加えて、 e(T )e(e(T )) を MS に渡す。すなわち、MS には元の T の
動作を模倣させる入力として T を符号化した入力を与える。
この MC の動作は矛盾する：MC に任意の TM として MC 自身の符号化 e(MC ) を与えると、
それが停止ときにだけ停止する。
この矛盾は、停止問題を決定する TM MT が存在するとした仮定に起因する。したがって、停
■
止判定性を機械は存在しない。
9
e(T)e(w)
1
if T halts on w
MT
if T does not halt on w
loops
0
e(T)e(w)
MS
MT
1
if T halts on w
0
if T does not halt on w
loops
e(T)
e(T)e(e(T))
MC
MS
loops
halts
if T halts on e(T)
if T does not halt on e(T)
halts
halts
参考文献
[1]『オートマトン 言語理論 計算論 I』ホップクロフト・ウルマン（第 1 版、サイエンス社, 1984）。
想定水準を落としたホップクロフト・モトワニ・ウルマンの第 2 版（共立出版, 2008）よりも、
第 1 版の方が良いという声がいまも多い。
[2]『計算理論の基礎 1. オートマトンと言語』Michael Sipser（共立出版, 2008）
[3]『計算論とオートマトン理論』A. サローマ（サイエンス社, 1988）。コンパクトにまとめられ
ているが HU 本とは違った形の好著
[4]『コンピュータの数学』Ronald L. Graham, Oren Patashnik, Donald E. Knuth（共立出
版,1993）組み合わせ数学の本として非常に優れている。『コンパイラ―原理・技法・ツール』
Aho, Lam, Sethi and Ullman（ サイエンス社、第 2 版, 2009）。表紙デザインからドラゴン
ブックとして有名な名著。
[5]『チューリングを読む』チャールズ・ペゾルド（日経 BP 社, 2012）。A. Turing の不朽の論文
On computable numbers, with an application to the Entscheidungsproblem(J. of Math.
1936) の逐語注解
10