[拼音]：nengxingxing he yiban digui

[外文]：effectiveness and general recursiveness

数理逻辑、数学和计算机理论科学所研究的一个重要课题。数学中很多定理，尤其是存在性定理往往不是能行的，如虽然已经证明了某某方程有根，但却无法求出其根，甚至无法求得比较精确的近似值。对很多数学家尤其是采用直觉主义或构造主义观点的数学家说来，欠缺能行性的定理是不能接受的。然而对于所谓“能行性”，长期以来都未有精确的定义，以致于很难对之作深入的探讨。

原始递归函数(见递归论)是处处可以计算的，它又包括了人们在数论中所曾使用过的数论函数，看来似乎可把“能行可计算函数”限于原始递归函数。对此，德国数学家W.阿克曼于1924年构造了一个数论函数，它是可计算的，但是却不是原始递归函数，从而推翻了上述猜想。1932年，美国数学家A.丘奇提出了λ换位演算。在这演算内可以表示自然数，并且利用运算子λ而作出了λ可定义函数，其中包括原始递归函数。1934年，K.哥德尔根据J.赫尔布兰德的一个建议，提出了一般递归函数。其定义是：如果能够作出一组方程式，使得只利用变元代以常数以及相等的数可以彼此替换两个过程，便能够导出函数f的一切值，而函数f便叫做一般递归函数。不久，美国学者S.C.克利尼证明了这个一般递归函数与丘奇的λ可定义全函数是相同的，并且也与使用叠置、原始递归式和摹状算子而得到的全函数相同。1936年，英国数学家A.M.图林提出以其姓命名的图林机器理论，并证明了可用图林机器计算的数论全函数恰好是λ可定义全函数。由于这些函数类都比原始递归函数类更广泛而又彼此相等，因此丘奇也于1936年提出了一个论题，即能行可计算的全函数类恰好是λ可定义全函数类，也就是一般递归函数类。后来发现，把能行可计算性推广到部分函数更有意义也更重要。于是，丘奇的论题便成为：能行可计算的部分函数恰好是递归部分函数，而能行可计算的全函数也恰好是递归全函数，亦即一般递归函数。

根据丘奇的论题，便可以对判定问题作进一步的讨论。

判定问题分问答题与求作题两种。要求回答“是”“否”的叫做问答题，要求用一个自然数回答的叫做求作题。例如，“3整除 5吗？”是问答题，“求m，n之积”是求作题。问题又分个别题与大量题两种。如果在问题中已给出全部数据，因而当时已有具体而明确答案的叫做个别题；问题中并未给出全部数据而含有参数，须把参数代以具体数值后才能作出答案的叫做大量题。对个别题除要求答案正确外，别无要求。对大量题则一般要求在未给出参数的值时，先有一个公共的解法，参数值给出后，即能按这个公共解法而求得答案。例如，把求作题的答案看作参数 m，n的函数ｆ(m，n)，把问答题本身看作参数m，n的谓词P(m，n)，则求作题就是求函数ｆ(m，n)的值，而问答题则是判定谓词P(m，n)的真假。如果函数ｆ(m，n)是递归全函数即一般递归函数，该问题就可以完全解决。因为， m，n给出后必能求得ｆ(m，n)之值作为答案。如果ｆ(m，n)是递归部分函数，而且能够判知ｆ(m，n)有无定义，这时 ｆ(m，n)叫做潜伏递归函数。那末，当m，n 的值给出以后，就可以判定ｆ(m，n)有无定义，若有定义必定可求得 ｆ(m，n) 的值作为答案，若无定义亦可用“无定义”作为答案。所以，对这个问题仍是可以完全解决的。如果ｆ(m，n)是递归部分函数而且不是潜伏递归，则当m，n的值给出后，只能假定它有定义而计算下去。这样，若ｆ(m，n)有定义，必可求得其值作为答案；若ｆ(m，n)没有定义，计算过程则有可能永无休止地继续下去而无法给出答案。对此，就可以说这个问题是可以半解决的，因为它只要有答案必能给出。如果ｆ(m，n)不是递归半函数，即使ｆ(m，n)有值也未必能算出，因此说这个问题是完全不可解决的。

对于问答题 P(m，n)可先引进它的特征函数 ｆ(m，n)，当P(m，n)成立时，ｆ(m，n)=0；当 P(m，n)不成立时，ｆ(m，n)=1。如果ｆ(m，n)为递归全函数，则可以说这个问答题是完全可以判定的。因为，m，n给出后，必可判定P(m，n)的真假。如果 ｆ(m， n)不是递归全函数，则不应马上说这个问题完全不可解。这时，先引进两个部分函数如下：ｆ1(m，n)=0当P(m，n)成立时，否则作为无定义;ｆ2(m，n)=0当P(m，n)不成立，否则作为无定义。如果ｆ1(m，n) 是递归部分函数，则可说问答题P(m，n)是可正半判定的；如果 ｆ2(m，n)是递归部分函数，则问答题P(m，n) 是可负半判定的。如果 ｆ1与ｆ2都不是递归半函数，便可说问答题是完全不可判定的。容易证明，如果 ｆ1(m，n)与ｆ2(m，n)都是递归半函数，亦即如果问答题P(m，n)既可正半判定又可负半判定，那末P(m，n)便是完全可判定的。因为，人们可以同时计算 ｆ1(m，n)与ｆ2(m，n)，结果必有一函数有值，从而可以判定P(m，n)的真假。

严正声明：本文由历史百科网注册或游客用户仇鹤蓉自行上传发布关于» 能行性和一般递归的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：仇鹤蓉；本文链接：https://www.freedefine.cn/wenzhan/125099.html