个人用计算理论导引笔记（待补充）

一、正则语言

预备知识

字母表：任意非空有穷集合
字符串：用字母表中的字母组成的序列，比如 Σ = { 0 , 1 } , x = 01001 \Sigma=\{0,1\},x=01001 Σ={0,1},x=01001
连接：首尾连接，如$x=01001,w=abcde,xw=01001abcde$
（特别地，$x...x=x^n$，表示n个x首尾连接）
串长度：$x=01001,|x|=5$
空串：$\epsilon ,|\epsilon |=0,x^0=\epsilon$。
（空串$\ne$空格！）
子串&子序列：略
串的标准序：并非字典序！而是先比较长度，再逐位比较大小！
语言：由字符串组成的集合,令字母表为$\Sigma$（里面的串要根据标准序排列）
${\Sigma }^{\ast }$：$\Sigma$上有穷长度的串（包括$\epsilon$）
${\Sigma }^{+}$：$\Sigma$上正有穷长度的串（不包括$\epsilon$）
${\Sigma }^{’}$：$\Sigma$上无穷长度的串
$\Phi$:空语言
（与空串语言 { ε } \{\varepsilon\} {ε}不同！空串语言 { ε } \{\varepsilon\} {ε}也与空串$\epsilon$不同！）
语言连接：类似于笛卡尔积，两两搭配。 A B = { x y ∣ x ∈ a , y ∈ b } AB=\{xy|x\in a,y\in b\} AB={xy∣x∈a,y∈b}
（特殊地， { ε } A = A { ε } = A \{\varepsilon\}A=A\{\varepsilon\}=A {ε}A=A{ε}=A,$\Phi A=A\Phi =\Phi$）

确定性有穷自动机（DFA）

$M=(Q,\Sigma ,\delta ,q_0,F)$
$Q$：有穷状态集
$\Sigma$：输入字母表
$\delta :Q\times \Sigma \to Q$（转移函数，也就是映射关系）
（特殊地，$Q\times {\Sigma }^{\ast }\to Q$（多了个空串）为扩展转移函数）
$q_0$：初始状态
$F$：接受状态/终止状态
语言：能够被自动机接受的串集合， L ( M ) = { w ∈ Σ ∗ ∣ δ ( q 0 , w ) ∈ F } L(M)=\{w\in \Sigma^*|\delta(q_0,w)\in F\} L(M)={w∈Σ∗∣δ(q0​,w)∈F}
正则语言：可以被有穷自动机接受的语言/可以用正则表达式描述的语言

设计DFA

1. 确定状态集
2. 确定转移函数
3. 标注初始状态&终结状态

正则运算

正则语言对正则计算封闭！
正则语言的**交并补、差、对称差、连接、*（星号）**封闭！
A ∪ B = { x ∣ x ∈ A 或 x ∈ B } A\cup B=\{x|x\in A或x\in B\} A∪B={x∣x∈A或x∈B}
A B = { x y ∣ x ∈ A 且 y ∈ B } AB=\{xy|x\in A且y\in B\} AB={xy∣x∈A且y∈B}
$A^{\ast }=A^0\cup A^1\cup A^2\cup ...$（见前，包括$\epsilon$）

非确定性有穷自动机（NFA，含有$\epsilon$，下一个状态可以有若干种选择（包括0种））

筹码集：字符集中只有$\epsilon$与一种字符的语言
$M=(Q,{\Sigma }_{\epsilon },\delta ,q_0,F)$
$Q$：有穷状态集
$\Sigma$：输入字母表（ Σ ε = Σ ∪ { ε } \Sigma_{\varepsilon}=\Sigma\cup\{\varepsilon\} Σε​=Σ∪{ε}）
$\delta :Q\times {\Sigma }_{\epsilon }\to P(Q)$（转移函数）
$q_0$：初始状态
$F$：接受状态/终止状态

任何一个NFA都有等价的DFA！
一个语言是正则语言，当且仅当只有一个NFA可以识别！
（具体转换见其他）

正则表达式

定义

对于$R$，有

