←

数学入門公開講座

計算量理論入門

ス
ライド
はこ
こに置
いてあり
ます

―「複雑さ」をとらえる―
河村彰星
令和3年8月14

計算量理論(Computational) Complexity Theory「どれほど計算し難いか」という尺度で複雑さを測る

14

第一日
問題と機械

14

計算して問題を解くことの難しさを論じたいので……

まず

問題とは？

ここでは各入力に対して 答が○か×か定めたものと考えることにする（入力は文字列で表される）

例えば
問題
PRIME

0 1 … 9 からなる文字列与えられた正整数（十進法で書く）が素数か答えよ
入力

12

3

4

5

6

7

答

×○○×○×○a と b からなる問題
ABA

与えられた文字列に「aba」が現れるか答えよ114

計算して問題を解くことの難しさを論じたいので……

まず

問題とは？

文字列 𝑢 の後に 𝑣 を付けた文字列を 𝑢𝑣
文字列 𝑢𝑢 ⋯ 𝑢 を 𝑢𝑚などと表すことにする
𝑚個

定義有限個の文字からなる集合 𝛴 を考える
𝛴 に属する文字を有限個並べて得られる文字列の全体を 𝛴 ∗ と書く𝛴 ∗ の部分集合を言語というこの講義では与えられた文字列が言語に属するか問う問題のみを考える

例 文字集合 𝛴 = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 を考える（今後は一々断らず適当に定める）
𝛴 上の文字列（36 とか 7 とか空文字列

εとか 119 とか）の全体を 𝛴 ∗ で表す文字列のうち十進法で素数を表すもの全体が言語 PRIME = 2, 3, 5, 7, 11, 13, … ⊆ 𝛴 ∗ である
この講義では「文字列を入力すると それが PRIME に属するか答えてくれる計算機械」などについて考えたい
この「入力された文字列が言語 PRIME に属するか判断せよ」という問題のことも PRIME と呼ぶ（言語と問題は同じものと考える）ことにする214

問題
ABA

与えられた文字列に「aba」が現れるか答えよ

この問題を解く有限状態機械b
始0aa1a, bbba b b a a b a ba b b a a b b a2a3

状態は有限個矢印も有限本状態

有限の記述で書き表せる

受理不受理

現在の状態

読んだ文
字012

3a1

1

3

3b0

203

（次にどの状態に行くか記した表）

314

定義
有限状態機械は次のものにより指定される• 有限個の状態の集合 𝑄 但し次のものが定まっている• 始状態 𝑞始 ∈ 𝑄• 受理状態の集合 𝑄受理 ⊆ 𝑄• 有限個の文字の集合 𝛴• 遷移規則と呼ばれる函数 𝛿: 𝑄 × 𝛴 → 𝑄
初め機械は始状態 𝑞始 にあり 与えられた文字列 𝑥 ∈ 𝛴 ∗ の左端から次のこと（遷移）を繰返す
状態 𝑞 で文字 𝜎 を読むと状態を 𝛿 𝑞, 𝜎 に変えて一つ右の文字に進む
右端まで終ったとき状態が 𝑄受理 に属すれば機械は 𝑥 を受理したという

414

定義
機械 𝑀 が言語 𝐴 を認識するとは 任意の入力 𝑥 に対し• 𝑥 ∈ 𝐴 のとき 𝑀 は 𝑥 を受理し かつすべての入力で• 𝑥 ∉ 𝐴 のとき 𝑀 は 𝑥 を受理しない
正しく判断！
入力

εabaa

abbabb aaa

問題

が要求する

答

○××

○

○

×○

×

機械による計算の結果

受
理

不受
理

不受
理

受
理

受
理

不受
理

受
理

不受
理

演習 a と b からなる文字列のうち（1）a が奇数回現れるもの全体（2）左から 3 文字目が a であるもの全体（3）右から 3 文字目が a であるもの全体をそれぞれ認識する有限状態機械を作って下さい

b始baa（1）の答（例）514有限状態機械の限界
ABA はなぜ認識できたか？

各時点で「今まで読んだ部分について覚えておくべき情報」が有限種類しかないからaba は現れていないが今 a が出た所
aa, b

先程の機械
b
始

0a

右のどれでもない

そういう単純な言語しか認識できない

1b2a3

aba が既に現れた状態

b aba は現れていないが今 ab まで来た所

例えば次の言語は無理

614

問題
MOREA

与えられた文字列に a が b よりも多く現れるか答えよ

定理
MOREA を認識する有限状態機械は存在しない

