可计算性理论

来自中文百科专业版
(重定向自算法理论
跳转至: 导航搜索

  可计算性理论(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论题得到了计算机科学界和数学界的公认。

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