计算机的过去、现在与未来

《计算机的过去、现在与未来》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机过去现在未来Lecture5-Turing机计算机程序算法及应用AlanTuring的抽象计算机－图灵机1936年,阿兰·图灵提出了一种抽象的计算模型─图灵机(TuringMachine)，其基本思想是－用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：(a)在纸上写上或擦除某个符号；(b)从纸的一个位置移动到另一个位置；图灵机-横向视图图灵机为模拟人的这种运算过程，图灵机器包括：①一条(无限长)纸带(tape)。纸带被划分为一个接一个的小格子(cell)，每

2、个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号□表示空白。纸带上的格子从左到右依此被编号为0,1,2,...，纸带的右端可以无限伸展。②一个读写头(read-writeHead)。该读写头可在纸带上左右移动，它能读出当前格子上的符号(Characters)，并能改变当前格子上的符号。③一个状态寄存器(Register)，用来保存图灵机当前所处状态。图灵机的所有可能状态的数目是有限的，且有1个特殊的状态，称为停机状态。(Halt)图灵机④一套控制规则。它根据当前机器所处的状态以及当前

3、读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态，纵向视图如下，无限长的带子读写头状态寄存器控制规则图灵机-工作原理首先，读写头在纸带上读出一个方格的信息，并且根据它当前的内部状态开始对程序进行查表，然后得出一个输出动作，也就是是否往纸带上写信息，还是移动读写头到下一个方格(cell)。程序同时告诉它下一时刻内部状态转移到哪一个。具体的程序就是一个列表，也叫做规则表(transi-tiontable)，形式如下：当前内部状态s输入数值i输出动作o下一时

4、刻的内部状态s'B1前移CA0往纸带上写1BC0后移A…………图灵机图灵机只要根据每一时刻读写头读到的信息(纸带格子里的符号)和当前的内部状态进行查表，就可以确定它下一时刻的内部状态和输出动作了。图灵机虽然简单，但只要变化它的程序（也就是上面的规则表），那么它就可能为你做任何计算机能够完成的工作。因此可以说，图灵机就是一个最简单的计算机模型！如何理解图灵机-小虫模型？小虫的比喻考虑这样一个问题。假设一个小虫在地上爬，那么我们应该怎样从小虫信息处理的角度来建立它的模型？首先，我们需要对小虫所在的环境

5、进行建模。我们不妨就假设小虫所处的世界是一个无限长的纸带，这个纸带上被分成了若干小的方格，而每个方格都仅仅只有黑和白两种颜色。……如何理解图灵机？显然，这个小虫要有眼睛或者鼻子或者耳朵等等感觉器官来获得世界的信息。首先，为简化问题，假设它仅仅具有1个感觉器官：眼睛，且它的视力短得可怜，也就是说它仅仅能够感受到它所处的方格的颜色。因而这个方格所在的位置的黑或者白色的信息就是小虫的输入信息。另外，还需要为小虫建立输出装置，即让它能动起来。我们仍然考虑最简单的情况：小虫的输出动作就是往纸带上前爬一个方

6、格或者后退一个方格。小虫I代模型仅仅有了输入装置以及输出装置，小虫还不能动起来，原因很简单，它并不知道该怎样在各种情况下选择它的输出动作。于是我们就需要给它指定行动的规则，这就是程序！假设我们记小虫的输入信息集合为：I={黑色，白色}它的输出可能行动的集合就是：O={前移，后移}那么程序就是要告诉它在给定了输入，比如“黑色”情况下，它应该选择什么输出。程序1(小虫I代模型)：输入输出黑色前移白色后移小虫I代模型这个程序非常简单，它告诉小虫当读到一个黑色方格的时候就往前走一个方格，当读到一个白色方格

7、的时候就后退一个格。我们不妨假设，小虫所处的世界的一个片断是：黑黑黑白白黑白……，小虫从左端开始运动，，，……开始小虫I代模型小虫I代移动模型的改进－I代小虫模型过于简单，为使它更贴近现实，现在假设：小虫除了可以机械地在世界上移动以外，还会对世界本身造成影响，因而改变这个世界。比如虫子会对纸带上格子里的颜色进行乱涂画等。小虫II代模型在新的小虫II代模型中，也就相当于必须假设小虫可以改写纸带上的信息。因而，小虫可能的输出动作集合就变成了：O={前移，后移，涂黑，涂白}这个时候，可把程序1改写一

8、下，比如：程序2：输入输出黑前移白涂黑(此处与程序1不同)纸带是黑黑白白黑……，小虫会怎样行动呢？下面的图表示出了这个例子中每一步小虫的位置。小虫II代模型开始：小虫在最左边的方格，根据程序的第一行，读入黑色应该前移。……第二步：仍然读入黑，根据程序的第一行，前移。……第三步：这个时候读入的是白色，根据程序的第二行，应该把这个方格涂黑，而没有其他的动作。假设这张图上方格仍然没有涂黑，而在下一时刻才把它表示出来。……小虫II代模型……第四步：当前方格已经是黑色的，因