您的位置: 首页  >  文章  >  计算性和复杂度理论1

计算性和复杂度理论1

分类: 文章 • 2025-07-07 19:17:10

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

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

预备知识

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

O ( g ( n ) ) = { f ( n )   ∣   ∃ c > 0 , ∃ n 0 , ∀ n ≥ n 0 : 0 ≤ f ( n ) ≤ c ⋅ g ( n ) } 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)\} O(g(n))={f(n) ∣ ∃c>0,∃n0​,∀n≥n0​:0≤f(n)≤c⋅g(n)}

Ω ( g ( n ) ) = { f ( n )   ∣   ∃ c > 0 , ∃ n 0 , ∀ n ≥ n 0 : 0 ≤ c ⋅ g ( n ) ≤ f ( 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)\} Ω(g(n))={f(n) ∣ ∃c>0,∃n0​,∀n≥n0​:0≤c⋅g(n)≤f(n)}

Θ ( g ( n ) ) = { f ( n )   ∣   ∃ c 1 , c 2 > 0 , ∃ n 0 , ∀ n ≥ n 0 : 0 ≤ c 1 ⋅ g ( n ) ≤ f ( n ) ≤ c 2 ⋅ g ( 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) \} Θ(g(n))={f(n) ∣ ∃c1​,c2​>0,∃n0​,∀n≥n0​:0≤c1​⋅g(n)≤f(n)≤c2​⋅g(n)}

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

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

f ∈ O ( g ) ⇔ 0 ≤ lim sup ⁡ x → ∞ ∣ f ( x ) g ( x ) ∣ < ∞ f\in O(g) \Leftrightarrow 0 \le \limsup_{x\rightarrow \infty} | \frac{f(x)}{g(x)} | < \infty f∈O(g)⇔0≤x→∞limsup​∣g(x)f(x)​∣<∞

f ∈ Ω ( g ) ⇔ 0 < lim inf ⁡ x → ∞ ∣ f ( x ) g ( x ) ∣ ≤ ∞ f\in \Omega(g) \Leftrightarrow 0 < \liminf_{x\rightarrow \infty} | \frac{f(x)}{g(x)} | \le \infty f∈Ω(g)⇔0<x→∞liminf​∣g(x)f(x)​∣≤∞

f ∈ Θ ( g ) ⇔ 0 < lim inf ⁡ x → ∞ ∣ f ( x ) g ( x ) ∣ ≤ lim sup ⁡ x → ∞ ∣ f ( x ) g ( x ) ∣ < ∞ 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 f∈Θ(g)⇔0<x→∞liminf​∣g(x)f(x)​∣≤x→∞limsup​∣g(x)f(x)​∣<∞

图灵机

图灵机组成

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

（ Q , Σ , Γ , B , q 0 , q ˉ , δ ） （Q,\Sigma,\Gamma,B,q_0,\bar q,\delta） （Q,Σ,Γ,B,q0​,qˉ​,δ）

Q Q Q：有限的状态集合

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

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

B ∈ Γ ∖ Σ B\in \Gamma \setminus \Sigma B∈Γ∖Σ：表示为空的符号

q 0 ∈ Q q_0 \in Q q0​∈Q： 起始状态

q ˉ ∈ Q \bar q \in Q qˉ​∈Q：终止状态

δ : ( Q ∖ q ˉ ) × Γ → Q × Γ × { R , L , N } \delta : (Q\setminus {\bar q})\times \Gamma \rightarrow Q \times \Gamma \times\{R,L,N\} δ:(Q∖qˉ​)×Γ→Q×Γ×{R,L,N}：状态转移方程

图灵机的运行机制

计算性和复杂度理论1

停止：

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

特别的：

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

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

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

图灵可计算性

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

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

组态konfiguration

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

α q β ⊢ α ′ q ′ β ′ \alpha q \beta \vdash \alpha' q'\beta' αqβ⊢α′q′β′

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

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

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

计算性和复杂度理论1

Γ n e u : = Γ ∪ Γ k \Gamma_{neu} := \Gamma \cup\Gamma^k Γneu​:=Γ∪Γk

多带图灵机

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

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

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

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

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

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

计算性和复杂度理论1

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

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

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

空间复杂度很明显

通用图灵机

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

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

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

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

哥德尔数编码(Gödelnummern)

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

Q = { q 1 , q 2 , . . . , q t } , t ≥ 2 , q 1 : 起 始 状 态 ， q 2 : 结 束 状 态 Q=\{q_1,q_2,...,q_t\},t\ge 2,\quad q_1:起始状态，q_2:结束状态 Q={q1​,q2​,...,qt​},t≥2,q1​:起始状态，q2​:结束状态

Γ = { 0 , 1 , B } X 1 = 0 , X 2 = 1 , X 3 = B \Gamma = \{0,1,B\}\quad X_1 = 0,X_2=1,X_3=B Γ={0,1,B}X1​=0,X2​=1,X3​=B

{ L , R , N } D 1 = L , D 2 = N , D 3 = R \{L,R,N\} \quad D_1 = L, D_2 =N, D_3 = R {L,R,N}D1​=L,D2​=N,D3​=R

转移函数： δ ( q i , X j ) = ( q k , X l , D m ) \delta(q_i,X_j) = (q_k,X_l,D_m) δ(qi​,Xj​)=(qk​,Xl​,Dm​)编码为 0 i 1 0 j 1 0 k 1 0 l 1 0 m 0^i10^j10^k10^l10^m 0i10j10k10l10m

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

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

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

通用图灵机的实现

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

通用图灵机U，输入 < M > w <M>w <M>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 w，读取头出于 w w w的第一个字符上面

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

计算性和复杂度理论1

模拟M单个步骤：

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

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

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

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

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

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

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

寄存器RAM

寄存器形式及命令：

计算性和复杂度理论1

命令的语法与语义

计算性和复杂度理论1
计算性和复杂度理论1

寄存器的运行方法

  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 M_i Mi​表示第i行程序行的图灵子程序， 1 ≤ i ≤ p 1\le i \le p 1≤i≤p.
  4. 另外我们令一个子程序 M 0 M_0 M0​给图灵机进行初始化，并且令 M p + 1 M_{p+1} Mp+1​准备计算结果的输出

RAM组态在TM上的存储

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

计算性和复杂度理论1

其中 0 ， i 1 , i 2 , . . . , i m 0，i_1,i_2,...,i_m 0，i1​,i2​,...,im​表示使用到的寄存器的下标。

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

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

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

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

时间消耗分析

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

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

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

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

  4. 得证

单带图灵机模拟

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

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

RAM模拟TM

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

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

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

证明

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

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

空字符的下标为0

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

整体结构：

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

计算性和复杂度理论1

模拟过程

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

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

时间消耗：

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

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

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

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

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

相关推荐