1. $a$表示语言 { a } \{a\} {a}，其中$a\in \Sigma$（包括$\epsilon$）
2. $\Phi$表示空语言
3. $R=(R_1\cup R_2)$是正则表达式
4. $R=(R_1\circ R_2)$是正则表达式
5. $R=(R_1^{\ast })$是正则表达式

则$R$是正则表达式

eg:数值常量：
{ + , − , ε } ( D D ∗ ∪ D D ∗ . D ∗ ∪ D ∗ . D D ∗ ) , D = { 0 , 1 , 2 , . . . , 9 } \{+,-,\varepsilon\}(DD^*\cup DD^*.D^*\cup D^*.DD^*),D=\{0,1,2,...,9\} {+,−,ε}(DD∗∪DD∗.D∗∪D∗.DD∗),D={0,1,2,...,9}
eg:72、3.14159、+7.、-.01

计算优先级

星号$\ast >$连接$>$并$\cup$

定理

Φ ∗ = { ε } \varPhi^*=\{\varepsilon\} Φ∗={ε}
$R\cup \Phi =R$
$R\epsilon =R$
R ∪ ε = R ∪ { ε } ≠ R R\cup \varepsilon=R\cup \{\varepsilon\}\neq R R∪ε=R∪{ε}=R
$R\Phi =\Phi \ne R$

正则表达式与一个确定自动机等价！

GNFA（广义非确定自动机,NFA的推广）

（与NFA不同的是，转移用的并非是单个字符，而是一个正则表达式！）
$G=(Q,\Sigma ,\delta ,q_{start},q_{accept})$
$Q$：有穷状态集
$\Sigma$：输入字母表（ Σ ε = Σ ∪ { ε } \Sigma_{\varepsilon}=\Sigma\cup\{\varepsilon\} Σε​=Σ∪{ε}）
δ : ( Q − { q a c c e p t } ) × ( Q − { q s t a r t } ) → R \delta:(Q-\{q_{accept}\}) \times (Q-\{q_{start}\}) \rightarrow R δ:(Q−{qaccept​})×(Q−{qstart​})→R
（与NFA不同的是，转移状态用的并非是单个字符，而是一个正则表达式！）
$q_{start}$：初始状态
$q_{accept}$：接受状态/终止状态

CONVERT(G)（过程函数）

对于任意GNFA G，$CONVERT(G)$与$G$等价！
对于$G$的状态数$k$，$k=2$时，$CONVERT(G)=\delta (q_{start},q_{accept})$。
当$k>2$时，令 q r i p ∈ Q − { q s t a r t } − { q a c c e p t } , Q ′ = Q − q r i p q_{rip}\in Q-\{q_{start}\}-\{q_{accept}\},Q'=Q-{q_{rip}} qrip​∈Q−{qstart​}−{qaccept​},Q′=Q−qrip​。
构造$G^{\prime }=(Q^{\prime },{\Sigma }_{\epsilon },{\delta }^{\prime },q_{start},q_{accept})$，如此循环直到$k=2$。
其中，对于每个非起始态$q_i$与每个非终结态$q_j$，${\delta }^{\prime }(q_i,q_j)=(R_1)(R_2)\ast (R_3)\cup (R_4)$
其中$R_1=\delta (q_i,q_{rip}),R_2=\delta (q_{rip},q_{rip}),R_3=\delta (q_{rip},q_j),R_4=\delta (q_i,q_j)$
（选择$i\to j$和$i\to (rip{)}^{\ast }\to j$的并集来转移状态不断递归）

转化方法

1. 增加新的起始点与终结点，并将其与原来的起始点/终结点用$\epsilon$连接
   （类似最大流的源点与汇点，使得起始点没有入度，终结点没有出度）
2. 合并平行边
   
