计算理论导引-图灵机

复习使用

定义

图灵机形式定义：
$m=(Q,\Sigma,\Gamma,\delta,q_{0},q_{accept},q_{reject})$
(1) $Q$ 是状态集
(2) $Σ\Sigma$ 编入定义表
(3) $Γ\Gamma$ 带定义表， $ε⊆Γ,⊔⊆Γ\varepsilon \subseteq \Gamma,\sqcup \subseteq\Gamma$
(4) $δ:Q×Γ→Q×Γ×{L,R}\delta:Q\times\Gamma\to Q \times \Gamma \times\{L,R\}$
(5) $q_0$ 为初态
(6) $q_{accept}$ 为接受状态
(7) $q_{reject}$ 为拒绝状态
格局
我们用格局表示图灵机的当前状态，当前带内容和读写头的当前位置的信息。
在这里插入图片描述
上图就是一种格局，我们表示为 $1011q_701111$ ，意思为：当前带内容是101101111，当前状态为 $q_7$ ，读写头当前在第二个0上。格局中状态后的第一个字符为读写头指向的位置。
如果图灵机能合法的从格局 $C_1$ 一步进入到 $C_2$ ，则称格局 $C_1$ 产生格局 $C_2$ ，可表示为 $C1→MC2C_1 \underset{M}{\rightarrow} C_2$ ，这个概念的形式定义如下：
设a,b和c是 $Γ\Gamma$ 中的符号，u和v是 $Γ∗\Gamma^{*}$ 中的字符串， $q_i$ 和 $q_j$ 是状态，则 $uaq_ibv$ 和 $uq_jacv$ 是两个格局。如果转移函数满足 $δ(qi,b)=(qj,c,L)\delta(q_i,b)=(q_j,c,L)$ ，则说：
$uaq_ibv$ 产生 $uq_jacv$
这说明了图灵机左移的情况，下面是右移的情况。如果 $δ(qi,b)=(qj,c,R)\delta(q_i,b)=(q_j,c,R)$ ，则说：
$uaq_ibv$ 产生 $uacq_jv$

图灵机与DFA的区别

DFA：确定性有穷自动机
1.带上可读写
2.读写头可左右移动
3.带子无限长
4.接受和拒绝状态都会停机

其他相关定义

