基本知识 ·可计算理论 研究计算的一般性质的数学理论，也称算法理论 通过建立计算的数学模型，区分可计算与不可计算 可计算函数：能够在抽象计算机上编出程序计算 其值的函数。这样的程序称为算法 这样就可以讨论哪些函数是可计算的，哪些函数 是不可计算的 可计算性：指一个实际问题是否可以使用计算机 来解决（能解决一定是指有限步内解决） -上一讲介绍的就是计算模型和可计算函数基 本 知 识 • 可计算理论 – 研究计算的一般性质的数学理论，也称算法理论 – 通过建立计算的数学模型, 区分可计算与不可计算 – 可计算函数：能够在抽象计算机上编出程序计算 其值的函数。这样的程序称为算法 – 这样就可以讨论哪些函数是可计算的，哪些函数 是不可计算的 – 可计算性：指一个实际问题是否可以使用计算机 来解决（能解决一定是指有限步内解决） – 上一讲介绍的就是计算模型和可计算函数 4