计算性和复杂度理论1

本系列文章是对可计算性和复杂度理论的简要概括，很大部分是对课件的翻译，中间掺杂着部分个人的理解，如有问题欢迎联系我修改。附课件地址：https://algo.rwth-aachen.de/Lehre/WS1920/BuK/BuK.py

本文是第一部分，理论基础部分，主要介绍了图灵机和寄存器RAM。

预备知识

时间复杂度三个符号O-,\Omega-和\Theta-的定义：

O(g(n)) = \{f(n)\ |\ \exist c>0, \exist n_0,\forall n\geq n_0:\quad 0\le f(n) \le c \cdot g(n)\}

\Omega(g(n)) = \{f(n)\ |\ \exist c>0, \exist n_0,\forall n\geq n_0:\quad 0 \le c \cdot g(n)\le f(n)\}

\Theta(g(n)) = \{f(n)\ |\ \exist c_1,c_2>0, \exist n_0,\forall n\geq n_0:\quad 0\le c_1 \cdot g(n)\le f(n) \le c_2\cdot g(n) \}

\qquad \quad \ \ =O(g(n)) \cap\Omega(g(n))

另外还有通过极限来定义：

f\in O(g) \Leftrightarrow 0 \le \limsup_{x\rightarrow \infty} | \frac{f(x)}{g(x)} | < \infty

f\in \Omega(g) \Leftrightarrow 0 < \liminf_{x\rightarrow \infty} | \frac{f(x)}{g(x)} | \le \infty

f\in \Theta(g) \Leftrightarrow 0 < \liminf_{x\rightarrow \infty} | \frac{f(x)}{g(x)} | \le\limsup_{x\rightarrow \infty} | \frac{f(x)}{g(x)} | < \infty

图灵机

图灵机组成

一个图灵机被定义成一个7元组：

（Q,\Sigma,\Gamma,B,q_0,\bar q,\delta）

Q：有限的状态集合

\Sigma：有限的输入字母集合

\Gamma \supset \Sigma：有限的图灵机带上的子母集合

B\in \Gamma \setminus \Sigma：表示为空的符号

q_0 \in Q： 起始状态

\bar q \in Q：终止状态

\delta : (Q\setminus {\bar q})\times \Gamma \rightarrow Q \times \Gamma \times\{R,L,N\}：状态转移方程

图灵机的运行机制

例：对于下面一个判断语言里的词是否以1为结尾的图灵机：（即判断一个词是否来自于L=\{w1|w\in\{0,1\}^*\}）

M = (Q,\Sigma,\Gamma,B,q_0,\bar q,\delta)

Q = \{q_0,q_1,\bar q\}

\Sigma = \{0,1\}

\Gamma = \{0,1,B\}

状态转移方程：

\delta	0	1	B
q_0	(q_0,B,R)	(q_1,B,R)	reject
q_1	(q_0,B,R)	(q_1,B,R)	accept

运行过程：

首先图灵机的初始状态为q0，

• 如果输入为空，那么对应的从状态转移方程表格中找“B”那一列，对应q0行“reject”，图灵机停止，即该图灵机不接受\epsilon。
• 如果输入第一个字符为1，那么对应从q0行找1那一列，相应的操作是状态改为q1，把读取头下面的字符改为”B“，读取头右移。（也就是状态变为q1，第一位字符改为B）
• 依次类推其他情况

那么这个图灵机的设计思路就是找到输入的最后一个字符，然后判断其是否为1。判断最后一个字符就是在第一次读取到“B”的时候，说明已经读取完输入的所有字符，然后该图灵机用两个状态，在q0时读到B的情况是最后一个字母是0或者输入为空，那么相应的就要拒绝这个输入；在q1读取到B的情况是最后一个字母为1的时候，满足条件，接受。

个人认为状态转移方程就如同说明书，告诉图灵机在当前状态读取到图灵机带上的某个字母该做什么操作。因此对于一个特定的图灵机来说，他的状态转移方程是不变的（或者说是不可变的），机带上的字母，读取头的位置是会变的。

