[音乐] Hi，欢迎回来。 接下来呢我们来介绍图灵机。 在我们前面介绍过有限状态机之后呢我们再来看看一种 新的能力更为强大的机器，它叫图灵机。 它是由计算机科学家这个图灵所发明的一个理想当中的一种机器。 我们先来看看图灵机的基本结构。 那么它的结构呢跟有限状态机也是类似的，也有纸带，也有一个机构，然后呢 这个结构呢它有内部也有状态。 那么它们不同之处在哪儿呢？首先第一呢， 这个图灵机上的这个纸带，它可以既是做输入，又是做输出，而且呢也做中间的这个的存储。 所以呢它是一个无限长的一个纸带，也就是说它的 存储的容量并没有什么限制，而且呢分格子。 然后每一个格子呢可以容纳一个字符，那么这也是形式语言当中字符集当中的单个字符。 然后另外呢它有一个读写头，它这个读写头或者说读写机构呢 的特征呢，它可以在一个纸带上进行移动。 而我们说这个有限状态机它的这个机器的这个模型是说 这个纸带呢进了机器以后只能够单向地进去， 进去以后就不能往回退，而它的这个读写头呢 有限状态机的这个读写头它是固定的，而图灵机的读写头可以在纸带上移动。 那么它这个移动呢可以双向移动， 那么移动的距离、 移动的范围都没有限制。 而且呢这个读写头，既然是读写嘛，它可以读出当前格子的字符。 然后用于判别说下一步要做什么。 然后呢它也可以重写 格子上的内容，比如说它可以把这个字符抹掉，用另外一个字符去覆盖它。 或者在一个空白的这个格子上写上一个字符。 然后呢同时呢它可以改变自己的内部的状态，所以它可以做三件事情。 首先呢它第一个呢有内部的自己的状态。 第二呢它可以移动。 第三呢，它可以改写。 那么除了这个除了这个纸带读写头之外， 那么还有一些这个规则来驱动这个读写头去做一些工作。 那么这呢就是一系列关于读写头动作的这个规则。 那么我们把这些规则呢，一组的这种规则也称之为 这个图灵机的程序，就是把这个图灵机本身称作一个程序。 也可以呢，类似于像有限状态机那样的叫法，叫做 状态转移函数，它可以从一个状态转移到另一个状态，只不过说它这个状态转移了以后， 或者说转移的过程当中它同时会完成 读写头可以做的几件事情，一个是呢可以移动，一个是呢可以重写。 所以呢我们说整个的图灵机就像下面这个图所示的这样。 它一头呢是有限的，另外一头呢是无限的，然后每个呢都会有一个格子， 然后每个格子当中可以写字符，然后有一个读写头可以沿着这个格子左右地移动， 进行左右移动，这就是图灵机的这个基本的结构。 那么图灵机它作为一个计算，它是怎么来实现的呢？首先， 这个纸带上的内容，包括这个特殊字符就有一个空白， 空白是什么都没有，那比较特殊，这个呢作为计算前的输入和计算以后的输出， 也就是说在计算发生之前，这个纸带上的内容就是输入的布局， 那么在计算完成之后，比如说停机了，当然我们后边还会说到它未必会 停机，只要计算完成，那么这个时候纸带上所剩下的一切就是它的计算的输出。 那么计算呢是从这个读写头的初始状态，它也有一个初始状态，s0开始， 它的初始位置，那么读写头放在哪个位置，这也很重要。 以及这个输入的纸带的格局开始来进行 计算，然后按照呢图灵机所包含的这些规则进行读写头的移动 至纸带字符的修改，然后直到最后能够进入这个停机状态。 我们说为这个图灵机呢，在它的状态 集当中设定了三种特殊的状态，一个是SH，就是停机状态， SY停机并接受，SN停机并拒绝，这三种状态，这三个状态呢就属于停机状态。 那么停机状态，到了停机状态之后，这个 再也不会有这个规则来 命令这个读写头做进一步的动作，那么它就停止下来了。 那么在停机状态，这三个状态的时候，那么纸带上什么内容 那么它就是这个图灵机的输出，这个它的输出。 那么这里当中呢最重要的就是计算规则。 那么计算规则呢我们当然也可以把它当做这个状态转移函数来进行看待。 那么对于这个图灵机的计算规则，或者说图灵机的状态 转移函数，那么它是一个Q叉上 这个δ，那么Q呢就是状态集，δ呢是字符集。 然后呢映射到这个状态，然后字符，然后呢还有 动作L,R,N这样的一个状态转移函数。 所以呢它每一个五元组就是一条规则， 比如说一个五元组si,ak al,sj,然后有个d，这五个。 那么其中呢这个si和sj，它就属于这个内部状态。 然后ak,al它是一个纸带上的字符， 那么然后d呢是L,R,N组成的这个动作的这么一个集合。 那么L呢就是把这个读写头往左移，然后R呢往右移，N呢就是不动，读写头不动。 所以呢我们就是说这样的一个五元组就表示说如果读写头当前的状态是 si的话，那么读到当前的格子的字符是ak的话， 那么它会做下面三件事情。 第一呢，把这个格子的内容改成al， 然后第二呢改变状态，改变成，状态改变成 sj，然后呢再进行这个d所指定的动作。 那么d呢指定的动作呢就是左移、 右移或者不动。 这就是一条，其中一条规则所实现的内容。 当然这个图灵机呢 它包含了若干条这样的规则，它形成了规则的集，所以呢它这也算是一个状态转移函数了。 那么但是呢它对这个计算规则有一些限制。 首先呢规则的数量是有限的， 它不能是无穷多个，无穷多条规则， 其次呢它要保证这个动作的这个确定性。 也就是说任意两条规则，它前两项不能相同。 这个前两项实际上是代表的是现状，读写头处于什么状态的时候，它读到了一个什么字符。 那么后面三项呢就是它所采取的动作。 如果说前两项相同，而后三项有一项，任意有一项不同的话，那么它就整个的这个图灵机 这个动作它就不确定了。 你说让机器到底是干这件事情还是干那件事情， 它就不确定。 然后最后呢确认这个有三个状态 是停机状态，所以呢不会有任何一个规则，它的第一项是SH，SY或者SN 这三个。 也就是说只要处于这三个状态之一，那么就 一定是一个停机状态，就不会再有规则引导读写头再做进一步的动作了。 那么对于这个图灵机和形式语言之间的对应来说，它们是一个什么样的关系呢？ 也就是说当我从，从这个字符集A*当中，它的一个子集W， 那么这个呢是一个形式语言。 那么我们把这个W 当中任意的字符串w作为这个图灵机的输入， 如果任何的这个w都作为输入， 这个图灵机M呢都会停止在接受状态SY的话， 然后呢同时，把这个A-W，就是W的这个补语言 补语言里头的每一个字符串放在 图灵机当中，它作为输入放在图灵机里，它都会停在拒绝状态。 然后还有同时，还有一个最关键的一个内容。 就是或者用户停机，因为这个图灵机的运行它 它要穷穷尽它的这个运行的这个结果， 一个呢是停机，另外呢还有可能不停机，所以 所以我们把这个不停机呢归纳到这个补语言里头的这个状态里去。 所以呢如果说补语言当中的所有的字符串，这个图灵机呢都会停在拒绝状态，或者永远不停- 机的话， 那么我们就称这个图灵机M 它识别或者说接受这个语言W。 那么这个呢就是形式语言和图灵机之间的一个关系。 那么一个形式语言L，它能够被这个 图灵机M识别，当且仅当这个L呢在 乔姆斯基的这个形式语言分类体系当中 是一个0型的形式语言的时候，那么它就被图灵机所识别。