3. 去除中心点（使得点减少更精简）
   
   以下图为例。
   1.添加新起始点s与新终结点a，用$\epsilon$连接。
   2.将状态2去消除中心点，变为$b(a\cup b{)}^{\ast }$后删除状态2
   3.将状态1去消除中心点，变为$a^{\ast }b(a\cup b{)}^{\ast }$，结束。
   （合并的时候，如果有不含$\epsilon$的部分，则消去所有$\epsilon$，否则不消去！）
   
   以下图为例。
   1.添加新起始点s与新终结点a，用$\epsilon$连接。
   2.将状态1去消除中心点。
   （消除路径经过1的、且不是回路的）
   （1）把$2\stackrel{a}{\to }1\stackrel{b}{\to }3$变为$2\stackrel{ab}{\to }3$
   （2）把$3\stackrel{b}{\to }1\stackrel{a}{\to }2$与$3\stackrel{a}{\to }2$变为$3\stackrel{ba\cup a}{\to }2$
   （消除新起始点/新终结点相关的）
   （3）把$s\stackrel{\epsilon }{\to }1\stackrel{a}{\to }2$变为$s\stackrel{a}{\to }2$
   （4）把$s\stackrel{\epsilon }{\to }1\stackrel{b}{\to }3$变为$s\stackrel{b}{\to }3$
   （消除路径经过1的、且是回路的）
   （5）把$2\stackrel{a}{\to }1\stackrel{a}{\to }2$与$2\stackrel{b}{\to }2$变为$2\stackrel{aa\cup b}{\to }2$
   （6）把$3\stackrel{b}{\to }1\stackrel{b}{\to }3$变为$3\stackrel{bb}{\to }3$
   3.将状态2去消除中心点。
   （1）将$s\stackrel{a}{\to }2\stackrel{\epsilon }{\to }a$与$2\stackrel{aa\cup b}{\to }2$变为$s\stackrel{a(aa\cup b{)}^{\ast }}{\to }a$
   （2）将$s\stackrel{b}{\to }3$与$s\stackrel{a}{\to }2\stackrel{aa\cup b}{\to }2\stackrel{ab}{\to }3$变为$s\stackrel{a(aa\cup b{)}^{\ast }ab\cup b}{\to }3$
   （因为$3\stackrel{\epsilon }{\to }a$，所以状态3也是终结状态）
   （3）将$3\stackrel{bb}{\to }3$与$3\stackrel{ba\cup a}{\to }2\stackrel{aa\cup b}{\to }2\stackrel{ab}{\to }3$变为$3\stackrel{(ba\cup a)(aa\cup b{)}^{\ast }ab\cup bb}{\to }3$
   （4）将$3\stackrel{\epsilon }{\to }a$与$3\stackrel{ba\cup a}{\to }2\stackrel{aa\cup b}{\to }2\stackrel{\epsilon }{\to }a$变为$3\stackrel{ba\cup a(aa\cup b{)}^{\ast }\cup \epsilon }{\to }a$
   4.将状态3去消除中心点。
   将$s\stackrel{a(aa\cup b{)}^{\ast }ab\cup b}{\to }3$、$3\stackrel{(ba\cup a)(aa\cup b{)}^{\ast }ab\cup bb}{\to }3$、$3\stackrel{ba\cup a(aa\cup b{)}^{\ast }\cup \epsilon }{\to }a$，
   与$s\stackrel{a(aa\cup b{)}^{\ast }}{\to }a$变为
   $s\stackrel{(a(aa\cup b{)}^{\ast }ab\cup b)((ba\cup a)(aa\cup b{)}^{\ast }ab\cup bb{)}^{\ast }(ba\cup a(aa\cup b{)}^{\ast }\cup \epsilon )\cup (a(aa\cup b{)}^{\ast })}{\to }a$
   

泵引理（一个正则语言一定存在泵长度）

若$A$是正则语言，则存在常数$p$（$p$为泵长度，类似最大循环节长度），若$s\in A$，$|s|\ge p$，
则$s=xyz$，并且满足：
（1）$\forall i\ge 0，x{y}^{i}z\in A$。
（2）$|y|>0$
（3）$|xy|\le p$

如果要证明一个语言不是正则的，则用反证法 。找一个反例即可。

二、上下文无关文法（CFG）

$G=(V,\Sigma ,R,S)$
$V$：有穷变元集
$\Sigma$：有穷终结符集
$R$：有穷规则集（形如$A\to w,w\in (V\cup \Sigma {)}^{\ast }$）
$S\in V$：初始变元
一个上下文无关语言(CFL)与上下文无关文法等价！

CFG生成

合并

对于原本的初始变元$S_1,S_2,...S_k$，新增规则$S\to S_1|S_2|...S_k$

正则语言生成