图灵机停止

1. 当图灵机到达终止状态，图灵机会停止
2. 然后输出词y\in \Sigma^*可以从带子上面读取：y从读取头开始到第一个空符结束（\Gamma\setminus\Sigma）

特别的：

1. 图灵机接受一个输入词，当他结束并以1输出
2. 图灵机不接受一个输入词，当他停止时输出不为1

运行时间 ：图灵机直到终止时运算的步骤

内存需求 ：图灵机在运算过程中访问过的带子上不同的格子数

图灵可计算性

一个函数f:\Sigma^*\rightarrow\Sigma^*称为可递归的（图灵可计算的），当存在一个图灵机，其对于每一个输入x都能输出f(x).

一个语言L\subseteq\Sigma^*称为可递归的（图灵可计算的），当存在一个图灵机，其对于所有的输入都会停。且输入w会被接受，当且仅当w\in L

组态konfiguration

\alpha q \beta：在图灵机带上有着\alpha \beta一串字符，字符以外区域都为空，图灵机当前状态为q，读取头位于\beta的左边第一个字符处

\alpha q \beta \vdash \alpha' q'\beta'

注意konfiguration的走向是一直向右，当遇到转移方程是L想左移动时，则将q左移一个还是向右走。（其实这里就是保证跟上面定义的那样，使读取头一直保持在\beta的第一个字符处）

k路径图灵机（k-spurige TM）

定义：一个图灵机，其带子是由多个路径组成的，也就是说在每个带子单元，都有k个字符，读取头会同时读取这些字符。

\Gamma_{neu} := \Gamma \cup\Gamma^k

多带图灵机

K-Band-TM ：一个k带图灵机是图灵机的一般化形式。它拥有k条工作带，且每一条带都有互不相关的读取头。

状态转移方程（\delta）：\delta:(Q\setminus{\bar q})\times\Gamma^k \rightarrow Q \times \Gamma^k \times \{L,R,N\}^k

第一条带为输入或输出带（和单带图灵机一样）

其余k-1条带起始是都为空（只有B）

**定理：**一个时间复杂度为t(n)和空间复杂度为s(n)的k带图灵机M可以被一个单带图灵机M'在时间复杂度O(t^2(n))和空间复杂度O(s(n))条件下模拟出来

证明：用2k-spurige单带图灵机模拟k带图灵机。

k带图灵机的每一步可以用单带图灵机M‘如下模拟：

1. 开始时M’的读取头处在最左边含有#的那个单元，且M’知道M的当前状态
2. 读取头开始向右移动知道碰到最右边的那个含有#的单元，与此同时M’将读取到有#的k个字符存入当前状态里
3. 当到达最右边含有#的单元后，M’可以将M的当前状态与第二步读取到的k个字符放入M的状态转移方程中来获取Q\times \Gamma^k \times \{L,R,N\}^k
4. 现在M’的读取头开始往回（即向左）移动，在此过程中，M’根据第三步中获得的新的\Gamma^k改变含有#标记的k个字符，并且相应的移动#（往右往左或不动）

时间复杂度分析：k带图灵机每走一步，单带复杂度限制在O(t(n))时间里，所以总共O(t^2(n))

空间复杂度很明显

通用图灵机

通用图灵机是用来模拟一个具体的图灵机在某个输入w上的行为

通用图灵机的输入形式为w，其中为图灵机M的编码（也就是后面的gödelnummer）,w为一个输入词

然后通用图灵机U模拟图灵机M在输入为w时的行为

**注：**对于不正确的输入（例如输入不是以一个图灵机的编码开始的或者输入词中含有不属于M输入字母集合中的字母）则输出错误（Fehlermeldung）

哥德尔数编码(Gödelnummern)

我们称编码为图灵机M的Gödelnummer

Q=\{q_1,q_2,...,q_t\},t\ge 2,\quad q_1:起始状态，q_2:结束状态

