电子发烧友App
如何理解图灵机？
1、小虫的比喻
我们不妨考虑这样一个问题。假设一个小虫在地上爬，那么我们应该怎样从小虫信息处理的角度来建立它的模型？
首先，我们需要对小虫所在的环境进行建模。我们不妨就假设小虫所处的世界是一个无限长的纸带，这个纸带上被分成了若干小的方格，而每个方格都仅仅只有黑和白两种颜色。很显然，这个小虫要有眼睛或者鼻子或者耳朵等等感觉器官来获得世界的信息，我们不妨把模型简化，假设它仅仅具有一个感觉器官：眼睛，而且它的视力短得可怜，也就是说它仅仅能够感受到它所处的方格的颜色。因而这个方格所在的位置的黑色或者白色的信息就是小虫的输入信息。
另外，我们当然还需要为小虫建立输出装置，也就是说它能够动起来。我们仍然考虑最简单的情况：小虫的输出动作就是往纸带上前爬一个方格或者后退一个方格。
仅仅有了输入装置以及输出装置，小虫还不能动起来，原因很简单，它并不知道该怎样在各种情况下选择它的输出动作。于是我们就需要给它指定行动的规则，这就是程序！假设我们记小虫的输入信息集合为I={黑色，白色}，它的输出可能行动的集合就是：O={前移，后移}，那么程序就是要告诉它在给定了输入比如黑***况下，它应该选择什么输出。因而，一个程序就是一个从I 集合到O 集合的映射。我们也可以用列表的方式来表示程序，比如： 程序1：
输入输出
黑色前移
白色后移
这个程序非常简单，它告诉小虫当读到一个黑色方格的时候就往前走一个方格，当读到一个白色方格的时候就后退一个格。
我们不妨假设，小虫所处的世界的一个片断是：黑黑黑白白黑白……，小虫从左端开始。 那么小虫读到这个片断会怎样行动呢？它先读到黑色，然后根据程序前移一个方格，于是就会得到另外一个黑色信息，这个时候它会根据程序再次前移一个方格，仍然是黑色，再前移，这个时候就读到白色方格了，根据程序它应该后退一个格，这个时候输入就是黑色了，前移，白色，后移……，可以预见小虫会无限的循环下去。
然而，现实世界中的小虫肯定不会这样傻的在那里无限循环下去。我们还需要改进这个最简
单的模型。首先，我们知道小虫除了可以机械地在世界上移动以外，还会对世界本身造 ……
开始
成影响，因而改变这个世界。比如虫子看到旁边有食物，它就会把那个东西吃掉了。在我们这个模型中，也就相当于我们必须假设小虫可以改写纸带上的信息。因而，小虫可能的输出动作集合就变成了：O={前移，后移，涂黑，涂白}。这个时候，我们可以把程序1改为比如： 程序2：
输入输出
黑前移
白涂黑
纸带是黑黑白白黑……，小虫会怎样行动呢？下面的图表示出了这个例子中每一步小虫的位置（标有圆点的方格就是小虫的当前位置），以及纸带的状况。
开始：小虫在最左边的方格，根据程序的第一行，读入黑色应该前移。
第二步：仍然读入黑，根据程序的第一行，前移。
第三步：这个时候读入的是白色，根据程序的第二行，应该把这个方格涂黑，而没有其他的动作。假设这张图上方格仍然没有涂黑，而在下一时刻才把它表示出来。
第四步：当前方格已经是黑色的，因此小虫读入黑色方格，前移。
第五步：读入白色，涂黑方格，原地不动。
第六步：当前的方格已经被涂黑，继续前移。
第七步：读入黑色，前移
小虫的动作还会持续下去……。我们看到，小虫将会不停的重复上面的动作不断往前走，并会把所有的纸带涂黑。
显然，你还可以设计出其他的程序来，然而无论你的程序怎么复杂，也无论纸带子的情况如何，小虫的行为都会要么停留在一个方格上，要么朝一个方向永远运动下去，或者就是在几个方格上来回打转。然而，无论怎样，小虫比起真实世界中的虫子来说，还有一个致命的弱点：那就是如果你给它固定的输入信息，它都会给你固定的输出信息！因为我们知道程序是固死的，因此，每当黑色信息输入的时候，无论如何它都仅仅前移一个方格，而不会做出其他的反应。它似乎真的是机械的！
如果我们进一步更改小虫模型，那么它就会有所改进，至少在给定相同输入的情况下，小虫会有不同的输出情况。这就是加入小虫的内部状态！我们可以作这样的一个比喻：假设黑色方格是食物，虫子可以吃掉它，而当吃到一个食物后，小虫子就会感觉到饱了。当读入的信息是白色方格的时候，虽然没有食物但它仍然吃饱了，只有当再次读入黑色时候它才会感觉到自己饥饿了。因而，我们说小虫具有两个内部状态，并把它内部状态的集合记为：S={饥饿，吃饱}。这样小虫行为的时候就会不仅根据它的输入信息，而且也会根据它当前的内部状态来决定它的输出动作，并且还要更改它的内部状态。而它的这一行动仍然要用程序控制，只不过跟上面的程序比起来，现在的程序就更复杂一些了，比如：
程序3：
输入当前内部状态输出下时刻的内部状态
黑饥饿涂白吃饱
黑吃饱后移饥饿
白饥饿涂黑饥饿
白吃饱前移吃饱
这个程序复杂多了，有四行，原因是你不仅需要指定每一种输入情况下小虫应该采取的动作，而且还要指定在每种输入和内部状态的组合情况下小虫应该怎样行动。看看我们的虫子在读入黑白白黑白……这样的纸带的时候，会怎样？仍然用下面的一系列图来表示，灰色的圆点表示饥饿的小虫，白色的圆点表示它吃饱了。为了清晰，我们把小虫将要变成的状态写到了图的下一行。
假定它仍然从左端开始，而且开始的时候小虫处于饥饿状态。这样读入黑色，当前饥饿状态，根据程序第一行，把方格涂白，并变成吃饱（这相当于把那个食物吃了，注意吃完后，小虫并没动）。
第二步：当前的方格变成了白色，因而读入白色，而当前的状态是吃饱状态，那么根据程序中的第四条前移，仍然是吃饱状态；
第三步：读入白色，当前状态是吃饱，因而会重复第二步的动作。
涂白方格，变成吃饱
前移，仍然吃饱
前移，保持吃饱
第四步：仍然重复上次的动作。
第五步：读入黑色，当前状态是吃饱，这时候根据程序的第二行应该后移方格，并转入饥饿状态；
第六步：读入白色，当前饥饿状态，根据程序第三行应该涂黑，并保持饥饿状态（各位注意，这位小虫似乎自己吐出了食物！）；
第七步，读入黑色，当前饥饿，于是把方格涂白，并转入吃饱状态（呵呵，小虫把刚刚自己吐出来的东西又吃掉了！）。
第八步，读入白色，当前吃饱，于是前移，保持吃保状态。
这时候跟第四步的情况完全一样了，因而小虫会完全重复5、6、7、8步的动作，并永远循环下去。似乎最后的黑色方格是一个门槛，小虫无论如何也跨越不过去了。
小虫的行为比以前的程序复杂了一些。尽管从长期来看，它最后仍然会落入机械的循环或者无休止的重复。然而这从本质上已经与前面的程序完全不同了，因为当你输入给小虫白色信息的时候，它的反应是你不能预测的！它有可能涂黑方格也有可能前移一个。当然前提是你不能打开小虫看到它的内部结构，也不能知道它的程序，那么你所看到的就是一个不能预测的满地乱爬的小虫。如果小虫的内部状态数再增多呢，那么它的行为会更加的不可预测！ 好了，如果你已经彻底搞懂了我们的小虫是怎么工作的，那么你已经明白了图灵机的工作原理了！因为从本质上讲，最后的小虫模型就是一个图灵机！
工商网监
评论