如果 $L(M)={w∈Σ∗∣∃u,v∈Γ∗,q0w→M∗uqacceptv}L(M)=\{w\in \Sigma^* |\exists u,v \in \Gamma^*,q_{0}w\xrightarrow[M]{*}uq_{accept}v\}$ 称 $w$ 是M接受（识别）的语言。
图灵可识别的/递归可枚举的( $r . e .$ )，定义为：
$L⊆Σ∗,r.e.⇔∃TMM(L=L(M))⇔∃TMM(∀w∈L,∃u,v∈Γ∗,(q0w∣→M∗uqacceptv))L\subseteq \Sigma^*,r.e.\Leftrightarrow \exists TM M(L=L(M))\Leftrightarrow\exists TM M\left ( \forall w \in L,\exists u,v \in \Gamma^*, \left ( q_0w |\xrightarrow[M]{*}uq_{accept}v\right )\right )$
图灵可判定的/图灵可递归的（recusive），定义为：
$L⊆Σ∗⇔∃TMM(∀w∈L,∃u,v∈Γ∗,(q0w∣→M∗uqacceptv)∧∀wˉ∉L,∃uˉ,vˉ∈Γ∗,(q0wˉ∣→M∗uˉqrejectvˉ))L\subseteq\Sigma^* \Leftrightarrow \exists TM M\left ( \forall w \in L,\exists u,v \in \Gamma^*, \left ( q_0w| \xrightarrow[M]{*}uq_{accept}v\right )\wedge\forall \bar{w} \notin L,\exists\bar{u},\bar{v} \in \Gamma^*, \left ( q_0\bar{w}| \xrightarrow[M]{*}\bar{u}q_{reject}\bar{v}\right ) \right )$
可递归的与可枚举的区别
1）可枚举的
在输入上运行TM时，可能达到停机状态，也可能达到循环即不停机状态
如果在，可达到这个状态，如果不在，没有回答
2）可判定的
对于任何输入，TM总能决定接受或者拒绝
如果在，可达到接受状态，如果不在，达到拒绝状态
可递归的与可枚举的联系
1）可判定的都是可识别的，可识别的不一定都是可判定的
2）设 $L⊆Σ∗,Lˉ=Σ∗−L,L is recusive， ⟺ L和Lˉ都是r.e.L\subseteq\Sigma^*,\bar{L}=\Sigma^*-L,L \, is \,recusive，\iff L和\bar{L}都是r.e.$
不是可识别的
$ATM‾、EQTM、EQTM‾、ETM\overline{A_{TM}}、EQ_{TM}、\overline{EQ_{TM}}、E_{TM}$
不是可递归的
$ATM、ATM‾、ETM、NETM、HALTTM、PCP、REGULARTMA_{TM}、\overline{A_{TM}}、E_{TM}、NE_{TM}、HALT_{TM}、PCP、REGULAR_{TM}$
通用图灵机：
$ATM={<M,w>∣TM M接受w}A_{TM}=\{<M,w>|TM \, M接受w\}$ ， $ATM is  r.e.(图灵可识别的)，ATM是不可判定的A_{TM} \,is\,\,r.e.(图灵可识别的)，A_{TM}是不可判定的$
构造 $\,U识别A_{TM}$
$U = "$ 对输入 $< M, w > ，其中 M 是一个 T M ， w 是一个串$ ：
$\quad\quad\quad\quad\quad\quad\quad\quad$ 在输入w上模拟 $M$
$\quad\quad\quad\quad\quad\quad\quad\quad$ 若 $M$ 停机，则停机 $"$
注意：如果 $M$ 在 $w$ 上循环，则 $U$ 在输入 $< M, w >$ 上循环，这就是 $U$ 不能判定 $A_{TM}$ 的原因。假如 $M$ 知道自己在 $w$ 上不停机，他能拒绝 $w$ ，但事实上，它不知道。图灵机 $U$ 是通用图灵机的一个例子。通用图灵机能模拟任何其他图灵机。
$\,U$ 识别 $M$

语言间的关系：
在这里插入图片描述
归约：
A，B两个问题（语言），A归约到B，若B可解，则A可解；若A不可解，则B不可解

时间复杂性
最坏情况分析：考虑在某特定长度的所有输入上的运行时间的最大值
平均情况分析：考虑在某特定长度的所有输入上运行时间的平均值
定义：令 $M$ 是一个在所有输入上都停机的确定型图灵机， $M$ 的运行时间（时间复杂度）是一个函数 $f:N→Nf:N\rightarrow N$ ，其中 $f (n)$ 是 $M$ 在所有长度n的输入上运行所经过的最大步数。若 $f (n)$ 是M的运行时间，则称M在时间 $f (n)$ 内运行， $M$ 是 $f (n)$ 的时间图灵机。
大O记法：
$f,g:N→R+，称f(n)=O(g(n))f,g:N\rightarrow R^+，称f(n)=O(g(n))$
$若∃c∈N+,∃n0∈N+,∀(n>=n0→f(n)<=cg(n))若\exist c \in N^+ ,\exist n_0 \in N^+ ,\forall( n >=n_0 \rightarrow f(n)<=cg(n))$
在这里插入图片描述
小o记法：
$f,g:N→R+，称f(n)=O(g(n))f,g:N\rightarrow R^+，称f(n)=O(g(n))$
$若lim⁡n→∞f(n)g(n))=0,∀c>0,∃n0∈N+,∀(n>=n0→f(n)<cg(n))若\lim_{n\to \infty }\frac{f(n)}{g(n))}=0,\forall c >0 ,\exist n_0 \in N^+ ,\forall( n >=n_0 \rightarrow f(n)<cg(n))$
在这里插入图片描述

