递归函数论是30年代发展起来的,是数理逻辑的一个分支,广泛应用于计算机科学的可计算性、计算复杂性和程序理论等方面。

一、递归函数和可计算性

  可以说递归函数和可计算性是同一概念。
  (1)可计算性

  (2)可计算性与递归函数

  (3)几个可计算的与不可计算的函数