图灵机简介和原理分析

图灵机简介和原理分析图灵机简介和原理分析 摘要摘要 1936 年 阿兰 图灵提出了一种抽象的计算模型 图灵机 Turing Machine 图灵机是指一个抽象的机器 可被视作 任意解决有限数学逻辑过程的机器 它提供了一种简单有效的解决 逻辑过程的方法 加快了后来诺依曼设计的计算机的出现 本文将 对图灵机的原理和历史等进行简介和分析 关键字 图灵机 计算模型 一 一 图灵机的历史发展 图灵机被公认为现代计算机的原型 这台机器可以读入一 系列的零和一 这些数字代表了解决某一问题所需要的步骤 按这个步骤走下去 就可以解决某一特定的问题 这种观念在 当时是具有革命性意义的 因为即使在 50 年代的时候 大部分 的计算机还只能解决某一特定问题 不是通用的 而图灵机从 理论上却是通用机 1936 年 图灵向伦敦权威的数学杂志投了一篇论文 题为 论数字计算在决断难题中的应用 在这篇开创性的论文中 图 灵给 可计算性 下了一个严格的数学定义 并提出著名的图灵机 Turing Machine 的设想 图灵机 不是一种具体的机器 而 是一种思想模型 可制造一种十分简单但运算能力极强的计算装 置 用来计算所有能想像得到的可计算函数 图灵机 与 冯 诺 伊曼机 齐名 被永远载入计算机的发展史中 1950 年 10 月 图 灵又发表了另一篇题为 机器能思考吗 的论文 成为划时代之作 也正是这篇文章 为图灵赢得了 人工智能之父 的桂冠 在图灵看来 这台机器只用保留一些最简单的指令 一个 复杂的工作只用把它分解为这几个最简单的操作就可以实现了 在当时他能够具有这样的思想确实是很了不起的 图灵机的产生一方面奠定了现代数字计算机的基础 要知 道后来冯 诺依曼就是根据图灵的设想才设计出第一台计算机的 另一方面 根据图灵机这一基本简洁的概念 我们还可以看 到可计算的极限是什么 也就是说实际上计算机的本领从原则 上讲是有限制的 请注意 这里说到计算机的极限并不是说它 不能吃饭 扫地等硬件方面的极限 而是仅仅就从信息处理这 个角度 计算机也仍然存在着极限 这就是图灵机的停机问题 二 二 图灵机原理及分析图灵机原理及分析 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算 的过程 他把这样的过程看作下列两种简单的动作 在纸上写上或擦除某个符号 把注意力从纸的一个位置移动到另一个位置 而在每个阶段 人要决定下一步的动作 依赖于 a 此人 当前所关注的纸上某个位置的符号和 b 此人当前思维的状态 为了模拟人的这种运算过程 图灵构造出一台假想的机器 该 机器由以下几个部分组成 一条无限长的纸带 纸带被划分为一个接一个的小格子 每个格子上包含一个来自有限字母表的符号 字母表中有一个 特殊的符号 表示空白 纸带上的格子从左到右依此被编号为 0 1 2 纸带的右端可以无限伸展 一个读写头 该读写头可以在纸带上左右移动 它能读出 当前所指的格子上的符号 并能改变当前格子上的符号 一个状态寄存器 它用来保存图灵机当前所处的状态 图 灵机的所有可能状态的数目是有限的 并且有一个特殊的状态 称为停机状态 一套控制规则 它根据当前机器所处的状态以及当前读写 头所指的格子上的符号来确定读写头下一步的动作 并改变状 态寄存器的值 令机器进入一个新的状态 这个机器的每一部分都是有限的 但它有一个潜在的无限 长的纸带 因此这种机器只是一个理想的设备 图灵认为这样 的一台机器就能模拟人类所能进行的任何计算过程 下面我们用另一种思想来理解图灵机 注 以下内容来自百度文库 小虫的比喻 我们不妨考虑这样 一个问题 假设一个小虫在地 上爬 那么我们应该怎样从小虫信息处理的角度来建立它的模型呢 首先 我们需要对小虫所在的环境进行建模 我们不妨假设小虫所 处的世界是一个无限长的纸带 这个纸带上被分成了若干小方格 而每个方格都只有黑白两种颜色 黑色表示该方格有食物 白色就 表示没有 假设小虫仅具有一个感觉器官 眼睛 而且它的视力差 得可怜 也就是说它仅仅能够感受到它所处的方格的颜色 因而这 个方格所在的位置的黑色或者白色的信息就是小虫的输入信息 其 次 小虫有输出动作 它可以在方格上前移 后移 还可以涂写方 格成黑色或者白色 最后 小虫还会有两种内部状态 即 饥饿 吃 饱 这样小虫的行动按照下面的程序进行 程序 输入 当前内部状态 输出 下时刻的内部状态 黑 饥饿 涂白 吃饱 黑 吃饱 后移 饥饿 白 饥饿 涂黑 饥饿 白 吃饱 前移 吃饱 即如果当前处于饥饿状态 则有食物就吃掉 没有食物就 吐出 食物 如果当前处于吃饱的状态 则如果没有食物就前移 如果有 就后退 并且转入饥饿状态 那么当小虫子读入黑白白黑白 这 样的纸带的时候 会怎样行动呢 小虫用圆圈表示 它从最左边开始 移动 灰色表示饥饿状态 白色表示吃饱状态 箭头表示移动的方向 从上到下 小虫一步一步 地根据纸带的颜色和它自己的内部状态查 找规则表中的对应项而采取行动 例如第 5 步读入方格是黑色 内 部状态为吃饱 根据这两项输入信息查找规则表找到对应项是第二 项 根据小虫应该后移 且内部状态变为饥饿 不难看到 到 了第 8 步 情况跟第 4 步完全相同 输入都是白色纸带和饥饿状态 根 据程序 小虫将重复 4 8 之间的动作 并一直持续下去 尽管 从长期来看 小虫会落入机械的循环 然而当你输入给小虫白色信 息的时候 它的反应可能完全不同 如第 4 步和第 6 步的行为 所以 只要小虫子的内部状态和程序非常复杂 那么小虫的行为也 会越来越超出你的想象 相信你 已经明白了这个小虫模型 那么你 就掌握了图灵机的工作原理 因为从本质上讲 这个小虫模型就是 一台图灵机 图灵机是一个会对输入信息进行变换给出输出信息的系统 比如 前面说的小虫 纸带上的一个方格一个方格的颜色信息就是对小虫 的输入 而小虫所采取的行动就是它的输出 不过这么看 你会发 现 似乎小虫的输出太简单了 因为它仅仅就有那么几种简单的输 出动作 然而 不要忘了 复杂性来源于组合 虽然每一次小虫的 输出动作很简单 然而当把所有这些输出动作组合在一起 就有可 能非常复杂 比如我们可以把初始时刻的纸带看作是输入信息 那 么经过任意长的时间比如说 100 年后 小虫通过不断的涂抹纸带最 后留下的信息就是输出信息了 那么小虫完成的过程就是一次计算 事实上 在图灵机的正规定义中 存在一个所谓的停机状态 当图 灵机一到停机状态 我们就认为它计算完毕了 因而不用费劲的等 上 100 年 我们自然可以通过组合若干图灵机完成更大更多的计算 如果