# 計算理論

## Math
- 可數集合觀念
- 可數 : 存在到正整數 $\{1,2,...\}$ 的 injection
- $\sum^{*}$.
- The set of all finite sequences.
- The set of all C programs.
- Any language
- 不可數
- $2^{\mathbb{N}}$ ( **CANTO's Diagonalization反證** )
- The set of all infinite sequences.
- The set of all languages.
## Regular Language
- Finite State Automata ： $M = <Q,\sum,\delta,q_0,F>$
- $DFA$ 中 ： $\delta:Q\times \sum\rightarrow Q$
- $NFA$ 中 ： $\delta:Q\times \sum_\epsilon\rightarrow P(Q)$
- Regular Expression：
- 可以用 $a$、$\phi$、$\epsilon$、$R_1\cup R_2$、$R_1。R_2$、${R_1}^*$ 所表達
- 性質：
- (1) 轉換：
- NFA → DFA：用 Power Set Constuction
- REGEX → NFA：用 Induction Consruction
- DFA → REGEX：用 GNFA 技巧
- 因此可知 DFA=NFA=REGEX
- (2) 若 NFA 有 n+1 states，Worst Case下對應的 DFA 至少要 $2^n$ states。
- 考慮 NFA 
- 存在長度 $2^n$ 字串 $A=??1xxx$、$B=??0xxx$，當 suffix 補到 $n-1$ 字元時矛盾
- (3) State Minimization Algorithm
- 建立表格，檢查每 state pair 是否 indistinguishable。
- **每一個 DFA 的最小等價 DFA 彼此同構**
- (4) Myhill-Nerode Theorem：
- $L$ 是 regular language $\iff$ $R_L$ 等價類數目是 finite
- $R_L$ 定義：$~~xR_Ly~~~\leftrightarrow~~~\forall z(xz\in L\leftrightarrow yz\in L)$
- (5) Pumping Lemma
- 若 $L$ 是 regular，且 $S\in L$ 滿足 $|S|≥p$，則 $S=xyz$ ，滿足三個條件：
$(1)$ $xy^iz \in L$ 對所有 $i≥0$ 成立 $~~(2)$ $|y|>0$ $~~(3)$ $|xy|≤p$
- **Regular languages 的封閉性：**
- (1)用 cartesian product 或是 $\epsilon$ transition
- Complement、Union、Intersection
- Concatenation、Kleene star
- $L^R=\{w^R:w\in L\}$
- $Shuffle(\{00\},\{11\})=\{0011,0101,1001,0110,1010,1100\}$
- $Perfet~Shuffle(L,M)=\{a_1b_1a_2b_2...a_kb_k|a\in L,~b\in M\}$
- (2)設定 DFA 的 final state
- $R/L=\{x\in\sum^*|\exists~y\in L,~xy\in R\}$
- $Prefix(L)=\{x\in L|\exists y~xy\in L\}$
- $Noprefix(L)=\{w\in L|\text{no proper prefix of }w\in L\}$
- (3)組合技
- $Suffix(L)=Reverse(Prefix(Reverse(L)))$
- $L-M=L\cap \bar M$
- (4)其他
- Homomorphism：$h(L)=\{h(x)|x\in L\}$
- Inverse Homomorphism：$h^{-1}(L)=\{x\in\sum^*|h(x)\in L\}$
- $\frac{1}{2}L$、$\frac{1}{3}L$
- $cycle(L)=\{xy|yx\in L\}$
- **Non-Regular：**
- $L=\{0^i1^j | i\ne j\}$
- $L=\{0^p|p~is~prime\}$
- $L_{\frac{1}{3}\_\frac{1}{3}}=\{xz|~|x|=|y|=|z|\text{, for some }xyz\in L\}$
## Context Free Language
- Context Free Grammar：$G = <V,\sum,R,S>$
- Push-down Automata：$P = <Q,\sum,\Gamma,\delta,q_0,F>$
- $\delta：Q\times\sum_\epsilon\times\Gamma_\epsilon\rightarrow P(Q\times\Gamma_\epsilon)$
- 性質：
- (1) 轉換
- CFG → PDA: 用 stack 模擬 nonterminal
- PDA → CFG: $A_{14}\rightarrow 0A_{23}1~~\Leftrightarrow~~\delta(s_1,0,\epsilon)=(s_2,x)~及~\delta(s_3,1,x)=(s_4,\epsilon)$
- (2) Ambiguious Grammar： 有 string 存在兩種不同的 leftmost derivations
- 決定 CFG 是否 Ambiguious 是 Undecidable，reduced from PCP 問題
- **Parikh's theorem**: 證明 **Inherently Ambiguous language** 存在，e.g. $\{a^ib^jc^k|i=j\text{ or }j=k\}$.
- (4) Linear Grammar： 產生式最多只有一個 nonterminal
- 又分成 left linear / right linear
- (5) 每個 Context Free Grammar 都有 Chomsky Normal Form
- $S\rightarrow\epsilon$
- $A\rightarrow BC$
- $A\rightarrow a$
- 亦有 Greibach normal form
- (6) 0-PDA < 1-PDA < 2-PDA = 3-PDA = ...
- 考慮 $\{0^n1^n\}$ 、 $\{0^n1^n2^n\}$ 、 及 multitape TM
- (7) Pumping Lemma
- 若 $L$ 是 context free，且 $w\in L$ 及 $|w|≥p$，則 $w=uvxyz$ 滿足三個條件：
$(1)$ $uv^ixy^iz \in A，對所有~i≥0$ $(2)$ $|vy|>0$ $(3)$ $|vxy|≤p$
- 可以推廣成 Ogden's Lemma
- **Context Free Languages 的封閉性：**
- (1) 簡易的 grammar 更改
- Union / Concatenation / Kleene Star
- Reversal
- Homomorphism：$h(L)=\{h(x)|x\in L\}$
- e.g. $h(0) = ab, h(1) = ccba$
- (2) 修改 PDA
- Inverse Homomorphism：$h^{-1}(L)=\{x\in\sum^*|h(x)\in L\}$
- (state × buffer): 讀到 1 時，buffer 存入 ccba
- $CFL\cap RL=CFL$
- **不封閉的例子**
- 交集: $\{0^n1^n2^m\}\cap\{0^m1^n2^n\}$
- 補集: $L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$
- 差集: $\overline L=\sum^*-L$

## 考題整理 Regular / Context Free
- (1) $a^*b^*c^*-\{a^nb^nc^n\}$ is context free.
- Nondeterministically check using stack.
- (2) $L$ and $\bar{L}$
- regular: 都是 / 都不是
- context free: 都是 / 都不是 / 恰一是
- $\{0^n1^n2^n\}$
- $\{ww\}$ [ref](https://cs.stackexchange.com/questions/19151/is-the-complement-of-ww-context-free)
- (3) $sort(\{10,101\})=\{01,011\}$, $sort(\{(01)^n\})=\{0^n1^n\}$
- (4) Set of palindromes/nonpalindromes 是 nonregular
- 考慮 $L\cap \{0^*10^*\}$
- (5) 存在 non regular language $L$，使得 $L^*$ 是 regular
- $\{0^p:p\text{ is prime.}\}$
- $\{0^n1^n\}\cup\{0,1\}$
- (6) If $h(L)$ is regular, then $L$ may not be regular.
- $h(a)=\epsilon$, $h(\{a^p\})=\epsilon$,
- (7) $h(h^{-1}(L))\subseteq L\subseteq h^{-1}(h(L))$
- $\sum=\{0,1\},~\Gamma=\{a,b\},~h(0)=h(1)=a$
- $A=\{a,b\},~~B=\{0\}$
- (8) $L$ is regular $\Rightarrow$ $Subst\_One\_Char(L,a,b)$ is regular
- (9) Let $L$ be a nonempty language in which the shortest string has length $k$. Then, $L$ cannot be recognized by a DFA with fewer than $k + 1$ states.
- 令 $w=w_1...w_k\in L$ 最短，任意 DFA 接受 $w$，經過的 state 數量恰好 $k+1$ 個
- (10) Infinite number intersection of regular language could be nonregular
- $L_4=\{a^2,a^3,a^5,a^7,a^8,a^9...\}$
- $L_5=\{a^2,a^3,a^5,a^7,a^{11},a^{12},a^{13},...\}$
## Turing Machine
- Turing Maching：$T=<Q,\sum,\Gamma,\delta,q_0,q_{ac},q_{rej}>$
- $\delta:Q\times\Gamma\rightarrow Q\times\Gamma\times\{L,R\}$
- 性質：
- (1) TM 性質
- 只有一個 final state
- input 可以來回讀
- 可能會 loop，看是否經過 halting state
- (2) 定義
- Recursive Enumerable：該 language 可以被某 TM recognize
- Decidable = Recursive：該 language 可以被某 TM decide
- (3) 變形 $\rightarrow$ 能立一樣
- Nondeterministic
- Multitape
- Heads can stay
- 2-way infinite tape
- Enumerator
- (4) $CSG \equiv LBA$ : $\{a^nb^nc^n\}$
- $S\rightarrow aBC|aSBC$
- $CB\rightarrow CW\rightarrow ZW\rightarrow ZC\rightarrow BC$
- $aB\rightarrow ab,~bB\rightarrow bb,~bC\rightarrow bc,~cC\rightarrow cc$
- (5) Rice's Theorem
- $P$ 是 nontrivial TM descriptions 的 language $\rightarrow$ $P$ is undecidable
## Decidability and Reducibilaty
- 最基本 Undecidable 問題
- $A_{TM}=\{\langle M,w\rangle:M\text{ accepts }w.\}$
- 假設 $S$ 是 decider，構造 $D(\langle M\rangle)=\neg S(\langle M, M\rangle)$，則 $D(\langle D\rangle)$ 矛盾
- $MPCP$ / $PCP$
- $[\frac{\#}{\#q_0w_1...w_n\#}]$ : 起始 configuration
- $[\frac{a}{a}],~~[\frac{\#}{\#}],~~[\frac{\#}{\_\#}]$ : 對齊
- $[\frac{qa}{br}]$ 若 $\delta(q,a)=(r,b,R)$ 且 $q\ne q_{rej}$ : 轉移
- $[\frac{cqa}{rcb}]$ 若 $\delta(q,a)=(r,b,L)$ 且 $q\ne q_{rej}$ : 轉移
- $[\frac{aq_{acc}}{q_{acc}}],[\frac{q_{acc}a}{q_{acc}}],~~[\frac{q_{acc}\#\#}{q_{acc}\#}]$ : 當下方出現 $q_{acc}$，吃掉旁邊的字元
- **Decidable Problem**
- Regular
- Acceptance: $\{\langle M,w\rangle: M \text{ is a DFA that accepts } w\}$
- Emptiness: $\{\langle M\rangle: M \text{ is a DFA and } L(M) = \phi \}$
- Infiniteness: $\{\langle M\rangle: M \text{ is a DFA and } |L(M)| = \infty \}$
- 檢查是否存在 $w\in L$ ，使得 $|Q| ≤ |w| ≤ 2|Q|−1$
- Equivalence: $\{\langle M,N\rangle: M, N \text{ are DFAs and } L(M) = L(N) \}$
- Containment: $\{\langle M,N\rangle: M, N \text{ are DFAs and } L(M) \subseteq L(N) \}$
- Context Free
- Acceptance: $\{\langle G,w\rangle: G \text{ is CFG that accepts } w\}$
- CYK Algorithm
- Emptiness: $\{\langle G\rangle: G \text{ is a CFG and } L(G) = \phi \}$
- Infiniteness: $\{\langle G\rangle: G \text{ is a CFG and } |L(G)| = \infty \}$
- 檢查是否存在 $w\in L(G)$ ，使得 $n ≤ |w| ≤ 2n−1$
- $\{\langle G,x\rangle: G \text{ is a CFG and } x \text{ is a substring of }y\in L(G).\}$
- 檢查 $L(G)\cap\sum^*x\sum^*$ 是否 empty
- $\{\langle P\rangle: P \text{ is a PDA that has a useless state.}\}$
- 依序把每個 state 設成 final 檢查 empty
- Context Sensitive
- $A_{LBA}=\{\langle M,w\rangle:M\text{ is LBA that accepts }w.\}$
- **Undecidable Problem**
- [Context Free](https://liacs.leidenuniv.nl/~hoogeboomhj/second/codingcomputations.pdf)
- (1)$ALL_{CFG}=\{\langle G\rangle:L(G)=\sum^*\}$
- 檢查 $A_{TM}$ 的 Accepting Configuration
- (2)$EQ_{CFG}=\{\langle G_1,G_2\rangle:L(G_1)=L(G_2)\}$
- 根據 PCP 構造
- (3)$L(G_1)\cap L(G_2)=\phi$
- (4)$L(G)$ is ambiguous
- (5)$L(G)$ is regular
- Context Sensitive
- $E_{LBA}=\{\langle M\rangle:M\text{ is LBA and }L(M)=\phi.\}$
- 檢查 $A_{TM}$ 的 Accepting Configuration
- Turing Machine
- $H_{TM}=\{\langle M,w\rangle:M\text{ halts on }w.\}$
- $E_{TM}=\{\langle M\rangle:L(M)=\phi.\}$
- $ALL_{TM}=\{\langle M\rangle:L(M)=\sum^*.\}$
- $REGULAR_{TM}=\{\langle M\rangle:L(M)\text{ is regular}.\}$
- $EQ_{TM}=\{\langle M_1,M_2\rangle:L(M_1)=L(M_2).\}$
- $USELESS_{TM}=\{\langle M,q\rangle: \text{q is a useless state in M.}\}$
- 檢查 accept state 就可以 decide $E_{TM}$
- $S_{TM}=\{\langle M\rangle: M \text{ accepts }w\text{ whenever it accepts }w^R.\}$
- **Recognizable v.s. Unrecognizable**
- Recognizable
- $A_{TM}$、$\overline{E_{TM}}$、$H_{TM}$
- Unrecognizable: 根據 $|P(\sum^*)|>\aleph_0$ 知道必定有
- $\overline{A_{TM}}$、${E_{TM}}$、$\overline{H_{TM}}$
- $EQ_{TM}$、$\overline{EQ_{TM}}$
- $\{M:M\text{ is a decider.}\}$
- 可數不可數
- language: countable
- $R$: countable
- $RE$: countable
- $\overline{RE}$: uncountable
- $RE\cup\overline{RE}=$ the set of all language
- Mapping Reduction $(\le_m)$：存在 $f$，使得 $w\in A\iff f(w)\in B$
- 定理：若 $A\le_mB$
- $B$ is decidable/recognizable $\rightarrow$ $A$ is decidable/recognizable
- $A$ is undecidable/unrecognizable $\rightarrow$ $B$ is undecidable/unrecognizable
- 定理：$A_{TM}\le_m B$
- 1.$B$ is undecidable
- 2.$\overline{B}$ is unrecognizable
## 考題整理 TM
- (1) $L$ and $\bar{L}$
- recursive: 都是 / 都不是
- r.e.: 都是 / 恰一是 / 都不是
- $\{\langle M_1,M_2,w\rangle:M_1\text{ halts on }w\text{ and }M_2\text{ doesn't}.\}$
- $L_\forall=\{\langle M\rangle:M\text{ accepts all inputs}.\}$
- (2) If $A ≤_m B$ and $B$ is regular, then A is not necessary regular.
- e.g. $A=\{a^nb^n\},B=\{a^*\}$
- (3) Rice’s theorem 用來判斷 undecidable language
- $\{\langle M\rangle~|~L(M)\in PSPACE\}$
- $\{\langle M\rangle~|~L(M)\in NP\}$
- (4) Finite Language 總是 regular(儘管有時我們不知道長相)
- (5) Prove that every infinite Turing-recognizable language has an infinite Turing-decidable subset. (Enumerator)
- $E_1=aa,bb,a,bbb,aa,aaa,aaaa,...$
- $E_2=aa,bb,bbb,aaaa,...$
- (6) PCP restricts to two symbols $\{0,1\}$ is undecidable.
- Map $a_i$ to $0^i1$
- (7) $L=\{w~|~\text{either w=0x for some }x\in A_{TM},\text{ or w=1y for some }y\in \overline{A_{TM}}.\}$
- $\langle M,w\rangle\rightarrow 0\langle M,w\rangle$:
- $\langle M,w\rangle\rightarrow 1\langle M,w\rangle$:
- (8) 分類以下 language
- (1) $L_1=\{\langle M\rangle~|~|L(M)|\le 3\}$
- not R.E.
- (2) $L_2=\{\langle M\rangle~|~|L(M)|> 3\}$
- R.E.
- (3) $L_3=\{\langle M\rangle~|~\text{存在 input 使得 M halts in 不到 }~|\langle M\rangle|~步\}$
- recursive
- 只要檢查長度 $|\langle M\rangle|$ 步數 $|\langle M\rangle|$
- 善用 $A_{TM}\le_p L$
- L 是 not decidable
- L 是 not R.E.
- M accepts w $\leftrightarrow$ $L(M_2)$ 任意， $\in \bar{L}$
- M not accepts w $\leftrightarrow$ $L(M_2=\phi)\in \bar{L}$
- (9) not R.E.
- $L_1=\{\langle M\rangle~|~L(M) \text{ is finite.}\}$
- M accepts w $\leftrightarrow$ $L(M_2)=\sum^*$
- M not accepts w $\leftrightarrow$ $L(M_2)=\phi$
- $L_2=\{\langle M\rangle~|~L(M) \text{ is infinite.}\}$
- 建構 $N$ 當 input x，模擬 M on w |x| 步，若 M 接受 w 則拒絕，否則接受
- M accepts w $\leftrightarrow$ $L(M_2)$ finite
- M not accepts w $\leftrightarrow$ $L(M_2)=\sum^*$
- (10) Recursive
- $L_1=\{\langle M\rangle~|~L(M) \text{ is countable.}\}$
- all TMs
- $L_2=\{\langle M\rangle~|~L(M) \text{ is uncountable.}\}$
- empty
- (11) Closed under Kleene star
- The class P
- 使用 DP 依序檢查 $w_i...w_j$ 是否屬於 $P$
- Recursive languages
- NTM
- (12) 因為 TM 是 countable
- $R$ is countable
- $RE$ is countable
- $\overline{RE}$ is uncountable (因為所有的 language 是 uncountable)
## Basic Time and Space Complexity
- 定義：
$P$ | $\{L\mid L\in TIME(n^k) \}$
-|-|
$NP$ | $\{L\mid L\text{ has polynomial time verifiers}~\}$
${}$ | $\{L\mid L\in NTIME(n^k)\}$
$PSPACE$ | $\{L\mid L\in SPACE(n^k) \}$
$L$ | $\{L\mid L\in SPACE(logn) \}$
$NL$ | $\{L\mid L\in NSPACE(logn) \}$
$\le_p$ | 可以在多項式時間轉換
$\le_L$ | 可以在 log 空間轉換
- **$SAT$ is NP-complete( Cook-Levin Theorem )**
- $\phi=\phi_{cell}\land\phi_{start}\land\phi_{accept}\land\phi_{move}$
- $\phi_{cell}$ 使表格每個位置都是合法 symbol
- $\phi_{start}$ 使表格第一 row 是 start configuration
- $\phi_{accept}$ 使表格出現 $q_{accept}$
- $\phi_{move}$ 使表格每個位置都是合法 transition
- **$TQBF$ is PSPACE-complete**
- $\phi_{c_1,c_2,t}=\exists m\forall c_3\forall c_4[(c_3=c_1\land c_4=m)\lor(c_3=m\land c_4=c_2)\rightarrow\phi_{c_3,c_4,t/2}]$
- Formula Games
- Generalized Geography
- **Savitch's Theorem**
- $PSPACE = NPSPACE$
- $NSPACE(f(n))\subseteq SPACE(f^2(n))$
- $CANYIELD(c_{start},c_{accept},2^{df(n)})$
- **Immerman's Theorem**
- $NL=coNL$
- **$PATH$ is NL-complete**，證明 $PATH\in coNL$
- Nondeterministically 算出 $s$ 可以到達的最多點數 $c$
- Nondeterministically 算出找出可以到達的 $c$ 個點，看是否 $t$ 不在其中
- 其他
- Every problem in L is L-complete [註](https://en.wikipedia.org/wiki/L_(complexity))
## Time and Space Hierarchies
- 
- Time Hierarchy Theorem： $~~~~P\ne EXP$
- Space Hierarchy Theorem：$NL\ne PSPACE$
- Hierachy
- [Chomsky Hierarchy](https://en.wikipedia.org/wiki/Chomsky_hierarchy)
- [Arithmetical hierarchy](https://zh.wikipedia.org/wiki/%E7%AE%97%E6%95%B0%E9%98%B6%E5%B1%82)
- [Polynomial Hierarchy](https://en.wikipedia.org/wiki/Polynomial_hierarchy)
- **線性加速定理 [Linear Speedup Theorem](https://en.wikipedia.org/wiki/Linear_speedup_theorem)**
- 每個 $t(n)$ 時間的 TM 有個等價 $ct(n)+n+2$ 時間的 TM
- 每個 $f(n)$ 空間的 TM 有個等價 $cf(n)+2$ 空間的 TM
- **時間階層理論 [Time Hierarchy Theorem](https://en.wikipedia.org/wiki/Time_hierarchy_theorem)**
- $TIME(f(n))\subsetneq TIME(f(2n)^3)$：越多時間，能力越強
- **空間階層理論 [Space Hierarchy Theorem](https://en.wikipedia.org/wiki/Space_hierarchy_theorem)**
- $SPACE(f(n))\subsetneq SPACE(f(n)logf(n))$：越多空間，能力越強
- **[Proper Complexity Functions](https://en.wikipedia.org/wiki/Proper_complexity_function)**
- 1.$~$non-decreasing
- 2.$~$可以在 $f(n)+n$ 時間，把 $n$ 個 $1$ 轉變成 $f(n)$ 個 symbol。

## Oracle Turing Machine
- Oracle Turing machine $M^O$:

## Counter Machine
- **TM = 2-stack Machine**
- **1-stack = 2-counter**
- 每個 stack 可以對應到一個數字，用一個 counter 記住。
- 另一個 counter，用作乘法或除法。
- **2-stack = 3-counter**
- 兩個 stack 分別對應到數字，用兩個 counter 記住。
- 共用一個 counter，用作乘法或除法。
- **3-counter = 2-counter**
- $(i,j,k)\rightarrow m=2^i3^j5^k$
- 另一個 counter，用作乘法或除法。
- **結論：TM = 2-stack = 2-counter**

## **Recursive Function Theory**
- Primitive Recursive Function 原始遞歸函數
- 常數函數：$0$
- 後繼函數：$S(k)=k+1$
- 投影函數：$\pi_i(x_1,x_2,x_3)=x_i$
- 複合： $h(X)=f(g_1(X),...,g_k(X))$
- 原始遞歸：
- $h(X,0)=f(X)$
- $h(X,S(n))=g(X,h(X,n),n)$
- 舉例：
- 加法：
- $add(x,0)=f(x)=\pi_1(x)=x$
- $add(x,S(n))=g(x,add(x,n),n)=S(\pi_2(x,add(x,n),n))$
- 乘法：
- $mul(x,0)=f(x)=0$
- $mul(x,S(n))=g(x,add(x,n),n)\\=add(\pi_1(x,mul(x,n),n),\pi_2(x,mul(x,n),n))$