用DFA转化为等价的CFG（正则语言都是上下文无关语言！）
对于原DFA中$\delta (q_i,a)=q_j$（即$q_i\stackrel{a}{\to }{q}_j$），则令$R_i\to a{R}_j$
对于原DFA中$q_i\in F$（即$q_i$为终止状态），则令$R_i\to \epsilon$

语法分析树

文法歧义性

最左派生：每一步都优先替换最左边的变元
eg1:$<EXPR>$
$\Rightarrow <EXPR>+<EXPR>$
$\Rightarrow a+<EXPR>$
$\Rightarrow a+<EXPR>\times <EXPR>$
$\Rightarrow a+a\times <EXPR>$
$\Rightarrow a+a\times a$
eg2:$<EXPR>$
$\Rightarrow <EXPR>\times <EXPR>$
$\Rightarrow <EXPR>+<EXPR>\times <EXPR>$
$\Rightarrow a+<EXPR>\times <EXPR>$
$\Rightarrow a+a\times <EXPR>$
$\Rightarrow a+a\times a$
注意到最左派生产生歧义性，因此这是歧义文法。

乔姆斯基范式(CNF)

初始变元不能在式子右方出现
只允许如下形式规则：
$S\to \epsilon$
$A\to BC$
$A\to a$（任意终结符）

生成CNF

任何的CFG都有等价的CNF！

1. 添加新初始变元$S_0$与新规则$S_0\to S$（旧初始变元）
2. 处理所有的$\epsilon$规则：
   若有非初始变元$A\to \epsilon$，则删除之，并修改所有等式右边与$A$相关的内容。
   $B\to uAv$变为$B\to uv$。
   $B\to uAvAw$变为$B\to uvAw|uAvw|uvw$（三种不同的可能情况）
   $B\to A$变为$B\to \epsilon$。
   重复以上，知道删除所有$\epsilon$相关规则为止（$S_0\to \epsilon$除外）
3. 处理所有的单一规则：（左边单个对应右边单个）
   删除$A\to B$，并修改所有相关的内容。
   若有$B\to u$，则添加$A\to u$。
   重复以上，直到删除所有单一规则为止。
4. 处理$A\to u_1{u}_2...u_k$长规则：
   将其换成$A\to u_1{A}_1,A_1\to u_2{A}_2,......,A_k=u_{k-1}{u}_k$。
5. 处理终结符：
   引入新变元$U_i$与新规则$U_i\to a_i$。
   $A\to a_i{a}_j$换成$A\to U_i{U}_j$
   $A\to a_{i}B$换成$A\to U_{i}B$
   $A\to B{a}_i$换成$A\to B{u}_i$

$G:S\to ASA|aB$
$A\to B|S$
$B\to b|\epsilon$
求等价CNF。

（1）添加新初始变元$S_0$
$S_0\to S$
$S\to ASA|aB$
$A\to B|S$
$B\to b|\epsilon$
（2）处理B的$\epsilon$规则
$S_0\to S$
$S\to ASA|aB|a$
$A\to B|S|\epsilon$
$B\to b$
（3）处理A的$\epsilon$规则
$S_0\to S$
$S\to ASA|aB|a|SA|AS$（$S\to S$没有用，可以删去）
$A\to B|S$
$B\to b$
（4）处理单一规则$S_0\to S$
$S_0\to ASA|aB|a|SA|AS$
$S\to ASA|aB|a|SA|AS$
$A\to B|S$
$B\to b$
（5）处理单一规则$A\to B$
$S_0\to ASA|aB|a|SA|AS$
$S\to ASA|aB|a|SA|AS$
$A\to S|b$
$B\to b$
（6）处理单一规则$A\to S$
$S_0\to ASA|aB|a|SA|AS$
$S\to ASA|aB|a|SA|AS$
$A\to ASA|aB|SA|AS|a|b$
$B\to b$
（7）处理长规则$ASA$
$S_0\to A{A}_1|aB|a|SA|AS$
$S\to A{A}_1|aB|a|SA|AS$
$A\to A{A}_1|aB|SA|AS|a|b$
$B\to b$
$A_1\to SA$
（8）处理终结符$a$
$S_0\to A{A}_1|UB|U|SA|AS$
$S\to A{A}_1|UB|U|SA|AS$
$A\to A{A}_1|UB|SA|AS|U|B$
$A_1\to SA$
$B\to b$
$U\to a$
于是得到$G$对应的乔姆斯基范式。

