1.1理论上的可计算一一可计算性理论 研究目标 确定什么问题是可计算的 合理的计算模型 已有的:递归函数、 TUring机、λ演算、Post系统等 条件:计算一个函数只要有限条指令 每条指令可以由模型中的有限个计算步骤完成 指令执行的过程是确定的 Church- Tur ing论题 如果一个函数在某个合理的计算模型上可计算,那么它在 Tur ing机上也是可计算的 可计算性是不依赖于计算模型的客观性质5 1.1 理论上的可计算――可计算性理论 研究目标 确定什么问题是可计算的 合理的计算模型 已有的：递归函数、Turing 机、 λ 演算、Post 系统等 条件：计算一个函数只要有限条指令 每条指令可以由模型中的有限个计算步骤完成 指令执行的过程是确定的 Church-Turing 论题 如果一个函数在某个合理的计算模型上可计算，那么它在 Turing 机上也是可计算的 可计算性是不依赖于计算模型的客观性质