团工具塑·口 4第11-12屏供共81屏 1迅副7)视密选项,X 假设一台筒化的图灵机只有两种內部状态:“快乐”和“悲伤”。它 也只能识别出三种符号:椭圆形、矩形和月矛形(但它不会在意各种矩 系统按照图灵机表选行按部就班的操作之后(操作过略),会在莱 形、椭圆形和月牙形之间的差别,并把圆看成是椭圆的一个特例)。在 时刻“停机”,并提交这样的输出行 这里,月牙形代表了一个具体的问题的边界。整台机器的困灵机表可以 是这样的: 《≤ 內部状态为“悲伤” 内部状态为“快 读入椭圆删除读入符号,打印椭圆,右移一格,删除读入符号 快 继续“悲伤” 打印月牙形,尔 后停机 读入矩形「删除读入符号,打印图,右移一格 继续“悲伤 图0-2图灵机的加法运算(停机状态) 读入月牙删除读入符号,左移一格,打印月牙 形 形,转为“快乐” 如果把这里我们看到的圆形释为最小的自然数单位“1”,并把短 表0-1图灵机的加法机表 形解榉为“加”的话,上面所呈现出来的图灵机,实质上就是一台加法 机。上面所展示的具体运算,就是“二加一等于三。很显然,这种“加 现在就假设读写头(用三角形表示)面对的是这样一段输入: 法机”的功能非常单一,它自身是无力模拟各种计算方式的。而要向“模 拟各种计算函数”的方向继续迈步,就得引入“图灵机”概念的衍生 《 万能图灵机( Universal Turing Machine,筒称UM):假设有这样 台困灵机,其图灵机表所包含的指导规则允许系统本身模拟任何一个其 它的图灵机的行为,那么这样的图灵机就是一台UM。UTM乃是今天 我们的市售计算机的数学抽象。原则上说,UM的具有这梯的功能(此 伤 功能由下述论题所表达) 图0-1图灵机的加法运算(初始状态)