时间复杂性类（time complexity class）
TIME（t(n))
令 $t:N→N,TIME(t(n))=L∣L是O(t(n))时间TM可判定的t:N\rightarrow N,TIME (t(n))={L|L是O(t(n))时间TM可判定的}$
$N是一个非确定的判定其，f:N\rightarrow N$
$N 的时间复杂性 f (n) 是任意长度为 n 的输入上， N 的所有分支达到接受态 / 最大的步数$
$定义 NTIME(t(n))={L|L是O(t(n))时间NTM可判定的}$
P类问题： TM多项式时间可判定的问题
NP类问题：NTM多项式时间可判定的问题

定理

1.设 $L⊆Σ∗,Lˉ=Σ∗−L,L is recusive， ⟺ L和Lˉ都是r.e.L\subseteq\Sigma^*,\bar{L}=\Sigma^*-L,L \, is \,recusive，\iff L和\bar{L}都是r.e.$
证明：1.必要性
1）显然L是可递归的 $⇒\Rightarrow$ L是递归可枚举的
2）L是可递归的 $⇒Lˉ\Rightarrow\bar{L}$ 是可递归的 $⇒Lˉ\Rightarrow\bar{L}$ 是递归可枚举的
2.充分性
1）设 $L(M)=L,L(Mˉ)=LˉL(M)=L,L(\bar{M})=\bar{L}$ ，构造 $T M O$ 如下：两个带上并行模拟M和 $Mˉ\bar{M}$ ，M接受，则O接受； $Mˉ\bar{M}$ 接受，则O拒绝，而 $w∈L(M)w\in L(M)$ 或 $w∈L(Mˉ)w\in L(\bar{M})$ ，故O必判定w，因此O判定L，L是递归的

存在性
使用反证法+对角线法证明

3.令 $x={0,1}，则xw是不可数的，xw是0,1无限序列的集合x=\left \{ 0,1 \right \}，则 x^w是不可数的，x^w是0,1无限序列的集合$
证明：设 $g:z+→xwg:z^+\rightarrow x^w$ ，得证 $g$ 不是满射（surjectivemap）
假设 $g$ 是一个满射，记 $g(i)=xi1…xii…xijg\left(i\right)=x_{i1}…x_{ii}…x_{ij}$
其中， $xi,j∈{0,1},i,j∈z+x_{i,j}\in \left \{ 0,1 \right \},i,j \in z^+$ ，构造 $y=y_1y_2….y_k….$
使得 $yk=1−xkk,k∈z+y_k=1-x_{kk},k\in z^+$
显然， $y∈xwy\in x^w$
由于y的第k位于g(x)的第k位不同， $\in z^+$
故有 $\notin \{ g(k)|k \in z^+\}$
即y不在g的象中
矛盾
因而g不是满射，故 $x^w$ 是不可数的

4.设A是一个集合，则A与 $z^A$ 不是一一对应的， $zA=P(A)z^A=\mathbb{P}(A)$
注： $z^A$ 是A的所有子集所组成的集合
证明：只须证明 $g:A→P(A)g:A\rightarrow\mathbb{P}(A)$ 不是满射即可
反证：假设g是一个满射
令 $B={a∈A∣a∉g(a)}B=\{a\in A|a\notin g(a)\}$
由于 $B⊆AB\subseteq A$ ，则存在 $b∈A,满足g(b)=Bb\in A,满足g(b)=B$
则有 $b∈B⇔b∉Bb\in B \Leftrightarrow b\notin B$
矛盾，故g不是满射，A与 $z^A$ 不是一一对应的
解释：
存在 $b∈A,满足g(b)=Bb\in A,满足g(b)=B$ （因为满射，所以对于B一定有 $b∈Ab\in A$ 与之对应）
则有 $b∈B⇔b∉Bb\in B \Leftrightarrow b\notin B$
（若 $b∈B⇒b∉g(b)⇒b∉Bb\in B\Rightarrow b\notin g(b)\Rightarrow b\notin B$ ，若 $b∉B且b∈A⇒b∈A并且b∈g(b)⇒b∈Bb\notin B且b\in A \Rightarrow b\in A 并且 b\in g(b)\Rightarrow b\in B$ ）

