一般递归函数

数学术语

一般递归函数(general recursive function)亦称递归函数，是指一类具有能行可计算的全数论函数。不仅如此，现在一般认为，能行可计算的全数论函数恰好就是一般递归函数，一般递归函数的概念最初是由美籍奥地利数学家哥德尔于1934年定义的，也就是现在所谓的埃尔布朗-哥德尔可计算函数，即若一个数论函数可由某个等式系ε定义，则哥德尔称f为一般递归的。1936年，美国逻辑学家、数学家克林(S.C.Kleene)引进了μ递归函数的概念，并进而证明了它恰好与哥德尔的一般递归函数类一致。此后，一般递归函数的概念便经常用μ递归的形式给出。莫绍揆于1965年利用一般递归式的概念提出了一般递归函数的另一种等价定义形式：从本原函数出发，经叠置和一般递归式作用而生成的函数称为一般递归式。注意到，比起等式系或μ算子来，一般递归式更好地体现了一般递归的意义，因此，利用一般递归式引入一般递归函数概念当是最为合理的。而且也是原始递归函数概念的一种自然推广。此外，一般递归函数恰好是部分递归函数中的全函数，不过与全体部分递归函数不一样，全体一般递归函数不是能行可列的。

发展简要

一般递归函数(gereral recursive function)是原始递归函数的推广。二十世纪初，为了一般地定义能行过程便引进了一般递归函数的概念。这个概念最初是哥德尔在厄尔勃朗的信的启示下提出来的。后来，克林改进了哥德尔的定义并发展了一般递归函数的理论。在此之前，邱吉引进了记号，定义了可定义函数的概念。以后，波斯特和图灵又引进了图灵机器并定义了可计算函数的概念。后来证明所有这些概念都与一般递归函数等价。由此可见，一般递归函数是非常重要的。一般递归函数集包含原始递归函数集为其真子集。

基本介绍

凡原始递归函数都是一般递归函数，反之不然。要找一个非原始递归函数的一般递归函数并不是一件容易的事。这就说明日常遇到的数论函数几乎都是原始递归函数。第一个找出非原始递归函数的例子的是德国数学家阿克曼，从而证实了一般递归函数的确比原始递归函数为广。

常见的一般递归函数的定义有两种，第一种都是在原始递归函数的定义中加进另一种则使用一般递归式，摹状式而得。

一般递归式通常写为：

其中，为归宿于零的函数，即从任何一值(作为第一变元)经过有限次迭置之后的值必为零。

摹状式一般写为：

但要求对任何都有使得

其中，表示满足(1)的最小自然数。

已经证明这两个定义是等价的。邱吉建议把一般递归函数考虑为能行可计算函数的数学定义。这个论断被称为邱吉论题。由于可计算函数是个无定义概念，所以，邱吉论题是无法证明的。但是，根据种种理由，大家都相信它是正确的。这样，凡是有一个计算过程或一个算法可以将函数值计算出来的函数便都是一般递归函数。利用这一结果解决了许多悬而未决的判定问题，重新研究了传统的描述集合论，阐明了半直觉主义数学中所使用的能行性概念，促进了新兴的计算机科学的发展。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省