计算机数学基础第七章

1、2020/9/6,计算机科学的数学基础,1,第七章图灵机,2020/9/6,计算机科学的数学基础,2,图灵机的基本模型,图灵机的基本模型：,图灵机的一个动作是，根据带磁头所扫描的符号和有限控制器的状态，进行下列工作： (1) 改变状态 (2) 改写被扫描的带符号，并且 (3) 把它的磁头向左或向右移动一个单元。,2020/9/6,计算机科学的数学基础,3,图灵机的数学模型,一个图灵机M = (Q, , , , q0, B, F)，其中： Q是状态的有穷集； 是所允许的带符号的有穷集； B是中的一个符号，表示空白； 是输入符号集，即不包含B的的子集； 转换函数：Q QL, R ； q0是开始状态

2、， q0在Q中； FQ是终止状态集。,2020/9/6,计算机科学的数学基础,4,瞬时描述,用1q2表示图灵机M的一个瞬时描述。这里q Q，即M的当前状态；12 *，即带上直至最右的非空白符号的内容，1位于磁头左边，2位于磁头右边（注意空白符号B可以出现在12中）。 为了避免混淆假定Q和是不相交的。 最后，带磁头被认为正在扫描2的最左字符，或当2时，磁头正扫描空白符号。,2020/9/6,计算机科学的数学基础,5,瞬时描述TM动作的描述,设ID = X1Xi1qXiXn为一个瞬时描述。,若(q, Xi) = (p, Y, L)，i 1，则 IDM X1Xi2pXi1Y Xn = ID,若(q,

3、 Xi) = (p, Y, R)，i 1，则 IDM X1Xi1YpXi+1 Xn = ID,如果通过有穷多个动作（包括没有动作）从某个ID得到另一个ID，则它们有关系ID*MID。当不会产生混淆时，省去下标M。,2020/9/6,计算机科学的数学基础,6,图灵机所接受的语言,M所接受的语言，表示为L(M)，是*中的那些字的集合：M从初始状态q0开始阅读这个字，这个字使得M进入终止状态。形式上， L(M) = w | w*且pQ：q0w * 1p2。,注意此定义中并不要求M一定要阅读完输入符号串。这与FA和PDA接受语言的定义不同。,给定识别语言L的TM，不失一般性，假设每当输入被接受时，TM

4、停机，即TM无后续动作。但是对未被接受的字，TM可能会永远不停机。,2020/9/6,计算机科学的数学基础,7,可计算语言和函数,被图灵机所接受的语言称为递归可枚举集(r.e.s)。这种语言的字可以用一个图灵机枚举，因此称为“可枚举的”。 递归可枚举集合类的一个真子类，称为递归集合，是那些至少有一个对所有输入都停机的图灵机来接受的语言。 除作为语言接收器，TM可做从In到I的函数计算。若MTM，L(M)为q00i110i210in*0mp, pF，则M定义了 函数f：In I。,2020/9/6,计算机科学的数学基础,8,图灵机的构造技术,有限控制器的存储：用有限控制器来保存有限数量的信息。

5、为此，可把状态写成对偶，一个元素行使控制，而另一个元素存储符号。 必须强调，这样安置仅仅为了概念上的目的，并未对图灵机的定义作任何修改。,2020/9/6,计算机科学的数学基础,9,图灵机的构造技术,多道：对任何有穷的k，TM的带被分成k道。实际是把带符号看成k元组，一个分量对应一道。,一个三道图灵机：,多道并没有改变图灵机模型，因为它的带符号实际是一个k元组，把一个k元组看成一个完整的符号，就是一个单道的图灵机了。,2020/9/6,计算机科学的数学基础,10,图灵机的构造技术,查询符号：在带上引用一个保存一个空白或的额外道。当图灵机在其各次比较的一次比较中考察了下面的符号后，便出现。 移动

6、：用有限控制器存储可把非空白符号右移有穷多个单元的方法在其带上留空。 子程序：和程序一样，可以使用子程序来定义基本的处理。这时相当于一个图灵机调用另外一个图灵机。因此可以用若干个图灵机来构造一个新的图灵机。,2020/9/6,计算机科学的数学基础,11,图灵机的修改,双向无穷带 多带图灵机 不确定的图灵机 多维图灵机 多头图灵机 离线图灵机 所有这些图灵机的修改都等价于原型。,2020/9/6,计算机科学的数学基础,12,双向无穷带图灵机,双向无穷带TM是带的左右两端都是无穷的。 定理7.1：L被双向无穷带的TM所识别，当且仅当L被单向无穷带的TM所识别。 证明：用两道的单向无穷带就可以模拟双

