什么是可计算性理论?

什么是可计算性理论?

[拼音]：kejisuanxing lilun

[外文]：computability theory

研究计算的一般性质的数学理论，也称算法理论或能行性理论。它通过建立计算的数学模型（例如抽象计算机），精确区分哪些是可计算的，哪些是不可计算的。计算的过程就是执行算法的过程。可计算性理论的重要课题之一，是将算法这一直观概念精确化。算法概念精确化的途径很多，其中之一是通过定义抽象计算机，把算法看作抽象计算机的程序。通常把那些存在算法计算其值的函数叫作可计算函数。因此，可计算函数的精确定义为：能够在抽象计算机上编出程序计算其值的函数。这样就可以讨论哪些函数是可计算的，哪些函数是不可计算的。

产生和历史

可计算性理论起源于对数学基础问题的研究。20世纪30年代，为了讨论是否对于每个问题都有解决它的算法，数理逻辑学家提出了几种不同的算法定义。K.哥德尔和S.C.克林尼提出了递归函数的概念，A.丘奇提出λ转换演算， A.M.图灵和E.波斯特各自独立地提出了抽象计算机的概念（后人把图灵提出的抽象计算机称为图灵机），并且证明了这些数学模型的计算能力是一样的，即它们是等价的。著名的丘奇-图灵论题也是丘奇和图灵在这一时期各自独立提出的。后来，人们又提出许多等价的数学模型，如A.马尔可夫于40年代提出的正规算法（后人称之为马尔可夫算法），60年代前期提出的随机存取机器模型（简称 RAM）等。50年代末和60年代初，胡世华和J.麦克阿瑟等人各自独立地提出了定义在字符串上的递归函数。

学科内容

若m和n是两个正整数，并且m≥n时，求m和n的最大公因子的欧几里得算法可表示为

E1［求余数］以n 除m 得余数r。

E2［余数为0吗?］若r＝0，计算结束，n即为答案;否则转到步骤E3。

E3［互换］把m的值变为n，n的值变为r，重复上述步骤。

依照这三条规则指示的步骤，可计算出任何两个正整数的最大公因子。可以把计算过程看成执行这些步骤的序列。我们发现，计算过程是有穷的，而且计算的每一步都是能够机械实现的（机械性）。为了精确刻划算法的特征，人们建立了各种各样的数学模型。

图灵机

一种在理论计算机科学中广泛采用的抽象计算机，它是图灵在1936年提出的，用于精确描述算法的特征。可用一个图灵机来计算其值的函数是可计算函数，找不到图灵机来计算其值的函数是不可计算函数。可以证明，存在一个图灵机U，它可以模拟任何其他的图灵机。这样的图灵机 U称为通用图灵机。通用图灵机正是后来出现的存储指令的通用数字计算机的理论原型。

λ转换演算

一种定义函数的形式演算系统，是A.丘奇于1935年为精确定义可计算性而提出的。他引进λ记号以明确区分函数和函数值，并把函数值的计算归结为按一定规则进行一系列转换，最后得到函数值。按照λ转换演算能够得到函数值的那些函数称为λ可定义函数（见λ转换演算）。

丘奇-图灵论题

可计算性理论的基本论题，也称图灵论题，它规定了直观可计算函数的精确含义。丘奇论题说：λ可定义函数类与直观可计算函数类相同。图灵论题说：图灵机可计算函数类与直观可计算函数类相同。图灵证明了图灵机可计算函数类与λ可定义函数类相同。这表明图灵论题和丘奇论题讲的是一回事，因此把它们统称为丘奇－图灵论题。直观可计算函数不是一个精确的数学概念，因此丘奇-图灵论题是不能加以证明的。30年代以来，人们提出了许多不同的计算模型来精确刻划可计算性，并且证明了这些模型都与图灵机等价。这表明图灵机和其他等价的模型确实合理地定义了可计算性，因此丘奇－图灵论题得到了计算机科学界和数学界的公认。

原始递归函数

自变量值和函数值都是自然数的函数，称为数论函数。原始递归函数是数论函数的一部分。首先规定少量显然直观可计算的函数为原始递归函数，它们是：函数值恒等于0的零函数C0，函数值等于自变量值加1的后继函数S，函数值等于第i个自变量值的n元投影函数P嬪。然后规定，原始递归函数的合成仍是原始递归函数，可以由已知原始递归函数简单递归地计算出函数值的函数仍是原始递归函数。例如，和函数f(x，y)=x+y可由原始递归函数P(1)1和S递归地计算出函数值

f(x，0)=P(1)1(x) f(x，S(y))=S(f(x，y))

比如，f(4，2)可这样计算，首先算出f(4，0)=P(1)1(4)=4，然后计算

