算法设计与分析 第十章.ppt

图灵机 1936年图灵提出了一个抽象计算模型 图灵机并用它来精确定义可计算函数图灵机的基本思想是模拟人用纸笔进行数学运算的过程这个运算过程可分解为下面两种简单的动作 1.在纸上写或擦除某个符号 2.把注意力从纸的一个位置移动到另一个位置 在每个阶段将由执行运算的人决定下一步的动作而他的决定依赖于此人当前所关注的是纸上哪个位置的符号以及此人当前思维的状态 Turing Machine Determi