图灵机简介和原理分析.docVIP

诺依曼就是根据图灵的设想才设计出第一台计算机的〕。另一方面，根据图灵机这一根本简洁的概念，我们还可以看到可计算的极限是什么。也就是说实际上计算机的本领从原那么上讲是有限制的。请注意，这里说到计算机的极限并不是说它不能吃饭、扫地等硬件方面的极限，而是仅仅就从信息处理这个角度，计算机也仍然存在着极限。这就是图灵机的停机问题。 图灵机原理及分析 图灵的根本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作以下两种简单的动作： 把注意力从纸的一个位置移动到另一个位置； 一个状态存放器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。 这个机器的每一局部都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程 下面我们用另一种思想来理解图灵机： 注：以下内容来自百度文库： 程序： 黑　　　　饥饿　　　　涂白　　　　　吃饱 黑　　　　吃饱　　　　后移　　　　　饥饿 白　　　　饥饿　　　　涂黑　　　　　饥饿 白　　　　吃饱　　　　前移　　　　　吃饱 即如果当前处于饥饿状态，那么有食物就吃掉,没有食物就“吐出食物〞；如果当前处于吃饱的状态，那么如果没有食物就前移，如果有就后退，并且转入饥饿状态。那么当小虫子读入黑白白黑白………… 图灵机是一个会对输入信息进行变换给出输出信息的系统。比方前面说的小虫，纸带上的一个方格一个方格的颜色信息就是对小虫的输入，而小虫所采取的行动就是它的输出。不过这么看，你会发现，似乎小虫的输出太简单了。因为它仅仅就有那么几种简单的输出动作。然而，不要忘了，复杂性来源于组合！虽然每一次小虫的输出动作很简单，然而当把所有这些输出动作组合在一起，就有可能非常复杂！比方我们可以把初始时刻的纸带看作是输入信息，那么经过任意长的时间比方说100年后，小虫通过不断的涂抹纸带最后留下的信息就是输出信息了。那么小虫完成的过程就是一次计算。事实上，在图灵机的正规定义中，存在一个所谓的停机状态，当图灵机一到停机状态，我们就认为它计算完毕了，因而不用费力的等上100年。 我们自然可以通过组合假设干图灵机完成更大更多的计算，如果把一个图灵机对纸带信息变换的结果又输入给另一台图灵机，然后再输入给别的图灵机……，这就是把计算进行了组合。