多带图灵机

2020-07-28

字数统计: 3.3k字 | 阅读时长≈ 13分

多带图灵机是单带图灵机的推广，在计算能力上，多带和单带的计算能力在多项式时间内可以相互模拟。对于整数$k\geq 1$，一个$k$带图灵机是一个四元组$M=(K,\Sigma,\delta,s)$，其中$K,\Sigma,s$和通常的图灵机是没有区别的，转移函数$\delta$是一个从$K\times \Sigma^k$到 $(K\cup \{h,yes,no\})\times (\Sigma\times \{\rightarrow ,\leftarrow,-\})^k$ 的映射，$\delta$可以决定每条带上哪个字符被改写和每条带上的指针移动方向。对于 $(q,\sigma_1,\cdots,\sigma_k)$ ，有

$\delta(q,\sigma_1,\cdots,\sigma_k)=(p,\rho_1,D_1,\cdots,\rho_k,D_k)$

即若$M$在状态$q$，第$i$条带上指针指着字符$\sigma_i$，$i=1,\cdots,k$，则接下来进入状态$p$，在第$i$条带上将$\sigma_i$改写成$\rho_i$，然后指针沿着方向$D_i$移动一次，$i=1,\cdots,k$，另外这里每条带上仍然有带头$\rhd$，且带头不能被改写，指针不能移到带头左边。多带图灵机计算时，基本规则和单带图灵机相同，另外第一条带上含有输入$x$，输出可以在机器停机时从最后一条带上读取。

多带图灵机也有瞬时像的定义，$k$带图灵机的瞬时像是一个$2k+1$元组$(q,w_1,u_1,\cdots,w_k,u_k)$，其中$q$为当前状态，在第$i$条带上有字符串$w_i,u_i$，且指针指向$w_i$的最后一个字符。显然通常的图灵机就是$k=1$时的$k$带图灵机，一旦定义了$M(x)$，可以简单的将函数计算，语言的判定和接受的定义推广到多带图灵机，所以多带图灵机是定义图灵机计算时间和所用空间的基础。

利用2带图灵机判断回文

回文的定义非常简单，就是前后对应的字符串，比如101,010,00100等等，利用2带图灵机判断回文是非常简单的，首先机器先将输入复制到第二条带，接下来，令第一条带的指针指向输入的第一个符号，第二条带的指针指向输入的最后一个符号。然后，两指针以相对方向同时移动，检查所指的两个符号是否相同，若相同，则擦去第二条带上所复制的符号；若不相同，则进入状态no，并停机。

这个的判断过程非常简单，但支撑着这些判断过程的就是转移函数的设计，有了转移函数，图灵机才能一步步运行，此2带图灵机的转移函数设计如下

$(s,0,\cup)$	$(s,1,\cup)$	$(s,\rhd,\rhd)$	$(s,\cup,\cup)$	$(q,0,\cup)$	$(q,1,\cup)$
$(s,0,\rightarrow,0,\rightarrow)$	$(s,1,\rightarrow,1,\rightarrow)$	$(s,\rhd,\rightarrow,\rhd,\rightarrow)$	$(q,\cup,\leftarrow,\cup,\leftarrow)$	$(q,0,\leftarrow,\cup,-)$	$(q,1,\leftarrow,\cup,-)$

$(q,\rhd,\cup)$	$(p,0,0)$	$(p,1,1)$	$(p,0,1)$	$(p,1,0)$	$(p,\cup,\rhd)$
$(p,\rhd,\rightarrow,\cup,\leftarrow)$	$(p,0,\rightarrow,\cup,\leftarrow)$	$(p,1,\rightarrow,\cup,\leftarrow)$	$(no,0,-,1,-)$	$(no,1,-,0,-)$	$(yes,\cup,-,\rhd,\rightarrow)$

接着分析此图灵机完成判断需要的指针移动次数，首先需要复制操作，复制完之后第一条带上的指针还要移回起点，第一条带指针共移动了$2(n+1)$次，接着上下两条带的两指针相对方向同时移动，检查符号是否相同，并擦去复制品，需要$n+1$次，即用2带图灵机判定回文需要指针$O(n)$次移动。这与之间的单带图灵机比较，指数由2次将为1次。

单带图灵机可模拟多带图灵机

单带图灵机和多带图灵机的的计算能力在多项式时间内可以相互模拟，实际上就是下面的定理：

设$M$为指针移动次数$f(n)$内的$k$带图灵机，则可以构造一个指针移动次数$O(f(n)^2)$内的单带图灵机$M'$，使得对任意输入$x$，$M(x)=M'(x)$

