計算量理論
計算論を知っていると、プログラミングで使える正規表現の限界を理解できる
判定に必要な時間によって言語を分類するためクラスを導入する
t:N⇨R^tとすると、TIME(t(n))はO(t(n))時間TM(単一テープTM)で判定される全ての言語の集合を表す
t(n)をt(n)>nである関数とする。全てのt(n)時間複数テープTMに対して、O(t(n)^2)時間単一テープTMが存在する
非決定性TMに関する計算時間を考える
NをNDTM Nを判定装置とする。Nの動作時間がf(n)であるとは、長さnの入力に対する計算で使う最大ステップ数である
全てのt(n)時間NDTMに対して、それと等価な2^O(t(n))時間単一テープNDTMが存在する
・クラスP
Pは決定性単一テープTMで多項式時間で判定できる問題の集合である
Pは現実的に解ける問題のクラスにほぼ対応
言語は非決定性多項式時間TMで判定されるとき、かつそのときに限り言語はNPである
NPは多項式時間検証装置を持つ言語のクラス
HAMPATHはNP
P:要素があるかどうかを多項式時間で判定できる
NP:要素であることを多項式時間で検証できる、要素かどうかをNDTMで多項式時間で判定できる
NP完全性
NPの中で一番難しい問題のクラス、P/=Nと信じらレているので、ある問題がNP完全であれば、多項式時間で解けない可能性が高い
充足可能性問題(SAT)
論理式をTrueに評価するような変数の割り当てが存在するとき、その式は充足可能という
Cook Levinの定理
SATはNP完全である
P=NPのとき、かつそのときに限りSATがPに含まれる
次回は一時間ぐらいでCook Levinの定理の証明をする
1.チューリングマシン
計算論=TMの限界を知る
・アルファベット
記号の有限集合をアルファベットといい、Σで表す。文字列とは、アルファベットを重複を許して並べたもの
長さが0の文字列を空列という
空列は空集合とは違う
・言語
言語とはアルファベット上の有限・無限集合を表す
Mを機械とし、言語AをMが受理する全ての文字列の集合とすると、言語AはMの言語であるといい、L(M)=Aで表す
・有限オートマトン
有限個の状態と遷移動作
・決定性有限オートんマトン(DFA:Deterministic Finite Automation)
与えられた文字列xを読み込み最後に受理または拒否を表す
あるDFAで受理される言語を正規言語という
M = (Q, Σ, δ, q0, F)
Qは状態の有限集合
Σはアルファベットの有限集合
δはQとΣを引数とする遷移関数
q0は開始状態
Fは受理状態の集合
・非決定性有限オートマトン(NFA: Nondeterministic Finite Automation)
DFAは入力文字を読むと状態が一意に決まるがNFAでは複数の選択肢がある
DFAは状態と入力文字に対して、次の状態を与える
NFAは状態と入力文字または空列に対して次の状態集合を与える
P(Q)ですべての部分集合の集合を表す(べき集合)
Σε = ΣU{ε}とする
NFAの遷移関数はδ:Q×Σε→P(Q)
NFAも(Q, Σ, δ, q0, F)で与えられる
入力を終了した時点でどれか1つでも受理状態にあればNFAは入力を受理する
・NFAとDFAの等価性
DFAとNFAは同じ言語クラスを受理する
証明のアイディア:NFAのk個の状態に対して部分集合を2^k個列挙しDFAに変換する
よってあるNFAによって受理される言語も正規言語である
・正規演算
言語の対する演算
AとBを言語とすると、以下の3つの演算を正規演算という
1. 和集合演算
2. 連結演算
3. スター演算
正規言語は正規演算に対して閉じている
・正規表現(Refular Expression)
正規言語を記述するための言語、正規表現は帰納的に定義される
1. アルファベットΣに属するa
2. ε
3. ゼロ集合
4. R1とR2を正規表現としてR1UR2
5. ..R1⚪︎R2
6. ..R1*
言語は正規表現で記述される時かつその時に限り正規
・RE⇨NFAの変換
・NFA⇨RE
・非正規言語
有限オートマトンは状態が有限個なので、認識可能な言語は限られる
数学的にある言語が正規でないことを示す方法がある
ポンピング補題はすべての正規言語が満たすべき定理
・ポンピング補題
Aが正規言語ならば、ある数P(ポンピング長)が存在して、Sが少なくとも長さPであるAの任意の文字列であるときにSは以下の条件を満たす断片s = xyzに分割できる
1. i>=0について xy^iz ∈ A
2. |y| > 0 (⇔ y ∈/ ε)
3. |xy| <= p
・捕捉
機械Mが言語Aを認識する⇔AがMの受理するすべての文字列である L(M) = A
・文脈自由文法(CFG:Context Free Grammar)
CFGは正規表現より複雑な言語を生成可能
CFGは人の元gのを解析するために考案されたモデル
CFGはプッシュダウンオートマトンPDAと同じクラスの言語を認識可能である
CFGは(V, Σ, R, S)で定義される
1. Vは変数の有限集合
2. Σは終端記号の有限集合
3. Rは書き換え規則の有限集合
4. Sは開始記号の有限集合
書き換え規則は A→αで表現される
Rを開始記号Sに適用することで文を生成する
・正規言語⊂文脈自由言語
任意の正規言語Lに対して、それを受理するDFAからLを生成するCFGを構成できる
・最左導出
言語Gの文字列wの導出において、最左の変数に規則を適用する制限
最左導出という制限でも文法Gが生成するすべての文字列なら導出可
文字列wが2つ以上最左導出を持つ場合、その文法は曖昧であるという
・チョムスキー標準形(CNF:Chomsky Normal Form)
CFGの書き換え規則は様々であるが、CNFは標準化した記法
・グライバッハ標準形(GNF:Greibach Normal Form)
・一般のCFGからCNFへの変換
・CFGのポンピング補題
・プッシュダウンオートマトン(PDA:Push Down Automation)
NFAと似たオートマトンでスタックと呼ばれる記憶装置を持つPDAとCFGの能力は等しい
PFAとCFGの能力は等しい
スタックはLast In First Outである
PDAは M = (Q, Σ, Γ, δ, q0, Z0, F)で表される
・CFGとPDAの等価性
あるPDAがある言語を受理するときかつそのときに限り、言語は文脈自由
・チューリングマシン
TMは無限の長さを持つテープと、テープに対して読み書きする制御部(ヘッド)から構成される
TMはテープに読み書き両方ができる
ヘッドは左右どちらにも動ける
テープの長さは無限
拒否・受理状態になると停止する
TMは (Q, Σ, Γ, δ, q_0, q_accept, q_reject)で定義される
TMは入力がテープに書き込まれた状態からスタートする(左端から書き込まれ、他は空白)
テープに現れる最初の空白文字は入力の終わりを意味する
テープの左端よりもさらに左には移動できない
・ヘッドの移動
・チューリング認識とチューリング判定
チューリングマシンMが受理する文字列の集合をMの言語といい、L(M)と表す
言語に対して、それを受理するTMがある場合、チューリング認識という
TMは受理、拒否、停止しないの3つの場合がある
受理、拒否を行う機械を判定装置という
任意の言語に対してそれを判定するTMがある場合、チューリング判定可能という
チューリング認識は止まるとは限らず、チューリング判定は必ず止まるという違いに注意
・TMのバリエーション
1.多テープTM(MTL)
複数のテープを持つ。初期状態ではテープ1に入力が書いてある
MTMの遷移関数は複数のテープに対してδ系る
MTMはTMでシュミレート可能
2.非決定性チューリングマシン(NDTM)
NFAと同様に非決定的な遷移関数を持つ
NDTMの能力はDTMの能力と等しい
・アルゴリズム
チャーチチューリングの提唱から以下のように定義される
1.TMで実行できる
2.解法がある(解くTMがある)
・判定可能性
正規言語について
DFAの受理問題を考える
文脈自由言語について
・停止問題
判定できない言語が存在する
・対角線論法
可算無限集合:自然数Nと1対1対応あり
不可算無限集合:自然数Nと1対1対応なし
・チューリング認識できない言語
・停止問題の判定不可能性
・チューリング認識できない言語の具体例
・計算量
ある問題が判定可能であるとき、判定するまでに必要なステップ数の最悪ケース
Mをすべての入力で停止するTMとする
Mの計算量は f:N→Nによって表される
f(N)は長さNの入力に対してMの判定に必要な最大ステップ数
f(n)の厳密な計算は難しいので漸近的な記法を用いる
・クラス
判定に必要な時間によって言語を分類するためにクラスを導入する
tをt: N→RとするとTIME(t(n))はO(t(n))時間TMで判定されるすべての言語の集合である
t(n)をt(n) >= nである関数とする
すべてのt(n)時間複数テープTMに対して、等価なO(t(n^2))時間単一テープTMが存在する
同様に非決定性TMに関する計算時間を考える
NをNDTMの判定装置とする
Nの動作時間がf(n)であるとは、長さnの入力に対する計算の枝においてNが使う最大ステップ数がf(n)であることをいう
NDTMで判定可能な問題はDTMでも判定可能
必要な計算時間は異なる
t(n)をt(n)>=nである関数とすると、すべてのt(n)時間NDTMに対して、等価な2^O(t(n))時間単一テープDTMが存在する
・クラスP
指数関数か多項式関数かのみで分類する
クラスPとは単一テープDTMで多項式時間で判定できる問題の集合である
問題の符号化:TMに問題を与えるとき、問題を文字列にするが、多項式時間の変換を仮定する
・クラスNP
HAMPATH問題のこと
HamiltonPathが多項式時間で解けるかどうかはまだわかっていない
HamiltonPathは多項式時間検証可能性という特徴を持つ
・検証装置
言語AをアルゴリズムVを用いて、以下のように定義できるとき、VをAの検証装置という
A = {w | vはある文字列cに対して<w, c>を受理}
cは補助情報、言語が多項式時間検証装置を持つとき、多項式検証言語という
クラスNPは多項式時間検証装置を持つ言語のクラスである
NPはNondeterministic Polynomial Timeに由来する
NDTMによっても定義される
・NPの2つの定義が等しいことの証明
・NP完全性
NPの中で一番難しい問題のクラス
P /= であることが信じられているのでNP完全なら、多項式時間で解けない強力な根拠となる
・多項式時間帰着可能性
任意の入力wに対して、f(w)を計算して停止する多項式時間TMがあるとき、fは多項式時間計算可能関数という
言語Aと言語
・COOK-LEVINの定理
SATはNP完全である
計算機自体をシミュレートし、その動作をSATに落としこむ
・帰納関数論
これまで、TMを考えることで計算を考えてきた
これに対して、帰納関数では基本的な関数をもとに複雑な関数を構成する
これらの操作で得られる関数を帰納関数という
TMで計算可能 = 帰納関数
・原始帰納関数(PRF)
帰納関数を構成する基本的関数をPRFという
PRFは3つの初期関数から作られる
1. 後者関数
2. ゼロ関数
3. 射影関数
PRFは2つの操作に関して閉じている
1. 合成
2. 原始帰納
・定理 すべてのPRFはTMで計算できる
・最小化関数
条件を満たす最小の自然数を探す関数
・割り算
普通の割り算は全域関数ではない
そこで以下の割り算を考える
・ゲーデル数
数の列を1つの数に一意にエンコードする方法
・計算可能部分関数
PRFは全域関数である
よってすべての入力に対して権威さんして値を返す
しかしTMは入力によっては停止しない
よってPRFの集合でTMに含まれない計算できる関数の集合
・限定なしの最小化関数
以前の最小化関数は探索が限られていたが、その限定を外したもの
・帰納関数(μRF)
全域関数であるPRFを部分関数に拡張したもの
PRFに限定なし最小化を入れたもの
・すべてのμRFはTMによって計算可能⇔μRFとして定義できない関数は計算できない
・λ計算
計算モデルの1つで、計算を作用と抽象化でモデル化したもの
λ計算 by チャーチ→ML,Lisp
帰納関数 by エルブラン、ゲーデル、クリーね
TM by チューリング →Fortran, Pascal
・λ計算の定義
・作用
・抽象化
・省略記法
・β簡約
・λ計算の能力
・μRFに必要な関数
・初期関数はλ定義可能
・λ定義可能な関数は合成に対して閉じている
・不動点定理
原始帰納のために必要な定理
・原始帰納はλ定義可能関数に対して閉じている
・最小化関数はλ定義可能
・簡約
・チャーチ・ロッサーの定理
・正規化定理
Mがβ-nfを持つならば、最左β基を簡約することでβ-nfが得られる
・λ計算における部分関数
Neural Networks and the Chomsky Hierarchy