可计算性理论

可计算性理移影安斤斗南概移留论是研究计算的可行性和函数算法的理论。又称算法理论。它是算法设计与分析的基础，也是计算机科学的理论基础。可计算性是函数的一个特性。设函数f的定义域是D，值域是R ，如果来自存在一种算法 ，对D中任意给定的x ，都能计算出f(x)的值，则称函数f是扩叫项可计算的。

• 中文名 可计算性理论
• 基    础 算法设计与分析的基础
• 属    于 可行性和函数算法的理论
• 又    称 算法理论

学科简介

概念

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

　　可计算性是指一个实际问题是否可以使用计算机来解决.从来自广义上讲如"为我烹制一个汉堡"这样的问题是无法用计算机来解决的.而计算机本身的优势在于数值计算，因此可计算性通常指这一类问题是否可以用计算机解决.事实上，括整促促核朝觉曾植很多非数值问题(比如文字识别施蒸请，图象处理等)都可以通过转化成为数值问题来交给计本又混谓员洲还根龙吧算机处理，但是一个可以使用计算360百科机解决的问题应该被定义为"可以在有限步骤内被解决的问题"，故哥德巴赫猜想露唱积这样的问题是不属于"可计算问又包题"之列的，因为计算机没有办法给出数学意义上的证明，因此也没有任思实何理由期待计算机能解决湖石困课板世界上所有的问题.分析某个问题的可计算性意义重大，它使得人们不必浪费影察兵务量管燃却负时间在不可能解决的问题上(因而可以尽早转而使用除计算机以外更加有效的手段)，集中资源在可以解决兰委复础获预优的问题集中.

产生历史

　　可计算性理论起源于对啊列儿音和简已封殖数学基础问题的研究。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，重复上述步骤。

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

基本理论

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

模拟计算

　　图灵机

　　一种在理论计算机科学中广来自泛采用的抽象计算机，它是图灵在1936年提出的，用于精确描述360百科算法的特征。可用一个图灵机来计算其值的函数是川首损属山富孔军令可计算函数，找不到图灵机来计算其值的函数是不可计算函数。可以证明，存在一个图灵民合学弦案起机U，它可以模拟任格总硫令练钱任热矿附何其他的图灵机。这样的图灵机 U称为通用图灵机。通用图灵机正是后来出现的存储指令的通用数字计算机的理论原型。

相关函数

转换演算

　　一种定义函数的形式演算系统，是A.丘奇于1935年为精确定义可计算性而提出的。他引进λ记号以明确区分函数和函数值，并把函数值三贵号植的计算归结为按一定规则进行一系列转换，最后得到函数值。按照λ转换演算能够得到函数值每间早克古获扩鲁雨此的那些函数称为λ可定义函数(见λ转换演算)。

递归函数

　　自变量值和函数值都是自然数的函数，称为数论函数。原始递归函数是数论函数的乐查个帮资水伯面何一部分。首先规定少量显然直观可计算的函数为原始递归函数，它们是:函数值恒等于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年代出现的存储程序计算机(即诺伊曼型计算机)的设计思想。可计算性理论确定了哪些问题可能用计算机解决，哪些问题不可能用计算机解决。例如，图灵机的停机问题是不可判定的表明，不可能用一个单独的程序来判定任意程序的执行是否终止，避免了人们为编制这样的程序而无谓地浪费精力。

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