\Gamma = \{0,1,B\}\quad X_1 = 0,X_2=1,X_3=B

\{L,R,N\} \quad D_1 = L, D_2 =N, D_3 = R

转移函数：\delta(q_i,X_j) = (q_k,X_l,D_m)编码为0^i10^j10^k10^l10^m

令第t个转移函数编码为code(t)

那么含有s个转移函数的图灵机的Gödelnummer为： = 111\ code(1)\ 11\ code(2)\ 11\ ...\ code(s)\ 111

如上开头结尾都是111，每一段转换函数编码之间用11隔开，转换函数内部用一个1隔开

通用图灵机的实现

使用三带图灵机来实现通用图灵机U:

通用图灵机U，输入w

1. 通用图灵机U的第一条带模拟图灵机M的带子
2. U的第二条带包含M的Gödelnummer
3. 在U的第三条带上存储M的当前状态

初始化：

1. U检查输入是否包含正确的Gödelnummer，如果不是：Fehlmeldung
2. U复制Gödelnummer到第二条带上并且将初始状态的编码写到第三条带上
3. U准备第一条带，带上只含有输入词w，读取头出于w的第一个字符上面

初始化的时间复杂度O(1)

模拟M单个步骤：

U根据第一条带上处在读取头上的字符和第三条带上当前的状态去第二条带上寻找相应的转移函数

然后根据转移函数所描述的：

U更新第一条带上读取头所在位置的字符；

移动第一条带上的读取头；

更改第三条带上所存储的M的当前状态

单个步骤的模拟时间复杂度：O(1)

**注：**那么U模拟M需要的时间是常数时间！ 因为U的输入是w，w在M上运行的步骤已经固定了，是个常数，然后每一步的时间复杂度也是常数，且初始化的复杂度同样是常数。

寄存器RAM

寄存器形式及命令：

命令的语法与语义

寄存器的运行方法

1. RAM的内存是不限制的，其由累加器c(0), 和寄存器c(1),c(2),c(3)…组成
2. 寄存器内的内容是自然数
3. 输入同样也是由自然数组成的，并且存储在最开始 的几个寄存器里
4. 所有其他的初始化为0
5. 当执行到命令END的时候，计算停止
6. 输出位于程序结束后的最开始的几个寄存器里

RAM的时间复杂度

统一时间消耗计量(Uniformes Kostenmaß)：RAM的每一步记为一个时间单位

对数时间消耗计量(Logarithmisches Kostenmaß)：RAM的每一步的时间消耗正比于所用到的寄存器里数字的二进制长度

TM模拟RAM

定理 ：对于每一个对数时间消耗限制在t（n）的RAM R存在一个多项式q和一个时间消耗限制在q(n+t(n))内的图灵机M，该图灵机M可以模拟R

证明 ：使用2带图灵机模拟RAM

整体结构

1. 在第一条带上模拟单个RAM指令，在第二条带上存储所有使用的寄存器里的内容
2. 假设RAM程序由p个程序行（也就是指令行）组成
3. 对于每一个程序行我们使用一个图灵子程序来模拟。令M_i表示第i行程序行的图灵子程序，1\le i \le p.
4. 另外我们令一个子程序M_0给图灵机进行初始化，并且令M_{p+1}准备计算结果的输出

RAM组态在TM上的存储

1. 因为RAM程序的长度是常数，所以指令计数器可以存在图灵机的状态里
2. 寄存器的内容以如下方式存储在图灵机的第二条带上
   

其中0，i_1,i_2,...,i_m表示使用到的寄存器的下标。

观察 ： 第二条带上的空间复杂度限制在O(n+t(n))内，因为RAM每生成出一个新的比特位至少需要一个时间单位

（因为t(n)是对数时间消耗计量，所以RAM给寄存器里的一个数加一个比特，需要>=1的时间单位，所以反过来在t(n)时间内RAM创造出的比特位小于等于t(n)，因此第二条带的空间消耗限制在O(n+t(n))）

