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，
Ge Li 李戈, Ph.D.Associate Professor
