←

数学入門公開講座

計算量理論入門

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

計算量理論

(Computational) Complexity Theory「どれほど計算し難いか」という尺度で複雑さを測る―「複雑さ」をとらえる―
河村彰星
令和3年8月1414

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

まず 問題とは？
ここでは各入力に対して答が○か×か定めたもの（入力は文字列で表される）

例えば問題

第一日問題と機械

PRIME

問題
ABA14と考えることにする

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

12

3

4

5

6

7

答

×○

○×

○×

○

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

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

まず問題とは？

ここでは各入力に対して計算して問題を解くことの難しさを論じたいので……

まず 問題とは？

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

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

問題
PRIME

1

入力×答

2○3○45×○問題です。57 は素数でしょうか？
それは入力であって問題ではない！

問題
ABA

計算
理論
警
察

この講義では67×

𝛴 上の文字列（36 とか 7 とか○始0a問題とはコレ全体のこと！

1ba b b a a b a ba b b a a b b a2a
状態

3

114

不受理

214

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

この「入力された文字列が言語 PRIME に属するか判断せよ」という問題のことも PRIME と呼ぶ（言語と問題は同じものと考える）ことにする

状態は有限個矢印も有限本受理ε

この講義では「文字列を入力すると それが PRIME に属するか答えてくれる計算機械」などについて考えたい

a, bb

空文字列

文字列のうち十進法で素数を表すもの全体が言語 PRIME = 2, 3, 5, 7, 11, 13, … ⊆ 𝛴 ∗ である

この問題を解く有限状態機械a与えられた文字列が言語に属するか問う問題のみを考える

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

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

文字列 𝑢 の後に 𝑣 を付けた文字列を 𝑢𝑣

文字列 𝑢𝑢 ⋯ 𝑢 を 𝑢
定義などと表すことにする
𝑚個有限個の文字からなる集合 𝛴 を考える
𝛴 に属する文字を有限個並べて得られる文字列の全体を 𝛴 ∗ と書く𝛴 ∗ の部分集合を言語という

0

1

2

3

a1

133

b0203

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

3

14

414

有限状態機械の限界

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

ABA はなぜ認識できたか？

入力

εabaa

abbabb aaa

問題

が要求する

答

○××○

○×○×

機械による計算の結果

受
理

不受
理

不受
理

受
理

受
理

不受
理

受
理

不受
理

演習 a と b からなる文字列のうち（1）a が奇数回現れるもの全体

bb（1）の答（例）をそれぞれ認識する有限状態機械を作って下さい

問題

始5

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

bbabaaではbba を読んでもa を読んでも同じ状態になるb?

➡矛盾

a3

aba が既に現れた状態

例えば次の言語は無理b b a a b a𝑞

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

𝑞

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

a b は不受理
a b は受理

その後 b をは◎か？
読んで至る状態2

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

証明 そのような機械があるとする
状態は有限個なので 或る数 𝑚 と 𝑁（𝑚 < 𝑁 とする）が存在してab14

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

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

そういう単純な言語しか認識できない与えられた文字列に a が b よりも多く現れるか答えよaa右のどれでもない定理

始0a（3）右から 3 文字目が a であるもの全体

MOREA

aba は現れていないが今 a が出た所
aa, b

先程の機械
ba

始（2）左から 3 文字目が a であるもの全体

各時点で「今まで読んだ部分について覚えておくべき情報」が有限種類しかないから

714※停止せず永遠に動き続ける場合は受理していないと考える

814

問題

問題

与えられた文字列に
MOREA a が b よりも多く現れるか答えよb, c 右MOREA を認識する
チューリング機械

始0右␣
3

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

a, b, c 右ac右c左左 a, b, cbb, c 右
初めは状態 0右に読み進め 最初の a を0
始c に書き換えて状態 1 になり
a右そのまま右端まで進む

1

␣

左2

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

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

左 a, c93c左左 a, b, c

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

1

␣

左2

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

辿れる矢印がないときは止読取りのみでは解けない問題を解けるようになった！
14

定義

914

チャーチとチューリングの定立（読取りのみの）

言語 𝐴 を認識する有限状態機械が存在するとき
𝐴 は正則であるという「計算できる」（チューリング機械で）認識可能（機械的な手順で解ける）

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

ボンヤリ
した概念

数学的にハッキリ
定義した概念チューリング機械ですべての「計算」が実現できているなんて本当？
幾つかの理由から

MOREAABA␣c bc bc acb a

今では広く受入れられています

現実の計算に出て来そうな色々な手順は確かにチューリング機械で書けるようだ（経験上）
他の様々なやり方で定義された計算可能性の概念とも一致

正則

チューリングの論文（次頁）
認識可能

1014

A. M. Turing. On computable numbers, with an application to the
Entscheidungsproblem. Proceedings of the London MathematicalSociety 2, 42: 230–265, 1936.

1114

紙に文字を書きながら計算する様子を考えよう大きな数値を記号と考えてもやはり瞬時には区別できない

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

文字は有限個と考えてよかろう

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

無限個使っても区別できなきゃ
意味ないので

12

14

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

14

14

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