下推自动机（PDA，通常指的是非确定性下推自动机）

由栈组成，每次读入字符后选择与栈顶字符匹配或压入栈。
$M=(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$
$Q$：有穷状态集
$\Sigma$：输入字母表（ Σ ε = Σ ∪ { ε } \Sigma_\varepsilon=\Sigma\cup\{\varepsilon\} Σε​=Σ∪{ε}）
$\Gamma$：栈字母表（ Γ ε = Γ ∪ { ε } \Gamma_\varepsilon=\Gamma\cup\{\varepsilon\} Γε​=Γ∪{ε}）
$\delta :Q\times {\Sigma }_{\epsilon }\times {\Gamma }_{\epsilon }\to P(Q\times {\Gamma }_{\epsilon })$（转移函数）
$q_0$：初始状态（$q_0\in Q$）
$F$：终结状态集（$F\subseteq Q$）

以此图为例，可以绘制出此自动机。
在栈的初始插入一个 $符号，用于判断是否为空栈。

上下文无关语言CFL

如果一个语言是上下文无关语言（CFL）$⟺$有下推自动机（PDA）识别这个语言。
CFL对正则运算封闭！
CFL对交$\cap$不封闭！（语言$A,B$是CFL，$A\cap B$不一定是CFL）
CFL对补运算不封闭！（语言$A$是CFL，$A^c$不一定是CFL）

CFL的泵引理（一个CFL必定有泵）

假设$A$为上下文无关语言，则存在常数$p$（泵长度，类似循环节最大长度），若$s\in A$，且$|s|\ge p$，
则$s=uvxyz$，其中
（1）$\forall i\ge 0,u{v}^{i}x{y}^{i}z\in A$
（2）$|vy|>0$
（3）$|vxy|\le p$

同正则文法一样，找出一个反例证明不是CFL即可！

eg1：证明 C = { a i b j c k ∣ 0 ≤ i ≤ j ≤ k } C=\{a^ib^jc^k|0\leq i\leq j\leq k\} C={aibjck∣0≤i≤j≤k}不是CFL。
prove：假设$C$为上下文无关语言，设$p$为泵长度，不妨令$s=a^p{b}^p{c}^p$。
则$s=uvxyz$，其中
（1）$\forall i\ge 0,u{v}^{i}x{y}^{i}z\in C$
（2）$|vy|>0$（即$v$与$y$至少含一种符号）
（3）$|vxy|\le p$（即$v$与$y$至多含两种符号，理由同上）

（1）：$v$与$y$仅含一种符号
①：$a$不在$v$与$y$之中，此时只可能是$\underset{p个}{\underbrace{a...a}}|\varnothing |\underset{p个}{\underbrace{b...b}}|\varnothing |\underset{p个}{\underbrace{c...c}}$，违背了$|vy|>0$，矛盾。
②：$b$不在$v$与$y$之中，此时只可能是$\underset{p-i个}{\underbrace{a...a}}|\underset{i个}{\underbrace{a...a}}|\underset{p个}{\underbrace{b...b}}|\underset{i个}{\underbrace{c...c}}|\underset{p-i个}{\underbrace{c...c}}$，违背了$|vxy|\le q$，矛盾。
③：$c$不在$v$与$y$之中，同①，矛盾。
（2）：$v$与$y$含两种符号
此时易知当$i>1$时，就不具有$a^p{b}^p{c}^p$的形式，即$i=0$或$i=1$，矛盾。（$\forall i\ge 0$才算成立）
综上，$C$不是CFL，证毕。

eg2：证明 D = { w w ∣ w ∈ { 0 , 1 } ∗ } D=\{ww|w\in\{0,1\}^*\} D={ww∣w∈{0,1}∗}不是CFL。
prove：假设$C$为上下文无关语言，设$p$为泵长度，不妨令$s=0^p{1}^p{0}^p{1}^p$。
则$s=uvxyz$，其中
（1）$\forall i\ge 0,u{v}^{i}x{y}^{i}z\in C$
（2）$|vy|>0$（即$v$与$y$至少含一种符号）
（3）$|vxy|\le p$（即$v$与$y$至多含两种符号）
（注意这里一定要挑一个合适的反例，例如$0^{p}10^{p}1$可以拆分为$\underset{p-1个}{\underbrace{\mathrm{0...0}}}|0|1|0|\underset{p-1个}{\underbrace{\mathrm{0...0}}}1$，是合法的。）

（1）$vxy$在前半部分里，即$vxy$在第一个$0^p{1}^p$内。此时随着$i$的变化，后半个$0^p{1}^p$的数量会与前半个不同，不匹配，矛盾。
（2）$vxy$在后半部分里，同上，矛盾。
（3）$vxy$横跨中间，则$v$与$y$不可以含两种符号，故$v$为$1^i$，$y$为$1^i$，同理$i$的变化会让头尾的两个$0^p$与$1^p$数量与内部的两个不同，不匹配，矛盾。
综上，$D$不是CFL，证毕。

三、图灵机

单带图灵机（TM）

有一个纸带序列与一个可以左右双向移动的读写头
$M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{acc},q_{rej})$
$Q$：有穷状态集
$\Sigma$：输入字母表（注意空格符$B\notin \Sigma$）
$\Gamma$：带字母表， Σ ∪ { B } ⊆ Γ \Sigma\cup\{B\}\subseteq\Gamma Σ∪{B}⊆Γ
$\delta$： Q × Γ → Q × Γ × { L , R } Q\times\Gamma\rightarrow Q\times\Gamma\times\{L,R\} Q×Γ→Q×Γ×{L,R}（转移函数，L/R表示左移/右移）
$q_0\in Q$：初始状态
$q_{acc}\in Q$：停机接受状态
$q_{req}\in Q$：停机拒绝状态，$q_{acc}\ne q_{rej}$
单带图灵机的格局（序列的当前状态）：$uqav$
$q$：当前状态
$uav$：当前带上的内容
$a$：当前的扫描符号
（即之前的序列$u$|当前的状态$q$|当前的扫描符号$a$|后面的序列$v$）
eg:对于带$101101111$,状态$q_7$正在扫描第五个字符$0$，其格局为$1011q_{7}01111$
初始格局：$q_{0}w$（w为输入串）
接受格局：$u{q}_{acc}av$
拒绝格局：$u{q}_{rej}av$
停机格局：$u{q}_{acc}av/u{q}_{rej}av$
（图灵机的计算结果只能是停机接受、停机拒绝、不停机）
若$\delta (q_i,b)=(q_j,c,L)$（L表示左移），则
$ua{q}_{i}bv$产生$u{q}_{j}acv$（将$b$变为$c$，$q_i$变为$q_j$后左移）
$q_{i}bv$产生$q_{j}cv$（已经在带最左端，不可再左移）
若$\delta (q_i,b)=(q_j,c,R)$（R表示右移），则
$ua{q}_{i}bv$产生$uac{q}_{j}v$（因为带一定可以继续右移，所以不需要分情况）
如何判断当前状态已经在带最左端：在当前位置写下某个特殊符号，让带头向左移动，若仍然检测到该符号则说明在最左端，否则恢复原来的符号。

