递归函数论是30年代发展起来的,是数理逻辑的一个分支,广泛应用于计算机科学的可计算性、计算复杂性和程序理论等方面。
一、递归函数和可计算性
可以说递归函数和可计算性是同一概念。
(1)
可计算性
(2)
可计算性与递归函数
(3)
几个可计算的与不可计算的函数