7、向无穷带。,2020/9/6,计算机科学的数学基础,13,多带图灵机,一台多带图灵机，由有限控制加上k个带和k个带头组成，每条带的两个方向都是无穷的。 每个带头都是独立的。,2020/9/6,计算机科学的数学基础,14,多带图灵机,定理7.2：如果一个语言被一个多带图灵机所接受，它也被单带图灵机所接受。 证明：令L被具有k条带的图灵机M1所接受。能够构造一具有2k道（两道对应着M1的每一条带）的单带图灵机M2来模拟M1。,2020/9/6,计算机科学的数学基础,15,不确定的图灵机,不确定TM对给定状态和带符号有多个动作选择。 定理7.3：若L被不确定TM M1接受，则L被某个确定TM M2接

8、受。 证明：对确定状态和带符号， M1的动作选择可编号为1, , r，r 为最大选择个数，则任何长度n的动作选择序列对应一个n位r进制数。 M2用三带模拟M1。带1保存输入。带2系统产生r进制数。对带2上每个序列，M2复制输入到带3，在带3上按该序列模拟M1。显然L(M2) = L。,2020/9/6,计算机科学的数学基础,16,多维图灵机,多维图灵机的带由k维无穷单元组成，带头可沿k个轴中的一轴移动。 定理7.4：若L被二维图灵机M2所接受，则L被某个一维图灵机M1所接受。,BBBa1BBB BBa2a3a4a5B a6a7a8a9Ba10B Ba11a12a13Ba14a15 BBa16a

9、17BBB,2020/9/6,计算机科学的数学基础,17,多维图灵机的带由k维无穷单元组成，带头可沿k个轴中的一轴移动。 定理7.4：若L被二维图灵机M2所接受，则L被某个一维图灵机M1所接受。,*BBBa1BBB* BBa2a3a4a5B* a6a7a8a9Ba10B* Ba11a12a13a14a15* BBa16a17BBB*,2020/9/6,计算机科学的数学基础,18,多头图灵机,k头TM有固定数目k个带头，带头各自独立。 定理7.5：如果L被某个k头TM M1接受，则L也被某个单头TM M2所接受。 证明：这个证明类似于定理7.2对多带图灵机的证明。M2在它的带上有k+1道，最后一

10、道含有M1的带，并且对1 i k，第i道的带有一个标志来指示第i个带头的位置。,2020/9/6,计算机科学的数学基础,19,离线图灵机,一个离线TM是一个输入带是只读的多带TM 。通常输入端点标志括起来，左边是，而右边是。这种TM不允许输入带头移出和之间的区域。 显然这种离线TM只是多带图灵机的特殊情况，所以不会比已经考虑过的任何模型功能更强。 反过来，离线TM 也可用比M多一条带来模拟任何图灵机M。离线图灵机做的第一件是把它自已的输入抄在额外的带上，然后模拟M，好像这根额外的带就是M的输入的一样。,2020/9/6,计算机科学的数学基础,20,Church假设,“可计算函数”的直观概念等同

11、于部分递归函数类的假设被称为Church假设或Church-Turing命题。 只要 “可计算的”直观概念没有限制步数或存储量，那么部分递归函数就显然是可计算的。 不清楚的一点是部分递归函数类是否包括所有“可计算”函数。 许多其他形式化，如，算子、Post系统、等等，全都被证明了等价于部分递归函数。此外如RAM等抽象计算机模型也产生部分递归函数。,2020/9/6,计算机科学的数学基础,21,用图灵机模拟概率处理机,定理7.6：假设基本的RAM指令本身可被一图灵机模拟的话，图灵机就可以模拟RAM。 证明：用一个多带图灵机M 进行模拟。 一条带上存放RAM的已经给了值的那些字；一条带来存放每个算

12、术寄存器的内容；一条带来存放指令计数器，即存放下一条指令的字的号码；一条带作为存储地址寄存器，即存放一个存储字的号码。 这样M就可以模拟RAM的计算。,2020/9/6,计算机科学的数学基础,22,图灵机作为枚举器,除了把TM看作语言识别器和非负整数上的函数的计算机外，还可把TM看作生成装置。 M是具有一条输出带的TM，一个字一旦印在输出带上就永不改变，且字与字之间用#隔开。 定义G(M)，由M生成的语言，为所有这样的w的集合，每个w *且最终会被印刷在输出带上的两个#之间。 若M不永远运行下去的话，G(M)就是有穷的。 G(M)中的字是可以枚举的。,2020/9/6,计算机科学的数学基础,2

