可计算性理论

　　可计算性理论（computability theory），研究计算的可行性和函数算法的理论。又称算法理论。它是算法设计与分析的基础，也是计算机科学的理论基础。可计算性是函数的一个特性。设函数f的定义域是D，值域是R，如果存在一种算法，对D中任意给定的x，都能计算出f（x）的值，则称函数f是可计算的。

　　算法有不同的直观定义。一般认为，能机械地实现，并总能终止的有穷指令序列称为算法。也有把算法称为“有效过程”的，并把能机械地实现，但不一定终止的有穷指令序列称为一般过程。

　　在可计算性理论中，算法主要用于计算函数和判定谓词。具有定义域D的谓词P是D中元素的一种特性，D中每个元素或者具有这种特性，或者不具有这种特性。如果D中x具有特性P，就称P(x)真，否则称P（x）假。如果存在一个算法，对D中任何给的x，该算法总能给出P(x)是否真的明确回答，则称谓词P是可判定的。

　　函数的可计算性和谓词的可判定性是密切相关的概念。可以把每个谓词P与一个值域为｛0，1｝的函数f连系起来，P和f具有相同的定义域D。对D中任意x，如果P(x)为真，则f（x）＝1；如果P（x）为假，则f（x）＝0。显然，f是可计算的当且仅当P是可判定的。因此，只需讨论函数的可计算性即可。

　　在可计算性理论中讨论的函数都是整函数，它们的定义域和值域都是非负整数集。这种限制的合理性在于：其他类型的函数可以通过G!!!K0448_1del算术化，与整函数建立一一对应。

　　为了表示一个函数是可计算的，只需给出一个计算它的算法即可。按照上述定义，对于一个适当的算法，应该能构造一个执行算法指令的机器，这是一种抽象的计算机，算法就是该抽象计算机的程序。只有能由这种机器计算的函数，才可定义为可计算函数。通常用于这种目的的抽象计算机就是所谓的图灵机。因为图灵机有精确的定义，所以可计算出数的概念就变成了一个精确的数学概念。

　　上述定义可计算函数的方法称为抽象机方法。在可计算性理论中，另一种定义可计算性的方法是函数方法，这种方法的基本出发点是认为可计算函数就是能行可构造函数。所谓“能行性”是指存在切实可行的构造方法，并能在有限步骤内构造出来。基于这种方法的研究在可计算性理论中构成了递归函数论，其主要成果是论证：能行可构造函数就是一般递归函数。

　　可计算性理论中有一基本论题称为Church-Turing论题，它断言图灵机可计算函数类就是直观可计算的函数类。因为直观可计算函数并不是精确的数学概念，所以Church-Turi-ng论题不能用数学方法加以证明。但是有许多令人信服的论据支持这个论题，人们后来提出许多不同的计算模型都被证明与图灵机等价，即各种模型所定义的可计算函数类都是图灵机可计算函数类。这表明图灵机及其他等价模型确实合理地定义了可计算性。因此，Church-Turing论题得到了计算机科学界和数学界的公认。

　　给定可计算函数的精确定义之后，既能证明一些具体函数是可计算的，也能证明某些函数是不可计算的。