图灵可识别=递归可枚举=计算可枚举=半可判定=半可计算
图灵可判定=递归=可解=能行=可判定=可计算

图灵可识别$\ne$图灵可判定！

图灵机的等价变形

多带图灵机（同时多个纸带）

δ : Q × Γ k → Q × Γ k × { L , R } k \delta:Q\times\Gamma^k\rightarrow Q\times\Gamma^k\times\{L,R\}^k δ:Q×Γk→Q×Γk×{L,R}k
$\delta :(q_i,a_1,...,a_k)=(q_j,b_1,...,b_k,\underset{k个}{\underbrace{L/R,L/R,...,L/R}})$
多带图灵机可转换为等价的单带图灵机！
图灵可识别$\iff$可用多带图灵机识别！

非确定性图灵机（NTM）

在左移/右移的基础上增加了“停止”状态$S$
d e l t a : Q × Γ → P ( Q × Γ × { L , R , S } ) delta:Q\times\Gamma\rightarrow P(Q\times\Gamma\times\{L,R,S\}) delta:Q×Γ→P(Q×Γ×{L,R,S})
因此计算NTM格局的方式变为了计算树（拥有多个非确定性分支）

每个非确定性图灵机（NTM）都有等价的确定性图灵机（DTM）！
图灵可识别$\iff$可用非确定性图灵机识别！
图灵可判定$\iff$可用非确定性图灵机判定！