f(4，1)=S(f(4，0))=S(4)=5

f(4，2)=S(f(4，1))=S(5)=6

因此，和函数是原始递归函数。显然，一切原始递归函数都是直观可计算的。许多常用的处处有定义的函数都是原始递归函数，但并非一切直观可计算的、处处有定义的函数都是原始递归函数。

部分递归函数

为了包括所有的直观可计算函数，需要把原始递归函数类扩充为部分递归函数类。设g(x1，…，xn，z)是原始递归函数，如果存在自然数z使g(x1，…，xn，z)=0，就取f(x1，…，xn)的值为满足g(x1，…，xn，z)=0的最小的自然数z；如果不存在使g(x1，…，xn，z)=0的自然数z，就称f(x1，…，xn)无定义。把如上定义的函数f加到原始递归函数类中，就得到部分递归函数类。因为不能保证如上定义的f在一切点都有定义，故称其为部分函数。处处有定义的部分递归函数称为递归函数。部分递归函数类与图灵机可计算函数类相同。对于每个n元部分递归函数f，可以编一个计算机程序P，以自然数x1，…，xn作为输入，若f(x1，…，xn)有定义，则P函数值执行终止并输出的f(x1，…，xn)，否则P不终止。

递归集

递归集最初是对于元素都是自然数的集合定义的，它们是有算法确定每个自然数是否为其元素的集合。可以将递归集的概念推广到其他集合。所讨论的对象的全体称为域，如果有算法确定域中任意元素是否属于A，则称A为递归集。对于每个递归集，可以编一个计算机程序，以域中任意元素作为输入，计算执行该程序都可给出适当的输出，表明该元素是否属于这个递归集。有许多集合不是递归集。

递归可枚举集

如果对于集合A可以编一个程序P，输入域中任意元素x，若x∈A，则P的执行将终止并输出“是”，否则P 的执行不终止，就称A为递归可枚举集。A为递归可枚举集的充分必要条件是可以编一个程序枚举A的元素，即打印A的元素，使得对于 A中任意元素，只要时间足够长总会在打印纸上出现。递归集都是递归可枚举集，但有些递归可枚举集不是递归集。有许多集合不是递归可枚举集。

可判定性和半可判定性

判定问题是无穷多个同类个别问题的总称。例如，2是不是素数？6是不是素数？这些都是个别问题，把这类个别问题概括起来，就得到一个判定问题：任意给定的正整数是不是素数？这里的正整数集合称为该判定问题的域，给定域中的一个元素，判定问题就对应一个个别问题。对于一个判定问题，如果能够编出一个程序，以域中任意元素作为输入，执行该程序就能给出相应的个别问题的答案，就称该判定问题为可判定的。例如，“任意正整数是不是素数”这个问题就是可判定的。对于集合A，域中任意元素是否属于它的问题称为集合 A对应的判定问题。集合是递归集的充分必要条件为对应的判定问题是可判定的。因此，全体素数的集合是递归集。

对于一个判定问题，如果能够编出一个程序P，以域中任意元素作为输入，当相应的个别问题的解答是肯定的时候，P 的执行将终止并输出“是”，否则P 的执行不终止，就称该判定问题为半可判定的。可判定的问题总是半可判定的。集合是递归可枚举集的充分必要条件为对应的判定问题是半可判定的。

图灵在1936年证明，图灵机的停机问题是不可判定的，即不存在一个图灵机能够判定任意图灵机对于任意输入是否停机。图灵机的停机问题是半可判定的。图灵机的停机问题是很重要的，由它可以推出计算机科学、数学、逻辑学中的许多问题是不可判定的。

应用

可计算性理论是计算机科学的理论基础之一。早在30年代，图灵对存在通用图灵机的逻辑证明表明，制造出能编程序来作出任何计算的通用计算机是可能的，这影响了40年代出现的存储程序计算机（即诺伊曼型计算机）的设计思想。可计算性理论确定了哪些问题可能用计算机解决，哪些问题不可能用计算机解决。例如，图灵机的停机问题是不可判定的表明，不可能用一个单独的程序来判定任意程序的执行是否终止，避免了人们为编制这样的程序而无谓地浪费精力。

可计算性理论中的基本思想、概念和方法，被广泛应用于计算机科学的各个领域。建立数学模型的方法在计算机科学中被广泛采用。递归的思想被用于程序设计，产生了递归过程和递归数据结构，也影响了计算机的体系结构。λ演算被用于研究程序设计语言的语义，例如，表处理语言就以λ转换演算为理论基础。

参考书目

H.Rogers， Theory of Recursive Functions and Effective Computability， McGraw－Hill， New York，1967.F. Hennie，Introduction to Computability，Addison-Wesley， Masschusetts，1977.