这个的证明并不复杂，设$M=(K,\Sigma,\delta,s)$，是一个$k$带图灵机，证明的主要内容就是构造单带图灵机$M’=(K’,\Sigma’,\delta’,s)$使得$M’$可以模拟$M$，直观的方法就是$M$的各条带上的串在$M’$的带上连接起来，当然，串之间没有$\rhd$，以便指针可以前后移动，但这样存在一些问题，即如何区分$M$不同带上的串和如何记住$M$每个串上的指针位置。

为了解决合并时的问题，要引入新的字符 $\{\rhd',\lhd,\lhd'\}$ 表示一个串的开始和终点，另外令 $\underline{\Sigma}=\{\underline{\sigma}|\sigma\in \Sigma\}$ 表示指针所指字符串的集合，则令新的字母表 $\Sigma'=\Sigma\cup\underline{\Sigma}\cup\{\rhd',\lhd,\lhd'\}$ ，这里$\rhd’$表示一个串的开始，指针可以通过并到其左端，$\lhd$表示一个串的右端，指针可以通过，最终带上的字符串如下：

$\rhd\rhd'x\lhd(\rhd'\lhd) \cdots(\rhd'\lhd)\lhd$

其中$(\rhd’\lhd)$有$k-1$个，$\rhd$依旧是带头，最后的$\lhd$表示$M’$上串的结束，由此$M$的任意一个瞬时像 $(q,w_1,u_1,\cdots,w_k,u_k)$ 可以由$M’$的瞬时像如下表示：

$(q,\rhd',w_1'u_1\lhd\rhd'w_2'u_2\lhd\rhd'w_3'u_3\lhd\cdots \rhd'w_k'u_k\lhd\lhd)$

其中$w_i’$是$w_i$的最后一个字符加上下划线，其余不变，表示指针指在这个字符上，$i=1,\cdots,k$，需要注意的是，加上下划线之后就是新的字符了，即$\sigma$与$\underline{\sigma}$是不同的字符。

实际的模拟过程是利用转移函数的设计实现的，这里不给出具体的转移函数设计，仅给出模拟的思想，实际上转移函数也是依据基础的模拟思想设计的。

模拟开始，初始时$M’$的带上只有$\rhd x$
$M’$将输入右移一位，在其前面加上$\rhd’$，在输入后面写入$\lhd(\rhd’\lhd)^{k-1}\lhd$，这个过程并不复杂，只需要增加状态即可，至多$2k+2$个新状态(写入$\lhd(\rhd’\lhd)^{k-1}\lhd$至多需要$2k$个状态，再加上移位所需的两个状态，共$2k+2$个状态，有些状态实际上可以共用)
$M’$从左到右扫描串并返回，收集$M$中$K$个当前被指针所指的字符，然后增加若干个状态，记住这些符号，这些增加的状态对应着$M$的一个状态
根据第一次扫描的结果，$M’$已经清楚哪些字符要执行哪些操作，比如改写，删除等等，也就是在每个有下划线的字符处改写附近一个或两个字符(由$\sigma$变为$\underline{\sigma}$也是一种改写)，由此$M’$再次从左到右扫描串，完成改写。
若$M$的一条带上指针在串的右端，并要继续向右移动至空格$\cup$，则$M’$的带上，对应的部分串要先为新字符创造一个格子，比如$\cup$，过程也并不复杂，先用特殊符号$\lhd’$标记当前的$\lhd$(其实就是改写)，然后移动$M’$的指针到右端的$\lhd\lhd$，接着向右移动所有字符一个位置，当遇到$\lhd’$时，将其右移一个位置，并改写为$\lhd$，原位置写空格，接着停止字符串右移，空格增添完成
前5步模拟持续进行，直到$M$停止，此时$M’$擦掉$M$的串，仅保留下$M$的最后一条带上的串并输出

显然上面的过程可以完美模拟多带图灵机$M$，且有$M(x)=M’(x)$，接着分析$M’$模拟$M$所用的转移函数转移次数。关于输入$x$，由于$M$在$f(|x|)$步内停机，故$M$各带上串的长$\leq f(|x|)$。于是$M’$的串的总长$\leq k(f(|x|)+1)+2$，这个长度是包含$\rhd,\rhd’,\lhd,\lhd’$这些符号的。模拟$M$的一次移动要有至多两次来往扫描，则至多有$4k(f(|x|)+1)+8$步,在模拟$M$的每个串时，为了在某个位置添加一个$\cup$，需要将此位置后面的所有字符右移一格，这需要至多$3k(f(|x|)+1)+6$步，因为增添字符这个操作的复杂度是$O(3n)$，之前有讨论过。另外$M$的一步中，每条带都有可能加空格，则加空格这个操作$M’$至多需要$k(3k(f(|x|)+1)+6)$步，由于$M$在$f(|x|)$步内停机，则$M’$的模拟至多需要如下步数：

$(f(|x|)+1)(4k(f(|x|)+1)+8+k(3k(f(|x|)+1)+6))$

即$O(k^2f(|x|)^2)$，由于$k$为固定的，且与$x$无关，故为$O(f(|x|)^2)$，另外复杂度中关于带数$k$的依赖性可以通过不同的模拟避免，但$f$的次数不能改变。另外，作为一个计算模型，添加有限多条带不能增加其计算能力，对效率影响仅为多项式。

时间复杂度

首先多带图灵机是刻画图灵机计算时间的基础，要刻画图灵机运行的时间，这个时间最好可以反映问题任何实例的求解所需的时间，由此，实例的大小$n$可以用于实例计算所用时间的刻画，即为$n$的函数。这里的时间定义也很简单，它就是图灵机计算过程中转移函数的转移次数，如果对于输入$x$，$t$次转移后，图灵机停机，则称关于输入$x$，$M$需要时间$t$，显然$t$必为实例大小$n$的函数。设$f$为非负整数到非负整数的函数(后面讨论的所有$f$都是这种类型的函数)，称$M$在时间$f(n)$内计算，如果对于任意输入串$x$，$M$计算的时间$\leq f(|x|)$，也把$f(|x|)$叫做M的时间界。

有了时间的具体定义就可以定义复杂类，设 $L\subseteq(\Sigma \backslash\{\cup\})^{*}$ 在时间$f(n)$内被一个多带图灵机判定，则称$L\in TIME(f(n))$，这里$TIME(f(n))$是一个语言集合，其所含的每个语言可由一个多带图灵机在时间$f(n)$内判定，因此$TIME(f(n))$为一个复杂类。显然，当$f(n)< g(n)$时，有$TIME(f(n))\subseteq TIME(g(n))$。特别的，关于复杂类$TIME(f(n))$，有如下线性加速定理：

对于任意$\epsilon>0$，$TIME(f(n))=TIME(\epsilon f(n)+n+2)$

由此可见，对于任意多项式$f(n)\geq n$，若$f(n)$为线性，则$TIME(f(n))=TIME(n)$；若$f(n)$是非线性，则首项系数可以任意小而且时间界可以包含任意线性界，因此可以忽略低阶项，即若$f(n)=n^t+c_1n^{t-1}+\cdots +c_t$，则$TIME(f(n))=TIME(n^t)$，由此可以定义复杂类$P$为

$P=\underset{f}{\cup} TIME(f(n))=\underset{t \geq 0}{TIME\left(n^{t}\right)}$

这个$P$也是最中心的复杂类，即多项式时间内可以计算完成的问题。

空间复杂度

计算一个问题所用的空间大小，就是此问题的空间复杂度，也就是图灵机运行时所用到的格子的数量。为了规范的定义空间复杂度，规定多带图灵机的第一条带为只读带，也叫输入带，只是存储输入，最后一条带为只写带，也叫输出带，输出最后的结果，其余的带称为工作带，完成主要的计算过程，显然，这种规定并没有改变图灵机的计算能力。

由此，对于一个$k$带图灵机$M$和一个输入$x$，设 $H\in \{h,yes,no\}$ 为一个停机状态，若

$(s, \rhd, x, \rhd, \varepsilon, \cdots, \rhd, \varepsilon) \stackrel{M^t}{\longrightarrow}\left(H, w_{1}, u_{1}, \ldots, w_{k}, u_{k}\right)$

则关于输入$x$，$M$所要求的空间为 $\sum_{i=1}^{k}\left|w_{i} u_{i}\right|$ ，但是对于带有输入输出带的$M$，则其所要求的空间为 $\sum_{i=2}^{k-1}\left|w_{i} u_{i}\right|$ 。由此，若对于任意输入$x$，$M$所要求的空间至多为$f(|x|)$，则称图灵机$M$在空间界$f(n)$内运作。

称$L$属于空间复杂类$SPACE(f(n))$，若存在一个带有输入输出带的图灵机$M$在空间$f(n)$内判定$L$。特别的，关于复杂类$SPACE(f(n))$，有如下空间压缩定理：

对于任意$\epsilon>0$，有$SPACE(f(n))=SPACE(\epsilon f(n)+n+2)$

和时间复杂度的线性加速定理一样，可以简单推导得$SPACE(f(n))=SPACE(n^k)$，其中$f(n)$为$k$次多项式，由此可类似定义复杂类$PSPACE=\underset{k \geq 0}{\cup} SPACE(n^k)$。这个$PSPACE$也是非常重要的复杂类，即占用多项式的空间就可以完成计算的问题。

本文作者： sklois-gjx
本文链接： http://yoursite.com/2020/07/28/多带图灵机/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！