识别器：输入$x$，输出$0/1/?$（停机拒绝/停机接受/不停机）
判定器：输入$x$，输出$0/1$（停机拒绝/停机接受，没有不停机）
转换器：输入$x$，输出$y$（输出一个串而非一位，通常用于计算函数）
产生器：输入$0^n$，输出$x_n$（生成序列）
枚举器：输入$\epsilon$，输出$x_1,x_2,x_3,...$（无输入，无遗漏，无多余，无顺序，可重复）

图灵可识别$\iff$图灵可枚举！

图灵机算法

对象编码写作<$O_1,O_2,...,O_k$>，表示对串$O_1{O}_2...O_k$进行一种编码转换。
eg:设定一种对$01$串编码的方式，将所有的字符重复出现1次，多个串拼接时用两个不同的字符作为间隔符拼接。
$x=010,y=11,$<$x,y$>$=001100101111$（$001100|10|1111$）

递归定理

存在可计算函数$q:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$，$\forall w$，$q(w)$是图灵机$P_w$的描述，单带图灵机$P_w$打印出$w$，然后停机。（一个函数如果可计算，则和图灵机等价！）

自我复制机：自己打印自己的图灵机。 $\forall x,SELF(x)=<SELF>$（不断地进行自我复制）
递归定理：假设单带图灵机$T$有计算函数$t:{\Sigma }^{\ast }\times {\Sigma }^{\ast }\to {\Sigma }^{\ast }$，则存在单带自动机$R$，其计算函数$r:{\Sigma }^{\ast }\times {\Sigma }^{\ast }\to {\Sigma }^{\ast }$，$\forall w,r(w)=t($<$R$>$,w)$
（$T$可以用$R$来代替，从而实现递归运算，将问题转化）

图灵机接受性问题

定义 A T M = { < M , w > ∣ 图灵机 M 能接受串 w } A_{TM}=\{<M,w>|图灵机M能接受串w\} ATM​={<M,w>∣图灵机M能接受串w}
一个图灵机能接受某些给定的串构成的语言， 是图灵可识别的！是不可判定的！

通用机：存在一个固定的图灵机$U$，对于任意图灵机$M$与输入$w$，$U(<M,w>)=M(w)$

图灵机极小性问题

极小图灵机：对于图灵机$M$，其描述的字符<$M$>是最短的。
（因为图灵机有无穷多种，每种都有等价的极小图灵机，因此$MI{N}_{TM}$是无穷语言。）
$MI{N}_{TM}$不是图灵可识别！

不动点(x=f(x))

递归定理的不动点形式：对于$\forall$可计算函数$t:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$，存在一个图灵机$F$，使得$t(<F>)$描述一个与$F$等价的图灵机。

四、可计算问题/不可计算问题

算法可解：存在处处停机的等价图灵机。

对于正则语言的可判定问题

A D F A = { < B , w > ∣ D F A   B 接受串 w } A_{DFA}=\{<B,w>|DFA\ B接受串w\} ADFA​={<B,w>∣DFA B接受串w}是可判定语言。
同理$A_{NFA}$是可判定语言。
A R E X = { < R , w > ∣ 正则表达式  R 派生串 w } A_{REX}=\{<R,w>|正则表达式\ R派生串w\} AREX​={<R,w>∣正则表达式 R派生串w}是可判定语言。
（因为DFA、NFA、REX提供给图灵机的都是等价的，图灵机能在这三种之间进行转换）
（DFA空性） E D F A = { < A > ∣ A 是 D F A 且 L ( A ) = ∅ } E_{DFA}=\{<A>|A是DFA且L(A)=\empty\} EDFA​={<A>∣A是DFA且L(A)=∅}是可判定语言
（DFA等价性） E Q D F A = { < A , B > ∣ A 与 B 都是 D F A 且 L ( A ) = L ( B ) } EQ_{DFA}=\{<A,B>|A与B都是DFA且L(A)=L(B)\} EQDFA​={<A,B>∣A与B都是DFA且L(A)=L(B)}是可判定语言。

