OK，那么下面我用一个例子来看一下图灵机的工作原理。
首先大家看到的这个抽象的图呢，就是一个抽象版的图灵机了。
这个呢，就是那个存储带。这个呢，就是那个控制器。
控制器呢有一个读写头，它有一个当前状态。并且呢，可以输入一些程序。
这是那个图灵机，这是一个空白的图灵机。
那图灵机在工作之前呢，首先要进行准备，完成一系列的初始化。 第一个初始化呢，像刚才我们讲过的，
首先要在存储带上放入一些表示符号，比方说我们在这个存储带上放入这样一些符号。
我们只放1，其他的呢保持空白，也就是说，
在这个存储带上，所有出现的符号只有两种，要么是1，要么是b，b表示空白。
第二个呢，要设好这个控制器当前的状态。
当前的状态，那么我们假设呢，当前的状态是q1，而且呢，我们假设在这个图灵机里头，
控制器值处于3种状态之一，q1，q2，q3。只处于这三种状态之一。
第三个，要放好读写头，放好位置，比方说我们把它放在这个位置。
对准这个相应的存储空格。第四个呢要准备好相应的工作程序。
比方说我们在这个图灵机里头要放入相应的工作程序。
那么大家看到的这个程序呢，是由一些字符来构成的。
实际上呢，它是六条程序语句，因为每一行表示一条程序语句。 一条相应的程序语句。
那这六条程序语句的格式是一致的。所以说呢，我们拿出其中的一条来做一个讲解。
任何一条程序语句呢，都包含5个符号。1，2，3，4，5。
这五个符号呢，分别表示不同的含义。 那么前两个符号，表示条件。 后三个符号
表示动作。
那这个程序语句的含义就是，当满足这个条件的时候，我要执行这个动作。那具体来说呢，
比方说这个符号q1，表示当前机器的状态。
也就是说，如果当前机器状态时q1，
并且，当前读到的符号是1，这个1表示的含义是当前读到的符号。
那么，这个条件就满足了。就要执行后面的这个动作，什么动作呢？
第一个，这个1表示当前应该写入的符号。
当前在图灵机所位于的这个存储格上应该写入的符号。
第二个R，表示图灵机要向右移动一步。
也就是说，在写完这个动作以后，
在写完这个1以后，它要往右移动一步。
那么第三个呢，q1表示机器应该转入的一个状态。
OK，准备工作完毕以后呢，图灵机就开始运转了。
那么根据我们刚才讲过的，图灵机怎么运转呢？首先，
读写头读出存储带上当前方格中的字母或者数字。 当前方格是这个方格，把这个字母读出来。
根据当前自身的状态，和所读到的字符，那么找到相应的程序语句。
根据自身的状态，以及所读到的字符，根据这两个信息，
我们要到程序集合里头去找相应的程序语句。
因为当前状态是q1，所以说我们只能，
这是表示当前状态，只能找到，哦，在这两条程序语句里头。 寻找其中的一条。
那么因为读到的字符是1，所以，我们再来看，读到的字符是1，那只有第一条语句是符合的。
所以接下来我们要按照第一条语句提供的信息来进行执行。
执行三个动作。哪三个动作呢？第一个，
这个1，刚才我们解释过，表示要在这个方格里面，
再写入1，当前方格里头再写入1。
写入一个1，这个R呢，表示写完1之后，读写头要向右移动一格。
这个q1呢，表示在做完这两个动作之后， 这个控制器的当前状态，
控制器的当前状态，要从q1变成这个状态，也是q1，那也就是保持不变。
那，在经历， 按照第一条语句运行完以后，当前的状态应该是这样一个状态，我们来看一下。
控制器向右移动了一格，
当前的状态仍然是q1，刚才呢写入了一个1，1也保持不变。
那么，根据现在的，根据现在的状态呢，当前状态q1，读到的是一个1，
那再继续匹配，再来选语句。
选到的是什么？当前状态q1，读到的是一个1，又匹配第一条语句。 又执行这条语句。
所以呢，再次在这儿写入一个1，根据这个，要右移一格，
根据这个，它要保持不变。于是这个执行完之后呢，状态应该是这个样子。
当前状态q1， 又读到一个1，那么又匹配这条语句，
依然按它执行，保持不变，写入1，右移，保持不变。写入1，右移，保持不变。执行完之后是这样子。
那么当前状态q1，又读到一个1，还是匹配原来这条语句，
于是继续写入1，右移。然后状态保持不变。
写入1，右移，状态保持不变。变成这样子。当前状态q1，读到的是一个空白，
匹配语句，当前状态q1，匹配这两条，读到是一个空白，只能匹配这条，于是这条语句被选中。
那接下来它要做什么呢？要在当前的这个位置写入一个1，
并且读写头的状态往右移动一格。并且呢，当前的状态要由q1变成q2。
这是要做的动作，那么执行完这个动作之后，结果就应该是这样子。
写入了一个1，往右移动了一格，状态变成了q2。
那么现在呢，当前状态q2，读到的是一个1，我们再来找相应的语句。
当前状态q2，写入的是一个1。哦，只有这句语句符合。
那我们接下来要做什么呢？当前写入一个1，
然后右移，然后当前状态保持不变。
保持q2不变，写入1，右移，状态保持不变。
执行完是这样的，当前状态q2读到的又是一个1，又是这条语句被符合。
那么写入一个1，右移，状态保持不变。 又得到这样，q2又读到一个1，继续匹配这条语句。
写入一个1，右移，状态保持不变。
OK，执行完是这样子。那么当前状态q2，读到的是一个空白，
那么我们根据这两个信息得到出来的匹配，
那么q2，读到的是一个空白，这条语句被匹配到，它要做什么呢？
当前写入一个空白，并且左移一下，
并且，状态由q2变成q3。
这是它要做的动作，那么这条语句执行完之后， 图灵机的状态变成这样子。
当前状态q3，读到的又是一个1，我们根据这两条来匹配。
那么q3，读到的又是一个1，匹配好这一条，
那现在图灵机要做什么呢？要在当前写入一个空白。
在这儿写入一个空白。并且呢，H，H表示 不动，读写头的位置不动，
然后状态呢，从q3变成q3，也是q3保持不变，执行完之后， 状态变成这样子，就是说不要动。然后当前状态q3，
读到的是一个空白，那我们再来匹配语句。哦，这条语句被匹配到
也就是说，如果当前状态是q3，并且读到了空白，那我做什么呢？
在当前的这个状况，写入一个空白， 并且位置不变，状态也不变。
读到一个空白，我就写入一个空白，并且位置不变，状态不变。
那执行完这条语句之后，仍然保持现有的这个状况。
仍然是这样一个状况。
在这个状况下，又是q3，又是读到一个空白，OK，一直就会执行这条语句。
于是，这个状态进入停机的状态。
我们这个时候我们可以说，图灵机成功的停机了。
成功的停机了。那么回顾一下刚才我们所举的这个例子。
看看它做了什么样的一件事情呢，这个图灵机？ 当然，有很多种的解释，在这儿呢，那我给出来一个解释。
还记得吗？我们刚刚开始的时候，在这儿输入了四个1，
在这儿输入了三个1， 1，2，3，4。1，2，3。我能不能这样解释，
在一开始的时候，这4个1呢，表示数字4，后面的三个1呢表示数字3，
这是最开始的状态。那整个图灵机执行完以后呢？
这些1都被连起来了，那我可不可以解释成，这是一个数字7。
所以说呢，刚才的图灵机做了这么一个加法。4+3=7。
有的同学说，哎呀这个太简单了吧！这么复杂，
这么费劲，结果就算了这么简单的一个数字。
那我想说，虽然这个数字是简单的，但是这台图灵机可以算所有的加法。
这就是图灵机的作用。那么还是很强大的。
那么一个图灵机成功停机，到底意味着什么呢？停机表示计算完毕。
也表示着当前存留在这个存储带上的值，就是一个计算结果。
所以我们可以说，
停机就意味着计算得出计算结果了。
图灵机是用来干嘛的？我们讲过，图灵机是用来判定一个问题到底可不可解的。
那么当你面临一个问题，比方说有一个输入A，问能不能算出B啊？
图灵机可以帮你做一个判定。 那么如果你能找到这样的一台图灵机，那就意味着这个问题可解。
如果找不到，那这个问题就不可解。
判定这个问题是否可解的 这件事情，就等同于，去寻找一台图灵机。
如果你能证明，存在这样一台图灵机，那么它就能解。
如果找不到这样一台图灵机，这个问题就不可解。 OK，这作为一个小插曲，介绍一下图灵机的作用。
那图灵机这样一个东西为什么能够受到如此的重视呢？
其实，探讨可计算性的这个模型有很多个，那么为什么唯独图灵机受到这样的重视呢？
因为图灵机有三大特性。第一个，简单。
这样的一台机器，几乎任何一个人，花一些功夫，都能搞的懂。
第二个，功能强大。它非常非常的强大，可以完成各种各样的运算。
第三个，它是看得见、摸得着，可以实现的。
有些同学说，有些东西恐怕不好实现，什么纸带啊，什么之类的。
这些就看你怎么去做了。比方说有这样一个网站，
这个网站叫做aturingmachine.com。 你可以到这个网站上去看一下。
它呢提供了一个图灵机的一个实现，长成这样子。
并且呢这个网站上有一段视频，这段视频专门来介绍，这个图灵机到底是怎么来运转的。
所以说，这个模型真的是可实现。这是图灵机
之所以这么受到重视的一个很重要的原因。
那么图灵机在理论上有什么意义呢？
当然，第一个意义是，当提出图灵机的时候，
所要解决的那个问题，就是可计算性的判定的问题。 除了这个之外，它还有很重要的意义。
首先，它给出了一个可以实现的 通用计算的一个模型。
这就意味着，按照这个模型，我们有可能，
制造出一台能够进行通用计算的机器。
第二点，它引入了通过”读写符号“ 和”状态改变“来进行运算的这种思想。
第三个，实现了基于简单字母表完成复杂运算的能力。
它直接给你展现出来了，你看基于一个简单的字母表，就像我们刚才，
只用1和空白，我们就实现了加法运算。
第四个，引入了存储区、程序以及控制器等等概念的原型。OK，关于图灵机的东西，我们就先介绍到这里。
那么在接下来的这个章节里面呢，我们将解释一个问题。
计算机为什么能够完成计算？
什么意思呢？ 就是说，我们所用的计算机，是由一些线路，一些电器来构成的。
这样一个电器，它为什么就能算数呢？
我想通过一个讲解，来给大家解释一下这个问题。OK。
Ge Li 李戈, Ph.D.Associate Professor
