算法图灵机及可计算性理论.ppt

图灵机与可计算性理论 图灵对计算本质的揭示 在哥德尔研究成果的影响下20世纪30年代后期, 图灵(A.M. Turing)从计算一个数的一般过 程入手对计算的本质进行了研究,从而实现了 对计算本质的真正认识 根据图灵的研究,直观地说,所谓计算就 是计算者(人或机器)对一条两端可无限延长 的纸带上的一串0和1执行指令,一步一步地改 变纸带上的0或1,经过有限步骤,最后得到 个满足预先规定的符号串的