关于上下文无关语言（CFL）的可判定问题

每一个CFL是可判定的！
A C F G = { < G , w > ∣ C F G   G 派生串 w } A_{CFG}=\{<G,w>|CFG\ G派生串w\} ACFG​={<G,w>∣CFG G派生串w}是可判定语言。
（CFG空性） E C F G = { < G > ∣ C F G   G ， L ( G ) = ∅ } E_{CFG}=\{<G>|CFG\ G，L(G)=\emptyset\} ECFG​={<G>∣CFG G，L(G)=∅}是可判定语言。
（CFG等价性） E Q C F G = { < G , H > ∣ C F G   G , H ， L ( G ) = L ( H ) } EQ_{CFG}=\{<G,H>|CFG\ G,H，L(G)=L(H)\} EQCFG​={<G,H>∣CFG G,H，L(G)=L(H)}是不可判定语言！

不可计算问题

有理数集可数，实数集不可数！

用对角化方法证明不可计算问题

对角化方法：在判定结果图上构造一个非图灵机后观察对角线上的判定结果。
eg：定义 A T M = { < M , w > ∣ 图灵机 M 能接受串 w } A_{TM}=\{<M,w>|图灵机M能接受串w\} ATM​={<M,w>∣图灵机M能接受串w}，
证明：$A_{TM}$不可判定。

证：
那只需用对角化法证明$D_{TM}$不可判定。
假设存在图灵机$H$可判定$A_{TM}$，即：
$H(<M>,w)=\{\begin{array}{ll}接受& M接受w\\ 拒绝& M不接受w\end{array}$
构造$D$=“对于输入<$M$>，$M$是图灵机”
在输入"$M,<M>$"上运行$H$，如果$H$接受则拒绝$D$，反之接受，即：
$D(<M>)=\{\begin{array}{ll}接受& M不接受<M>\\ 拒绝& M接受<M>\end{array}$
（M串是图灵机自己的编码，即所有w中的一部分，即$D_{TM}$是$A_{TM}$的特例。）
不妨令$M=D$，即：
$D(<D>)=\{\begin{array}{ll}接受& D不接受<D>\\ 拒绝& D接受<D>\end{array}$
显然矛盾，故原命题得证。
如图所示，对于$H(<M,<M>>)$，$D$的结果是反过来的，而$D<D>$上的结果却并不是全部接受。

非图灵可识别语言

对于$A$和$A$的补集$A^c/\overline{A}={\Sigma }^{\ast }-A$，A可判定$\iff$A与$A^c$图灵可识别。（可判定语言对布尔运算封闭）

归约法

（图灵机的停机问题） H A L T T M = { < M , w > ∣ 图灵机 M 在输入 w 上停机 } HALT_{TM}=\{<M,w>|图灵机M在输入w上停机\} HALTTM​={<M,w>∣图灵机M在输入w上停机}是不可判定的。
（图灵机空性问题） E T M = { < M > ∣ M 是图灵机且 L ( M ) = ∅ } E_{TM}=\{<M>|M是图灵机且L(M)=\emptyset \} ETM​={<M>∣M是图灵机且L(M)=∅}是不可判定的。
（图灵机正则性问题） R E G U L A R T M = { < M > ∣ M 为图灵机且 L ( M ) 正则 } REGULAR_{TM}=\{<M>|M为图灵机且L(M)正则\} REGULARTM​={<M>∣M为图灵机且L(M)正则}是不可判定的。
（图灵机等价性问题） E Q T M = { < M 1 , M 2 > ∣ M 1 和 M 2 是图灵机且 L ( M 1 ) = L ( M 2 ) } EQ_{TM}=\{<M_1,M_2>|M_1和M_2是图灵机且L(M_1)=L(M_2)\} EQTM​={<M1​,M2​>∣M1​和M2​是图灵机且L(M1​)=L(M2​)}是不可判定的。