文字列 問題

計算理論 第 2 回演習問題
平成 28 年 10 月 6 日
文字列
この講義では情報処理を文字列に対する操作として扱うので，そのための用語や記法を
用意しておく．
字母（alphabet）とは空でない有限集合であり，その元を文字（letter）或いは記号（sym-
bol）と呼ぶ．字母 Σ に属する文字を重複を許して有限個並べた列 x = x1 x2 . . . xn を Σ
上の文字列（string）或いは語（word）と呼ぶ．並べた文字の個数 n を x の長さ（length）と
いい |x| で表す．長さ 0 の文字列を ε で表す．Σ 上の長さ n の文字列全体を Σ n で表し，
文字列全体を Σ ∗ で表す．例えば字母 Σ = {0, 1} 上の文字列全体は
Σ ∗ = Σ 0 ∪ Σ 1 ∪ Σ 2 ∪ Σ 3 ∪ · · · = {ε, 0, 1, 00, 01, 10, 11, 000, 001, . . .}
である．また文字列 001 ∈ Σ 3 ⊆ Σ ∗ の長さは |001| = 3 である．
文字列 x = x1 · · · xm の後に続けて文字列 y = y1 · · · yn を並べて得られる文字列
x1 · · · xm y1 · · · yn を xy で表す．また文字列 x を n 回書き並べた文字列
xx
· · · x}
| {z
n
を xn で表す．
Σ ∗ の部分集合を言語（language）と呼ぶ．例えば Σ = {0, 1} として，
primes = { x ∈ Σ ∗ : x は或る正整数を二進法表示であり，その整数は素数である }
は Σ 上の言語である*1 ．言語 L に対し，L に属しない文字列の全体 L = Σ ∗ \ L を L の
補集合
（complement）
（補言語）という．
問題
本講義では計算の目標とする課題として，入力された文字列に対して何かを答えるとい
う，一回限りの受け答えを考える．何度も入出力を繰返したり，複数の計算機がやりとり
をして一つの目的を達したりする計算は，本講義では扱わない．そこで，入力文字列が何
*1
このように言語というときは字母 Σ を指定して話をすべきだが，以後文脈に応じて Σ は適当な文字を含
んでいるものと一々断らずに仮定する．例えばこの primes の定義を書いたら，二進法表示に必要な 0，
1 を含む字母を考えていると解釈してもらいたい．
1
であるときに答として何が許されるかを定めたもの（仕様）を問題（problem）と呼ぶこと
にしよう．以下に形式的な定義を述べる．
判定問題（decision problem）とは，前回扱った問題のように，受取った文字列に対して
真か偽かを定めたものである．何らかの言語 L ⊆ Σ ∗ に属するか否かを判定しているこ
とになる．例えば上の言語 primes に対応する判定問題は次のものである（以後言語と問
題をこのように混同して同じ名で呼ぶ）
．
{
primes(x) =
真
x が二進法で素数を表す文字列であるとき
偽
そうでないとき
判定問題は今後の議論で重要な役割を果すが，より一般には
• ただ真偽の判定するのではなく，答として文字列を期待する
• 正答となる文字列は幾つかあり，そのいずれを答えても正解となる
という状況も考えたい場合がある．そのために一般の「問題」を定義しておこう．形式的
にいえば問題 A とは，各文字列 x ∈ Σ ∗ に対し，入力が x のときに許される出力の候補
として，空でない集合 A[x] ⊆ Σ ∗ を定めるものである．この x を問題 A に対する入力
（input）
ないし個例
（instance）
という．各個例 x について A[x] がただ一つの元より成ると
きは，要するに A は Σ ∗ から Σ ∗ への函数（function）である．このときその A[x] の唯一
の元を A(x) で表す．判定問題でないことを強調するため，ここで単に問題と称したもの
を探索問題
（search problem）と呼ぶことがある．
形式的には以上の通りであるが，通常は文字列に何らかの意味をもたせた問題を考える
わけであり，逐一この定義に従って厳密に文字列を指定するのは煩わしいので，本質に障
らぬ限り多少の曖昧さは気にせず日本語で記述する．例えば「与えられた正の整数が素数
であるか判定する問題」といえば上述の primes を指す（と解してよい）
．また「与えられ
た正の整数を素因数分解する問題 factor」とは次の探索問題である．
• Σ = {0, 1, #}．
• 文字列 x ∈ Σ ∗ が正の整数を二進法で表したものであるとき factor[x] は，次を
満す y1 #y2 # . . . #yk の形をした文字列の全体である．各 yi は二進法で或る素数 pi
を表しており，積 p1 p2 · · · pk は x が二進法で表す数に等しい．
• 文字列 x ∈ Σ ∗ が正の整数を二進法で表したものでないとき factor[x] = {#}．
通常ここまで細かく指定する必要がないのは，そのような細部が今後考える意味での問題
の難しさに影響を及ぼさないからである．例えばここでは整数を二進法で表すことにした
が，代りに十進法で表してもやはり問題の困難さは殆ど変らない．二進法と十進法の間の
2
変換は容易だからである．無論このことは「容易」の意味によるが，二進と十進の変換く
らいは今後考える如何なる意味においても容易であるから気にしないのである．
ただ二進法ではなく羅列表示（整数 n を文字列 0n で表す）にしてしまうと著しく冗長
になるため，計算量を扱う上で影響が出る．特に断らないとき整数は二進法で表すなど，
計算対象は自然で簡潔な表現で符号化する．このような習慣の下で「整数 n を二進法で表
した文字列」を単に n と呼んだり，
「適当な符号化法を用い，容易に復号できるよう文字列
y1 ，…，yk を書き並べたもの」
（上の例で y1 #y2 # . . . #yk としたように）を単に (y1 , . . . , yk )
と書いたりする．
チューリング機械と問題
チューリング機械の定義は前回資料の通りだが，今回からは上述のように真偽の判定以
外も考えるため少し補足を要する．
真偽の判定をしたかったときは状態が q受理 と q拒否 になることを以て計算結果とした．
すなわち機械 M が言語 L を判定（decide）する（決定するともいう）とは，任意の個例 x
に対して
• x ∈ L ならば M は x を受理し
• x∈
/ L ならば M は x を拒否する
ことをいうのであった．
何らかの文字列を答として出力したいときは，テープ上にその答えたい文字列を書いて
から状態を q受理 にすることとしよう．つまり機械がテープ上に文字列 y しかない状況に
してから状態を q受理 にすることを，y を出力（output）すると呼ぶことにする（この場合
q拒否 という状態があることは無意味になるが）．機械 M が（探索）問題 A を解くとは，任
意の個例 x に対して
• M に x を入力すると A[x] の元の一つを出力（して受理）する
ことをいう．「解く」の代りに「計算する」ともいう*2 ．「出力する」というには文字列を
書いてから受理状態 q受理 に入らねばならないことを強調しておく．文字を書きはしたが
終了報告をせずにだらだらと動作し続けるという無責任な態度は許されない．
実際そのようなだらしない挙動を許すか否かは大きな違いである．「判定」を少し緩め
た次の概念を考えよう．機械 M が言語 L を認識するとは，任意の個例 x に対して
*2
なお一般に探索問題では許される答が複数あり，ここでは M は A[x] に属する文字列のうちいずれを出
力しても構わないと定義したが，実際には入力 x が決れば M の動作は出力まで一意に決るわけだから，
M は結局何らかの一つの函数を計算することになる．
3
• x ∈ L ならば M は x を受理し
• x∈
/ L ならば M は x を受理しない
ことをいう．判定と比べると，L に属しない入力 x ∈
/ L が与えられたときには停止せず動
き続けることが許されているのである．
判定・認識・計算について，「それを行う機械が存在する」ことを○○可能という．す
なわち，
• 言語 L が判定可能であるとは，L を判定するチューリング機械が存在することを
いう．
• 言語 L が認識可能であるとは，L を認識するチューリング機械が存在することを
いう．
• 問題（や函数）A が計算可能であるとは，A を計算するチューリング機械が存在す
ることをいう．
判定可能な問題は認識可能であるが，後で見るように，認識可能な問題が判定可能であ
るとは限らない．
問 0.8 判定可能な問題が認識可能であるのは何故か．
2
問 0.9 判定可能性は補集合について閉じている．すなわち言語 L が判定可能ならば L
2
も判定可能である．何故か．
認識可能性については成立たないことを後で見る．
問 0.10
2＋2
（1）判定可能性は合併について閉じている．すなわち言語 L と L′ が判定可能
ならば L ∪ L′ も判定可能である．何故か．
（2）認識可能性は合併について閉じているか．
認識不能問題
認識可能でない言語の存在を示す．
まず，チューリング機械は遷移規則を書き記すことにより文字列で表せることを注意し
ておく．入力文字集合 Σ が Σ = {0, 1} であるような機械を文字列で表す方法を決めてお
く*3 ．さらにこの記述中の各文字を適当に符号化して {0, 1} 上の文字列で表す．以下で
*3
機械の定義では文字や状態の名に好きな文字を用いてよいことにしていたが，機械が何らかの機能を実現
する上では単にどの状態でどの文字を読むとどの状態になるかという関係のみが重要なので，ここでは
4
0
1
00
01
10
11 000 · · ·
x
0
×
×
×
○
×
○
×
1
×
○
○
×
×
×
○
00
×
×
×
×
×
×
×
01
○
×
×
×
○
○
×
10
○
×
○
×
○
×
×
diag(x) 真
偽
真
真
偽
真
偽 ···
..
.
M
図1
受M (x) を纏めた表（M が x を受理するとき○，しないとき×）
．diag(x) は対角線上の成分
受x (x) の逆である．
は機械 M を表す {0, 1} 上の文字列をやはり M と呼ぶことにしよう．
ここで {0, 1} 上の文字列 M と x に対し，「機械 M に文字列 x を入力すると受理する」
ことを 受M (x) と書くことにしよう．文字列 M がそもそも機械の記述になっていないと
きは，便宜上 受M (x) は成り立たないとしておく．
すると次の言語 diag ⊆ {0, 1}∗ は認識不能である．
diag = { x ∈ {0, 1}∗ : 受x (x) でない }
何故なら，これを認識する機械 D があったとすると，それは入力 x に対し
x ∈ diag ならば受理し，x ∈
/ diag ならば受理しない
すなわち
受x (x) でなければ受理し，受x (x) ならば受理しない
（＊）
ような機械である．これが任意の x で成立つのだから，特に x = D のときにも成立つは
ずである．しかし，もし 受D (D) ならば（＊）の前半が成立たないし，さもなくば後半が成
立たない．これは矛盾である．
この証明の末尾の部分（（＊）を満たす機械が存在しないこと）は次のように図解でき
る．縦軸にすべての文字列 D を，横軸にもすべての文字列 x を並べ，各成分に 受D (x) を
記した図 1 の表を考える．示したいのは，いずれの機械 D の挙動も（つまり表のいずれ
一定の文字集合のみを使って書いた機械を考える．すなわち 0 と 1 以外の文字は γ0，γ1，γ10，γ11，
γ100，…，また状態は q0，q1，q10，q11，q100，…と二進法の番号で名づける．このように約束してお
けばあらゆるチューリング機械を一定の文字集合で書き表せる．
5
の行も）（＊）に一致しないことであった．これはどの機械 D の行も，x = D に対応する
列において
い違うことからわかる．この証明法は，表の対角線上の成分を使った議論で
あることから，対角線論法と呼ばれる．
問 0.11 対角線論法は，（無限）集合どうしの大きさが異なることを示すのに使われるこ
5
とがある．X から Y への全写像とは，函数 f : X → Y であって，任意の y ∈ Y に対し
て x ∈ X が存在して y = f (x) が成立つようなものをいう．このような f があれば，Y
の「大きさ」が或る意味で X よりも大きくはないと言えるだろう．
集合 S に対し，S の部分集合全体を P(S) で表すことにする．S から P(S) への全写像
が存在しないことを示せ．
ヒント S から P(S) への全写像 f が存在したとして，縦軸にすべての s ∈ S ，横軸にすべての
t ∈ S を並べ，f (s) が t を含むか否かを記入した図 1 のような表を考え，対角線論法を使う．
6