计算性和复杂度理论2
本文系统性探讨了Turing理论基础下的各类问题分类：包括Turing可确定、不可确定以及半确定问题等核心议题。
在现有研究中, 对可判定与不可判定的术语存在不同的翻译方式, 为了便于讨论, 我们统一采用"可判定"与"不可判定"这一表述体系。
预备知识
可数与不可数集合
可数集合
称集合M为可数集，则满足以下条件：要么集合M为空；要么存在一个满射函数$c:\mathbb{N}\rightarrow M”。
- 所有可数集合中的元素都可以一一列举。
- 任何有限集合必然是可列的。
- 每个可计数且无限延伸的集合都会有一个双射函数f将其映射至自然数组成的\mathbb{N}。
- 所有具备无限元素且为可计数类型的集合都将具有与\mathbb{N}相同的基数。
可数集合举例：
由有限个符号构成的所有字符串组成的集合Σ*（例如：Σ={0,1}时，在康托尔排列下可以依次枚举出所有的二进制字符串）。这不仅包括单个符号如0和1本身。
\epsilon,0,1,00,01,10,11,000,001,010,011,100,101,...
- 集合中的哥德尔数（Gödel numbers）聚焦于字母集{0,1}。
因为每个元素在这一集中都可以对应字母表中的特定符号。 - 所有图灵机（Turing machines）构成了一个独特的集合。
因为每个机器都可以通过一个特定的哥德尔编号（Gödel number）来表示。
符号
对于二维字母集合\Sigma=\{0,1\}我们将在卡农顺序下的第i个词表示为w_i
对于第i个卡农顺序下的图灵机Gödelnummer我们记为M_i
不可数聚合
定理：自然数集的幂集\mathcal{P}(\mathbb{N})是不可数的
证明：反证法
假设\mathcal{P}(\mathbb{N})是可数的
那么令S_0,S_1,S_2,S_3,...为一个\mathcal{P}(\mathbb{N})的枚举
我们定义一个二维无限的邻接矩阵(A_{i,j})_{i,j\in \mathbb{N}}
A_{i,j}= \begin{cases} 1& \quad 如果j\in S_i\\ 0& \quad 其他 \end{cases}
上述两行分别定义对角线集合S_{diag}和其补集\bar S_{diag}
注
现在有两种情况，都可以导致矛盾：
当矩阵元素 A^{(m)}_ {i,j} 等于 1 时，默认情况下（按照 \overline{S}_{ diag }^{(m)} 的定义），元素 i,j 不包含于集合 \overline{S}_{ diag }^{(m)} 中；因此也不包含于对应的集合 S^{(m)} _ {i,j } 中。基于矩阵 B^{(m)} _ {i,j } 的构造方式，则得出结论：(B^{(m)}) _ {i,j }=0. 当然这与假设条件矛盾
当矩阵元素 A^{(m)}_ {i,j }= 0 时，默认情况下（按照 \overline{S}{ diag }^{(m)} 的定义），元素i, j 包含于集合 \overline{S}{ diag }^{(m)} 中；因此也包含于对应的集合 S^{(m)} _ {i,j } 中。基于矩阵 B^{(m)} _ {i,j } 的构造方式，则得出结论：(B^{(m)}) _ {i,j }=1.$ 这与假设条件一致
所以不存在\mathcal{P}(\mathbb{N})的枚举，因此不可数
不可判定问题
对角线语言
定义：D=\{w\in\{0,1\}^*|w=w_i且M_i不接受w\}
换句话说，在按照卡农顺序排列的二元符号序列空间\{0,1\}^*中属于对角线语言D的第i个词w_i（即按照卡农顺序编号为i的图灵机M_i），当且仅当该图灵机M_i（按照卡农顺序编号）不接受该词w_i。
说明 ：这里图灵机 M_i 未被接受的情况有两种：1. 图灵机 M_i 被拒绝接收输入项；2. 图灵机 M_i 无法完成对输入项的处理。
定理：对角线语言D是不可判定的
证明：反证法
假设对角线语言D是可判定的，则存在一个M_j，可以判定D
对角线语言补集的不可判定性
相似的，对角线补集的定义为\bar D=\{w\in\{0,1\}^*|w=w_i且M_i接受w\}
定理：对角线语言补集\bar D是不可判定的
证明：反证法
假使可计算性问题类\overline{D}是可以被某台图灵机解决的，
那么必然存在着一台特定的图灵机\overline{M}_{\overline{D}}}，
其功能就是识别该类问题类\overline{D}。
基于此，
我们可以借助该核心组件，
构建出另一台能够识别对角线语言
L = \{\langle M\rangle | M \text{接受}\langle M\rangle \}\}
的新机器，
从而导致矛盾的发生。
如下构造：
子程序技术
上面的这个证明过程就用到了子程序技术
其具体方法为：
已存在一可被证实为非递归的语言标记为L'。需展示新的语言标记为L具有不可递归性；若构建包含子程序图灵机 M_L(此TM可识别
语言标记为L)的主程序图灵机能够识别
语言标记为L'。
观察 ：
当一个语言L\subseteq\{0,1\}^*不可判定 时，那么他的补集也不可判定
同样的当一个语言L\subseteq\{0,1\}^*可判定 时，那么他的补集也可判定
停机问题
定义：H = \{
注：停机问题是所有图灵机Gödelnummer
定理：停机问题H是不可判定的
证明：子程序
- 基于输入w及其在卡农顺序中的位置i（即确定对应的元素为w_i = w），随后通过下标i获得其对应的Gödel数。
- 将符号串
w_i 输入至2号子程序 M_H 中，在以下条件下处理：- 如果 M_i 在处理 w_i 时无法停止，则拒绝；
- 如果能够停止，则接受并转移至第3号程序。
（此处因 M_H 接受符号串w_i 只能表明它确认了该符号串属于某个特定类型，并不涉及对角线语言补集的具体性质）
- 通用图灵机执行模拟任务：对于给定的输入符号串
w_i ，系统会模仿执行程序的行为过程。
（由于前面已确认过该符号串会被接受到第2号程序中，
所以在此之后的模拟行为自然也会被正确处理）
正确性证明 ：
需要证明：
- w \in \bar D \Rightarrow M_{\bar D} 接受w
- w \notin \bar D \Rightarrow M_{\bar D} 拒绝w
\epsilon-停机问题
定义：H_\epsilon = \{
定理：\epsilon-停机问题H_\epsilon是不可判定的
证明：子程序技术
首先判断输入是否是以正确的Gödelnummer开始的，如果不是，则直接拒绝
当输入格式正确时，则基于该输入构建一个新的图灵机Gödelnummer
假设字符串\epsilon被包含在构造好的机器中，则当该机器执行时（此处表示该操作完成后），它会立即在其磁带上写下字符w，并切换到状态以开始模拟原始图灵机的行为（即当前操作完成后），这等价于下面所述的情况：如果原始图灵机无法停止，则不会被接受者所接受）。
2）当输入字符串不为空字符串时，在证明过程中无需关注M^*_w的行为。我们假设该自动机将陷入死循环（即永远运行下去）。
将Gödelnummer
正确性证明：
对于那些不符合
莱斯定理
由图灵机计算的偏分方程具有以下形式：
f_M:\{0,1\}^*\rightarrow \{0,1\}^*\cup\{\bot\}
对于判定问题有以下形式：
f_M:\{0,1\}^*\rightarrow \{0,1,\bot\}
其中0表示拒绝，1表示接受，\bot表示不停
定理内容：
令\mathcal{R}是由图灵机计算的所有偏分方程的集合。
令集合 \mathcal{S} 被称为集合 \mathcal{R} 的一部分，并且必须满足以下条件之一：第一是空集严格包含于 \mathcal{S} ；第二是 \mathcal{S} 严格包含于全集；第三是非空集合同时又不等于全集
则语言L(\mathcal{S}) =\{
注：莱斯定理仅适用于对可计算函数进行哥德尔编号的图灵机设计，并不涉及对图灵机运行时长及其运行过程的具体考量。
证明：M_{L(\mathcal{S})}作为M_\epsilon的子程序
令u为一般的未定义的函数u(w)\equiv \bot
u\notin \mathcal{S}
令f是\mathcal{S}里的一个函数
令N是一个计算f的图灵机
如果输入不是由正确的Gödelnummer组成，M_\epsilon则拒绝这个输入
否则，M_\epsilon则从输入
输入x在M^*上的行为如下：
首先，在预先设定好的路径上（此处指Spur），模拟器M^*模仿图灵机M在输入空字符串\epsilon\$时的行为。若图灵机M无法停机，则模拟器M^*同样无法完成模拟任务。其计算结果等同于函数u(w)恒等于无定义值\bot$”，从而导致随后构建的机器$L_{\mathcal{S}}$必定会以拒绝状态运行。
2）随后系统M^*执行图灵机N对输入为x的操作。每当图灵机N完成停止动作，则其结果也会让系统M^*停止运行，并将该结果作为自身的输出。（此处指当系统\epsilon在机器M上完成停机过程时，则需要运行子程序N接受输入x并将其处理后的结果作为f(x)返回）
最后将该字符串
正确性证明：
封闭性
当语言L是可判定的，那么它的补集\Sigma^*-L也是可判定的
当两个语言L_1和L_2是可判定的，则
- L_1\cap L_2可判定
- L1\cup L_2可判定
可判定的语言集合在交并补下面是封闭的
递归可枚举性与归约
一个语言L被一个图灵机M所判定，当
- 对于任何一个输入M都会停
- M只接受来自于L里的词
一个语言L会被一个图灵机所识别，当
- M接受所有来自于L里的词
- M不接受任何一个不是L里的词
如果存在一台图灵机M, 能够识别集合L, 则我们称这种语言L为半可判定的（semi-entscheidbar）。
递归可枚举性
一个枚举装置对应于一个语言L\subseteq\Sigma^*是图灵机的一种变体，并与之配套的打印机相连
该打印机可被视为一个附加的输出端口。该打印机上的读取头仅限于在该带上向右移动，并且仅能执行写操作。
- 枚举器将从一个空的工作带启动，并随着时间的推移不断输出来自集合L的所有单词至打印机。
- 输出的每个词将通过一个不属于Σ的分隔符进行分割。
- 枚举器仅打印属于集合L中的单词。
定义：当一个语言L有一个枚举器时，则称L是递归可枚举的
定理：一个语言L是递归可枚举的，当且仅当L是半可判定的
证明：
递归可枚举\rightarrow半可判定
设L为一递归 enumerable集合，并设A为其枚举器。按照以下步骤构建图灵机M: 首先初始化状态寄存器；其次根据输入字符串逐步模拟A的行为；最后若处于接受状态则接受该输入字符串
沿着一条带子进行模拟操作以实现枚举器A的工作流程，并将其输出至该带上实现了打印机功能的转移
每当图灵机M在带子上打印出一个单词后
正确性：
当w\in L，则在某一时刻，w必然会被打印出来，那么这时候M会输出接受
当w\notin L，则w永远都不会被打印出来，M就会不停也就不会输出接受
半可判定\rightarrow递归可枚举
我们假定语言L为半可判定，并由图灵机M进行识别。为此目的，请按照以下步骤构建枚举器A用于生成语言L。
注：我们的目标是将能够被图灵机M接受的词汇输出打印出来。然而存在一些词汇可能导致图灵机M进入无限循环而不停机的状态。因此我们需要找到一种方法来模拟这些词语的行为。为此我们采用了一种分阶段模拟的方法通过多轮次模拟逐步覆盖所有可能的情况
在第k轮里（k=1,2,3,…）
枚举器A用图灵机M模拟w_1,w_2,...,w_k中每个词，并且每个词只运行k步
在模拟过程中每当M接受了某个词，那么枚举器A就会把这个词打印出来
正确性：
显然，在构造出来的这个枚举器中仅限于属于集合 L 的词。那么有必要考察该枚举器是否能够输出所有属于集合 L 中的单词。
- 我们定义符号表示为：令符号表示为s = w_1, w_2, ..., w_n。
- 其中s ∈ L^+是一个由n ≥ 1个连续的非空字符组成的字符串。
- 那么对于任意给定的字符串s ∈ L^+和图灵机M，在有限步骤t(s)内能够被图灵机M接受。
封闭性
当两个语言L_1和L_2是递归可枚举的，则
- L_1\cap L_2递归可枚举
- L1\cup L_2递归可枚举
引理：
假设某个语言L\subseteq\Sigma^*及其补集\bar L:=\Sigma^*-L均为递归可枚举，则该语言L是可判定的。
用子程序技术即可证明这个引理
\bar H和\bar H_\epsilon不是递归可枚举的
证明：鉴于停机问题H属于递归枚举集合，在这种情况下若\bar H同样构成一个递归枚举集合，则依据前述引理可知该停机问题具有可判定性。然而实际上该停机问题是不可判定的这一事实表明\bar H并非属于此类集合。
同理\bar H_\epsilon不是递归可枚举的。
可计算性语言分类
观察：每一个语言L都属于以下四个类别里中的一个
- 该语言是可以被决定的（其中,L与其补集都属于递归可枚余集合）
- 语言$L属于Recursively Enumerable类,然而其补集\overline{L}则不属于该类.
- 补集语言\overline{L}属于Recursively Enumerable类别,但原语言L并不属于此类.
- 对于语言S,它以及它的补集\overline{S}都未能实现Recursively Enumerable的目标.
归约
设L_{1}和L_{2}为基于字母表\Sigma的形式语言。我们称为可归约的，并记作L_{1}\leq L_{2}, 当且仅当存在一个可计算函数f:\Sigma^{*}\rightarrow\Sigma^{*}满足: 对于所有x\in\Sigma^{*}有x\in L_{1} \Leftrightarrow f(x)\in L_{2}.
即x \in L_1 \Rightarrow f(x)\in L_2;x\notin L_1 \Rightarrow f(x)\notin L_2
定理：如果两个语言L_1\le L_2
L_2可判定的\quad \Rightarrow \quad L_1可判定的
L_2递归可枚举的\quad \Rightarrow \quad L_1递归可枚举的
L_1不可确定的\quad \Rightarrow \quad L_2不可判定的
L_1不是递归可枚举的\quad \Rightarrow \quadL_2不是递归可枚举的
使用子程序技术即可证明：
完全停机问题
定义：H_{tot} = \{
就是H_{tot}里的图灵机不存在对于某个输入会不停
定理：\bar H_{tot}和H_{tot}都不是递归可枚举的
证明：
已知\bar H_\epsilon不是递归可枚举的，那么需要证：
- \bar H_\epsilon \le \bar H_{tot}
- \bar H_\epsilon \le H_{tot}
\bar H_\epsilon \le \bar H_{tot}
定义一个可计算函数f。对于任意属于\Sigma^*的符号串x而言：
- 如果x属于\bar{H}_\epsilon集合，则f(x)必定属于\bar{H}_{tot}；
- 如果x不属于\bar{H}_\epsilon集合，则f(x)也不会属于\bar{H}_{tot}。
其构建过程如下：
令w是\bar H_\epsilon的一个输入
当w不是哥德尔数时，直接令f(w) = w
当设w=
M_\epsilon^*忽略它的输入直接模拟M在输入为\epsilon时的行为
正确性证明：
w\in \bar H_\epsilon \Rightarrow f(w)\in \bar H_{tot}
w\notin \bar H_\epsilon \Rightarrow f(w)\notin \bar H_{tot}
首先当w不是哥德尔数时，满足w\in \bar H_\epsilon和f(w)\in \bar H_{tot}
当w=
\bar H_\epsilon \le H_{tot}
定义一个可计算函数f为：对于任意属于\Sigma^*的字符串x来说，在满足x\in \bar H_\epsilon的情况下有f(x)\in H_{tot}；当且仅当x\notin \bar H_\epsilon时，则有f(x)\notin H_{tot}。其构建过程如下：
令w是\bar H_\epsilon的一个输入。令w'是来自于H_{tot}的任意一个输入。
当w不是一个有效的哥德尔数时，令f(w) = w'
当给定一个有效的Gödel编码值< M >时，则设定函数f(< M >)等于< M ' >；对于任何长度为l的输入字符串x，在执行过程中：
1. 将符号序列x复制到工作带上；
2. 模拟图灵机M'的状态转移表；
3. 根据当前状态和工作带内容确定下一个操作；
4. 若当前状态属于终止状态则停止运算；
5. 否则继续执行下一步骤。
在执行过程中，在完成l个步骤内的任务时（即模拟输入ε到该机器的状态机上），若该机器在此前的l步后已停止运行，则会导致该辅助机器（记作M'）陷入无限循环；否则，在这l步中未能停止时，则会导致该辅助机器（记作M'）终止工作。
正确性证明：
w\in \bar H_\epsilon \Rightarrow f(w)\in H_{tot}
w\notin \bar H_\epsilon \Rightarrow f(w)\notin H_{tot}
首先当w不是哥德尔数时，满足w\in \bar H_\epsilon和f(w) = w'\in H_{tot}
当w=
解题思路
可判定证明：
构建能够识别并接纳属于该语言的所有词汇的图灵机，并且不识别也不接纳不属于该语言的任何词汇
使用可计算性问题交并补的封闭性
证明该语言和其补集都是递归可枚举的
不可判定证明：
- 通过diagonalization方法构造一个矛盾的情况，在出现第i个语言的问题时（即当Mi不接受该语言），就可以应用某种技术来解决这个问题。
- 如果所讨论的问题涉及图灵机计算某个偏函数，则可以直接应用Rice定理来得出结论。
- 使用reduction技术将已知不可判定的问题归约到当前研究的问题上。
- 子程序技术
递归可枚举证明：
设计一台能够识别语言L中所有词的图灵机；该图灵机具备识别语言L中所有词的能力；而那些不属于语言L的其他词则无法被识别。
不可递归可枚举证明：
- 首先论证问题的non-decidability, 然后确定其complement是否属于recursively enumerable类别。
- 通过reduction的方法将一个非r.e.的问题转化为当前问题。