5.设 $ATM={<M,w>∣TM M接受w}A_{TM}=\{<M,w>|TM \, M接受w\}$ ，则 $A_{TM}$ 不是递归的，不是图灵可判定的。
证明：设 $A_{TM}$ 是可判定的，则判定器为 $H$ 。
$H(<M,w>)={accept，if M acceptreject,if M rejectH(<M,w>)=\left\{\begin{matrix} accept，if \, M \, accept\\ reject,if \, M \, reject \end{matrix}\right.$
构造 $TM DTM\, D$ ，使 $H$ 成为其子程序，识别 $H$ 的行为， $D$ 则与其行为相反，则
$D(<M>)={accept，if M reject <M>reject,if M accept <M>D(<M>)=\left\{\begin{matrix} accept，if \, M \, reject \,<M>\\ reject,if \, M \, accept\, <M> \end{matrix}\right.$
若输入 $< D >$ ，则有
$D(<D>)={accept，if D reject d<D>reject,if D accept <D>D(<D>)=\left\{\begin{matrix} accept，if \, D \, reject \,d <D>\\ reject,if \, D \, accept \, <D> \end{matrix}\right.$
$\Leftrightarrow D拒绝<D>$ ，矛盾，
因而， $A_{TM}$ 不是可判定的
注：这个问题被称为接受问题

6. $ATM={<M,w>∣TM M接受w}A_{TM}=\{<M,w>|TM \, M接受w\}$ ， $ATM is  r.e.(图灵可识别的)A_{TM} \,is\,\,r.e.(图灵可识别的)$
证明：构造 $\,U="$ 对输入 $< M, w >$ ：
$\quad\quad\quad\quad\quad\quad\quad\quad$ 在串上模拟 $M$ 对输入 $w$ 的动作，
$\quad\quad\quad\quad\quad\quad\quad\quad$ 若 $M$ 停机，则停机 $"$
$\,U$ 识别 $M$

7. $ATM‾\overline{A_{TM}}$ 不是图灵可识别的，即不是递归可枚举的
证明：因为 $A_{TM}$ 是递归可枚举的，若 $ATM‾\overline{A_{TM}}$ 也是递归可枚举的，根据定理可得， $A_{TM}$ 是可判定的，与 $A_{TM}$ 是不可判定的，矛盾， $ATM‾\overline{A_{TM}}$ 不是图灵可识别的。

归约性
停机问题：
8. $HALTTM={<M,w>∣TM M∧M对w停机}HALT_{TM}=\{<M,w>|TM\,M \wedge M对w停机 \}$
$HALT_{TM}$ 是不可判定的，即不是递归的
证明方法：1).可以使用对角线法证明
2).使用归约法证明
$A_{TM}归约到HALT_{TM}$
证明（归约法）：
假设 $TM R判定HALTTM，基于TM R构造TM S，使得TM S判定ATMTM\, R判定HALT_{TM}，基于TM\,R构造TM\,S，使得TM\,S判定A_{TM}$
$S = " 输入 < m, w > :$
$\quad\quad$ 在输入 $< m, w >$ 上运行 $TM RTM\,R$ ，
$\quad\quad$ （1）若 $R$ 拒绝， $<m,w>∉ATM<m,w>\notin A_{TM}$ ， $S$ 拒绝
$\quad\quad$ （2）若 $R$ 接受， $<m,w>∈HALTTM<m,w>\in HALT_{TM}$ ， $M$ 对 $w$ 停机：
$\quad\quad\quad$ $M$ 接受 $w$ ， $S$ 接受
$\quad\quad\quad$ $M$ 拒绝 $w$ ， $S$ 拒绝
若 $R判定HALT_{TM}，则S判定A_{TM}$ ，但 $A_{TM}$ 不是递归的，所以 $HALT_{TM}$ 不是递归的

$ETM={<M>∣TM M∧L(M)=ϕ}E_{TM}=\{<M>|TM\,M \wedge L(M)=\phi \}$
$NETM={<M>∣TM M∧L(M)不等于ϕ}NE_{TM}=\{<M>|TM\,M \wedge L(M) 不等于 \phi \}$
9. $E_{TM},NE_{TM}$ 不是递归的
证明：
（1） $NE_{TM}是r.e.的$
利用通用 $TM UTM\,U$ 构造 $TM TTM\,T$
T="对于 $TM M的编码<M>TM\,M的编码<M>$
(1)猜测一系列M的输入 $wi∈Σ∗w_i\in\Sigma^*$
(2)在输入 $< M, w >$ 上运行 $TM UTM\,U$
若M接受 $w_i$ ，则接受
这样，若 $不等于\phi$ ，则 $<M>∈L(T)<M>\in L(T)$
反之，若 $=\phi$ ，则 $<M>∉L(T)<M>\notin L(T)$
故 $L(T)=NE_{TM}，NE_{TM} 是r.e.的$
（2） $NE_{TM}不是递归的$
$A_{TM}归约到NE_{TM}$
假设 $TM N判定NETM，基于TM N构造TM A，使得TM A判定ATMTM\, N判定NE_{TM}，基于TM\,N构造TM\,A，使得TM\,A判定A_{TM}$
$S = " 对输入 < m, w > :$
$\quad\quad$ 1）构造 $TM UTM\,U$ ="对输入 $x ：模拟 M 运行 w ，若 M 接受 w ，则 U 接受 x$ ，
$\quad\quad$ 2） $在输入 < U > 上运行 N$
$\quad\quad\quad$ $N$ 接受 $U$ ， $A$ 接受
$\quad\quad\quad$ $N$ 拒绝 $U$ ， $A$ 拒绝
显然，若 $TM N判定N，则TM A判定ATMTM\,N判定N，则TM\,A判定A_{TM}$ ，而 $A_{TM}$ 不是递归的，所以 $NE_{TM}$ 不是递归的
（3）由（1）（2）可知， $E_{TM}不是r.e.的$ ，故 $E_{TM}不是递归的$ 。
或：
$NE_{TM}不是递归的$ ，
若 $E_{TM}是递归的$ ， $NETM=ETM‾NE_{TM}=\overline{E_{TM}}$ ， $NE_{TM}是递归的$ ，所以 $E_{TM}不是递归的$

10.Res定理
$r . e .$ 语言的非平凡性质是不可判定的
注：问题 $L⊆Σ∗L\subseteq \Sigma^{*}$
$\quad$ 性质 $P⊆ZΣ∗\mathbb{P}\subseteq Z^{ \Sigma^{*}}$
非平凡的 $P不等于ϕ，P不等于ZΣ∗\mathbb{P}不等于\phi，\mathbb{P}不等于Z^{ \Sigma^{*}}$
注： $P\mathbb{P}$ 既不为空，也不为所有语言的集合
推论：
$REGULARTM={<M>∣TMM∧L(M)是正则的}\quad REGULAR_{TM}=\{<M>|TM_{M}\wedge L(M)是正则的\}$
$EQTM={<M1M2>∣TMM1,M2∧L(M1)=L(M2)}\quad EQ_{TM}=\{<M_1M_2>|TM M_1,M_2\wedge L(M_1)=L(M_2)\}$

11.POST问题（不重要）
定义：计算历史
$TM M，M∈Σ∗,M在w上的计算历史是一个格局系列：C1,C2,…,CiTM\,M，M\in \Sigma^*,M在w上的计算历史是一个格局系列：C_1,C_2,…,C_i$
$其中C_1是M在w上的起始格局，且C_i|—C_m，i=1,2,….$
$若C_l为接受格局，则称为接受历史$
$若C_l为拒绝格局，则称为拒绝历史$
POST对应问题
在这里插入图片描述
计算层次：

语言类别	计算过程	计算层次	注
递归的	算法	可计算的	可数的
递归可枚举的	程序	半可计算的	可数的
非r.e.的	无	不可计算的	不可数的

映射可归约性
在这里插入图片描述
12. $EQTM既不是r.e.的，也不是补r.e.的（即EQTM‾不是r.e的）}EQ_{TM}既不是r.e.的，也不是补r.e.的（即\overline{EQ_{TM}}不是r.e的）\}$
分析：要证 $EQTM不是r.e.的，即证ATM‾≤mEQTM，根据定理可得，只需证明ATM≤mEQTM‾EQ_{TM}不是r.e.的，即证\overline{A_{TM}}\leq mEQ_{TM}，根据定理可得，只需证明A_{TM}\leq m\overline{EQ_{TM}}$
证明：
<1> $EQ_{TM}不是r.e.的$
$计算 f 的图灵机为：$
$F=“对输入<M,w>：\quad F=“对输入<M,w>：$
$1.构造M1,M2\quad\quad 1.构造M_1,M_2$
$M1=“对x拒绝”\quad\quad M_1=“对x拒绝”$
$M2=“对x，模拟M执行w，若M接受，则M2接受”\quad\quad M_2=“对x，模拟M执行w，若M接受，则M_2接受”$
$2.输出<M1,M2>\quad\quad 2.输出<M_1,M_2>$
$由F：ATM≤mEQTM‾由F：A_{TM}\leq m\overline{EQ_{TM}}$
$F 是可计算函数$
$<M,w>∈ATM⇔<M1,M2>∈EQTM‾<M,w>\in A_{TM}\Leftrightarrow <M_1,M_2>\in \overline{EQ_{TM}}$
$故ATM‾≤mEQTM故\overline{A_{TM}}\leq mEQ_{TM}$
$而ATM‾不是r.e.的，故EQTM不是r.e.的而\overline{A_{TM}}不是r.e.的，故EQ_{TM}不是r.e.的$
<2> $EQTM‾不是r.e.的\overline{EQ_{TM}}不是r.e.的$
$计算 g 的图灵机为：$
$G=“对输入<M,w>：\quad G=“对输入<M,w>：$
$1.构造M1,M2\quad\quad 1.构造M_1,M_2$
$M1=“对x接受”\quad\quad M_1=“对x接受”$
$M2=“对x，模拟M执行w，若M接受，则M2接受”\quad\quad M_2=“对x，模拟M执行w，若M接受，则M_2接受”$
$2.输出<M1,M2>\quad\quad 2.输出<M_1,M_2>$
$由G：ATM≤mEQTM由G：A_{TM}\leq mEQ_{TM}$
$G 是可计算函数$
$<M,w>∈ATM⇔<M1,M2>∈EQTM<M,w>\in A_{TM}\Leftrightarrow <M_1,M_2>\in EQ_{TM}$
$故ATM‾≤mEQTM‾故\overline{A_{TM}}\leq m\overline{EQ_{TM}}$
$而ATM‾不是r.e.的，故EQTM‾不是r.e.的而\overline{A_{TM}}不是r.e.的，故\overline{EQ_{TM}}不是r.e.的$

13.计算 $x + y$
x的编码，记为 $lt;x>=1^x$
y的编码，记为 $lt;y>=1^y$
$m=(Q,\Sigma,\Gamma,\delta,q_{0},q_{accept},q_{reject})$
(1) $Q=\{q_0,q_1,q_2,q_3,q_{accept},q_{reject}\}$
(2) $Σ={0,1}\Sigma=\{0,1\}$
(3) $Γ={0,1,⊔}\Gamma=\{0,1,\sqcup \}$
(4) $δ\delta$ 的定义

–	0	1	$⊔\sqcup$
$q_0$	$q_{reject},0,R)$	$q_{1},1,R)$	$(qreject,⊔,R)(q_{reject},\sqcup,R)$
$q_1$	$q_{reject},0,R)$	$q_{1},1,R)$	$q_{2},1,R)$
$q_2$	$q_{reject},0,R)$	$q_{2},1,R)$	$(q3,⊔,L)(q_{3},\sqcup,L)$
$q_3$	$q_{reject},0,R)$	$(qaccept,⊔,R)(q_{accept},\sqcup,R)$	$(qreject,⊔,R)(q_{reject},\sqcup,R)$
$q_{accept}$	HALT	HALT	HALT
$q_{reject}$	HALT	HALT	HALT

(5) $q_0$ 为初态
(6) $q_{accept}$ 为接受状态
(7) $q_{reject}$ 为拒绝状态
解码得到z=x+y

计算理论导引-图灵机

定义

图灵机与DFA的区别

其他相关定义

定理

Published by

风君子

发表回复取消回复

定义

图灵机与DFA的区别

其他相关定义

定理

Published by

风君子

发表回复 取消回复

发表回复取消回复