13、3,生成器刻划递归可枚举集,引理7.1：如果对某个图灵机M1，L是G(M1)，则L是一个递归可枚举集。 证明：构造比M1多一条带的图灵机M2，M2使用除它的输入带外的其他带来模拟M1。 每当M1在它的输出带上印刷#时，M2便把它的输入与刚生成的字相比较。如果它们相同，M2便接受，否则M2继续模拟M1。 显然M2接受输入X当且仅当X在G(M1)中。于是L(M2) = G(M1)。,2020/9/6,计算机科学的数学基础,24,递归可枚举集可以枚举,定理7.7：一个语言是递归可枚举的，当且仅当它是某个图灵机M2的G(M2)。 证明：图灵机M2先逐个生成上的字，然后依次对它们模拟M1，若M1接受，则

14、印刷该字。,不过，这样做是有点问题的。因为如果有某个字不被M1接受，M1可能会永不停机，这样后面的字就没有机会被检测了，也就不会被生成了。,2020/9/6,计算机科学的数学基础,25,递归可枚举集可以枚举,定理7.7：一个语言是递归可枚举的，当且仅当它是某个图灵机M2的G(M2)。 证明：图灵机M2先逐个生成上的字，然后依次对它们模拟M1，若M1接受，则印刷该字。,因此要采用所谓三角形的方法来对上的字进行检测。,2020/9/6,计算机科学的数学基础,26,递归可枚举集可以枚举,定理7.7：一个语言是递归可枚举的，当且仅当它是某个图灵机M2的G(M2)。 证明：图灵机M2先逐个生成上的字，然

15、后依次对它们模拟M1，若M1接受，则印刷该字。,M2模拟对偶产生器。当(i, j)被产生时，M2按规范顺序产生第i个字wi且模拟M1对wi的j步动作。若M1在第j步接受，则M2生成wi。显然G(M2) = L。,推论：若L是递归可枚举集，则有一个L的生成器，使得L中的每个字正好被枚举一次。,2020/9/6,计算机科学的数学基础,27,用生成器描述递归集,引理7.2：如果L是递归的，则有一个L的生成器，它按规范顺序印刷L中的字，并且不印刷任何其他的字。 定理7.8：L是递归的，当且仅当L按规范顺序被生成。,2020/9/6,计算机科学的数学基础,28,等价于基本模型的受限图灵机,多栈机器：一个

16、确定的两栈机器是具有一条只读输入带和两条存储带的确定图灵机。带头按栈控制的方式访问这两条存储带。 多计数器机器：是存储带是单向无穷的并且带字母表仅二个符号，z和B，的离线图灵机。,两计数器机器,2020/9/6,计算机科学的数学基础,29,四计数器机器等价于TM,引理7.4：四计数器机器能够模拟任意的图灵机。 证明：两条计数器带能够模拟一个栈。 每个栈符号对应一个一位k进制数。设栈含有m1个非空白的栈符号，则能够用唯一k进制的“计数” j = im+kim-1+k2im-2+km-1i1来表示栈zi1zi2zim。 注意，并不是每个整数都表示一个栈，那些k进制表示含有数字0的整数就不表示一个栈

17、。,2020/9/6,计算机科学的数学基础,30,四计数器机器等价于TM,引理7.4：四计数器机器能够模拟任意的图灵机。 证明：两条计数器带能够模拟一个栈。 每个栈对应一个k进制数。 j = im+kim-1+k2im-2+km-1i1。,假设符号zr被压入栈zi1zi2zim的栈顶，则相当于计算kj + ir，这里j是原栈所对应的整数。 反之，如果弹出栈顶符号zim，j必须由j/k，j/k的整数部分来代替，即整除运算。 所以两条计数器带能够模拟一个栈。,2020/9/6,计算机科学的数学基础,31,两计数器机器等价于TM,定理7.9：两计数器机器能够模拟任意TM。 证明：可用两计数器机器模拟

18、四计数器机器。,首先，四个计数器的计数i, j, k和l可以唯一地表示为一个计数n，并且且i, j, k和l也可以唯一地从计数n获得。,怎么做？,算术基本定理,2020/9/6,计算机科学的数学基础,32,两计数器机器等价于TM,定理7.9：两计数器机器能够模拟任意TM。 证明：可用两计数器机器模拟四计数器机器。,设四个计数器分别为i，j，k和l。令n=2i3j5k7l，则计数n便唯一地表示了i，j，k和l。,现在只要证明能分别对i，j，k和l进行运算就可以实现对这四个计数器的模拟。为此只需要能够实现分别对i，j，k和l进行加一和减一的运算就行了。,2020/9/6,计算机科学的数学基础,33,两计数器机器等价于TM,定理7.9：两计数器机器能够模拟任意TM。 证明：可用两计数器机器模拟四计数器机器。,设四个计数器分别为i，j，k和l。令n=2i3j5k7l，则计数n便唯一地表示了i，j，k和l。,为了实现i/j/k/l加一，分别用2/3/