递归论的介绍

递归论的介绍

递归论（Recursion theory）是数理逻辑的重要分支之一，研究解决问题的可行的计算方法和计算的复杂程度的一门学科，尤其是研究递归函数及其推广。递归函数是数论函数的一种，其定义域与值域都是自然数集。只是由于构作函数方法的不同而有别于其他的数论函数。将定义域推广到不限于自然数集时，便是所谓广义的递归函数。递归论研究的函数主要包括本原函数、原始递归函数、递归半函数和递归全函数或称一般递归函数、可摹状函数等等。