一个特定的子程序M_b的模拟过程（1\le b \le p）

1. 将RAM第b个程序行所用到的寄存器里的内容复制到第一条带上（先寻找第二条带上对应的寄存器内容然后复制）
2. 对于这些寄存器内容运行必要的操作
3. 复制上面的操作结果到第二条带上对应的寄存器里
4. 更新程序计数器b

时间消耗分析

初始化需要的时间O(n)

所有的子程序的时间消耗都限制于当前第二条带上的长度的多项式时间内，因为第二条带的长度限制在O(n+t(n))，所以每一个子程序的时间消耗都限制在O(q(n+t(n)))内。

**注：**这里指子程序模拟每一个RAM指令都可以在多项式时间内完成（可根据上面子程序M_b的模拟过程得证）

因此所有的模拟时间消耗可在n+t(n)的多项式时间内完成

得证

单带图灵机模拟

根据之前单带多路径图灵机模拟多带图灵机可知，用单带图灵机模拟时间是多带时间的平方倍

那么由上面双带图灵机模拟RAM，用单带也同样模拟，n+t(n)的多项式时间的平方仍然是n+t(n)多项式时间，所以一样的

RAM模拟TM

定理 ：每一个t(n)时间限制的图灵机都可以通过一个RAM来模拟，其时间限制分别为

统一时间消耗计量(Uniformes Kostenmaß)：O(t(n)+n)

对数时间消耗计量(Logarithmisches Kostenmaß)：O((t(n)+n)\cdot log(t(n)+n))

证明

我们假设这是关于单边图灵机（就是图灵机读取头只能在起始点右边，这个其实是可以与双边图灵机互相转化的），其单元用0,1,2,3,4,…标记

在Q里的状态和图灵机带上的字母也被用数字下标一一标记，以使得其可以存入寄存器中

空字符的下标为0

对于只含有0,1和B的图灵机带，一般标记为B\rightarrow0,0\rightarrow1,1\rightarrow2

整体结构：

1. 第一个寄存器存储读取头位置的下标
2. 第二个寄存器存储当前状态
3. 寄存器1,2,3,4,5,6,7,…存储图灵机带上的内容0,1,2,3…
   

模拟过程

选择正确的图灵机转移函数：RAM使用2层的if-条件语句，第一层有|Q|个if条件语句，根据当前的状态选择进入第二层，第二层有|\Gamma|个if条件语句，根据当前读取头上的内容来选择下一步操作

1. 读取寄存器2里当前的状态，根据读取到的状态选择正确的条件语句，结束跳到第二层部分
2. 根据寄存器1里读取头的位置跳转读取对应位置的寄存器（也就是读取头对应的带上字母），之后根据字母选择正确的条件语句跳转执行转移函数右边的操作
3. 更新寄存器2里图灵机的状态
4. 更改寄存器1里读取头对应位置的寄存器里的内容
5. 更新寄存器1中读取头的位置
6. 跳转到第一步继续，知道读取到结束状态停止END

时间消耗：

对于统一时间消耗计量(Uniformes Kostenmaß)：

1. 初始化可以在时间O(n)里完成
2. 每一步图灵机的模拟都是固定的时间消耗，所以所有步骤需要O(t(n))
3. 综上模拟时间是O(n+t(n))

对于对数时间消耗计量(Logarithmisches Kostenmaß)：

需要考虑寄存器里数字的二进制长度，在寄存器里存储的数字分别代表状态，图灵机带上的字母和读取头的位置

1. 状态和带上的字母是固定的，因此有固定的编码长度
2. 读取头的位置，是被\mathbb{max}\{n,t(n)\}\le n+t(n)限制的（两种情况：1. 读取头在运行过程中超出了输入长度的范围；2. 没有超出该范围）那么相应的这个位置的编码长度就是O(log(t(n)+n))。
3. 因此对于单个图灵机步骤的模拟限制在O(log(t(n)+n))内
4. 综上整个模拟时间限制在O((n+t(n))\cdot log(t(n)+n))