証明 そのような機械があるとする
状態は有限個なので 或る数 𝑚 と 𝑁（𝑚 < 𝑁 とする）が存在してa始babaababab
ではa𝑚 を読んでもa𝑁 を読んでも同じ状態になるb?

a𝑚 b𝑚 は不受理
a𝑁 b𝑚 は受理その後 b𝑚 をは◎か？
読んで至る状態➡矛盾714

読むばかりでなく書く機能（と左右に動く機能）があれば？

b b a a b a𝑞

b b c a b a例えば𝛿 𝑞, a = 𝑞 ′ , c, ㊨ なら…

𝑞′

定義
チューリング機械は次のものにより指定される• 有限個の状態の集合 𝑄 但し次のものが定まっている• 始状態 𝑞始 ∈ 𝑄• 受理状態の集合 𝑄受理 ⊆ 𝑄• 有限個の文字の集合 𝛴 これと空白文字 ␣ を含む集合 𝛤 ⊇ 𝛴 ∪ ␣• 遷移規則 𝛿: 𝑄 × 𝛤 → 𝑄 × 𝛤 × ㊧, ㊨ ∪ 止

初め機械は始状態 𝑞始 にあり テープ上に与えられた文字列 𝑥 ∈ 𝛴 ∗ の左端から始めて 次のこと（遷移）を繰返す
状態 𝑞 ∈ 𝑄 で文字 𝜎 を読むと 𝛿 𝑞, 𝜎 が• 止 ならば停止する• 𝑞 ′ , 𝜎 ′ , 𝑑 なら 状態を 𝑞 ′ にし 𝜎 ′ を書込み 𝑑 の向きに一歩進む
𝑄受理 に属する状態で停止したら機械は 𝑥 を受理したという※停止せず永遠に動き続ける場合は 受理していないと考える

814

問題

与えられた文字列に
MOREA a が b よりも多く現れるか答えよb, c 右MOREA を認識する

チューリング機械

始0右␣
3ac左左 a, b, ca, b, c 右c右b

1

␣

左

状態 0 で文字 a を読むと• 状態を 1 にし• 文字 c を書込み
• 右へ行く2

左 a, c914

問題

与えられた文字列に
MOREA a が b よりも多く現れるか答えよb, c 右初めは状態 0
右に読み進め 最初の a を0始c に書き換えて状態 1 になり
a右
そのまま右端まで進む

右端に達すると状態 2 になって左へ戻ってゆき 最初の b をc に書き換えて状態 3 になりそのまま左端まで進む␣
3c左左 a, b, cc bc bc cb aa

不受理a, b, c 右c右b

1

␣

左2左 a, c

状態 0 で文字 a を読むと• 状態を 1 にし• 文字 c を書込み
• 右へ行く辿れる矢印がないときは止読取りのみでは解けない問題を解けるようになった！

914

定義
（読取りのみの）

言語 𝐴 を認識する有限状態機械が存在するとき
𝐴 は正則であるという
定義
言語 𝐴 を認識するチューリング機械が存在するとき
𝐴 は認識可能であるという

MOREA
ABA

正則

認識可能

1014

チャーチとチューリングの定立「計算できる」（機械的な手順で解ける）
ボンヤリ
した概念

（チューリング機械で）認識可能
数学的にハッキリ
定義した概念チューリング機械ですべての「計算」が実現できているなんて本当？
幾つかの理由から 今では広く受入れられています
現実の計算に出て来そうな色々な手順は確かにチューリング機械で書けるようだ（経験上）
他の様々なやり方で定義された計算可能性の概念とも一致

チューリングの論文（次頁）A. M. Turing. On computable numbers, with an application to theEntscheidungsproblem. Proceedings of the London MathematicalSociety 2, 42: 230–265, 1936.

1114

紙に文字を書きながら計算する様子を考えよう文字は有限個と考えてよかろう
無限個使っても区別できなきゃ意味ないので1214

大きな数値を記号と考えてもやはり瞬時には区別できない

現在の文字と現在の状態から次の動きを決める

状態も有限個と考えてよかろう

一度に読み書きできる文字数も1314

まとめ第一日問題と機械• 問題＝言語 無限個の入力に正解を定めたもの• 機械＝算法 有限に記述される計算手順• 有限状態機械（書込み機能なし）により認識される ＝ 正則
• チューリング機械（書込み機能あり）により認識される＝ 認識可能 ≒ 「計算できる」• 正則でないが認識可能である言語が存在する

14
14