可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。可计算理论的研究对象有三个 ： ( 1) 判定问题； ( 2) 可计算函数；( 3) 计算复杂性。 [1]
- 中文名
- 可计算性理论
- 外文名
- computability theory
- 学 科
- 计算机、数学
- 又 称
- 算法理论
- 基 础
- 算法设计与分析的基础
- 应用领域
- 并行计算、人工智能
可计算性理论，亦称算法理论或能行性理论，计算机科学的理论基础之一。是研究计算的一般性质的数学理论。可计算性理论通过建立计算的数学模型 [2]，精确区分哪些是可计算的，哪些是不可计算的。计算的过程是执行算法的过程。可计算性理论的重要课题之一，是将算法这一直观概念精确化。算法概念精确化的途径很多，其中之一是通过定义抽象计算机，把算法看作抽象计算机的程序。通常把那些存在算法计算其值的函数叫做可计算函数。因此，可计算函数的精确定义为：能够在抽象计算机上编出程序计算其值的函数。这样就可以讨论哪些函数是可计算的，哪些函数是不可计算的。
应用计算性理论是计算机科学的理论基础之一。早在30年代，图灵对存在通用图灵机的逻辑证明表明，制造出能编程序来作出任何计算的通用计算机是可能的，这影响了40年代出现的存储程序的计算机（即冯诺依曼型计算机）的设计思想。可计算性理论确定了哪些问题可能用计算机解决，哪些问题是不可能用计算机解决的。
可计算性理论中的基本思想、概念和方法，被广泛用用与计算机科学的各个领域。建立数学模型的方法在计算机科学中被广泛采用。递归的思想被用于程序设计，产生了递归过程和递归数据结构，也影响了计算机的体系结构。
可计算理论的计算模型主要包括: ( 1)Turing 机； ( 2) 递归函数 ； ( 3) λ演算 ；( 4) POST 系统；( 5) 正则算法。 第一个模型是程序设计语言 S，该程序语言定义了 1) 变量；2) 标号； 3)语句； 4) 指令；5) 程序； 6) 状态;；7) 快相； 8) 后继； 9)计算。 设f(x 1 , x 2 , …, x n )是一个部分函数， 如果存在程序 S 计算 f ，则称 f 是部分可计算函数。 从而, 一个函数是否是可计算的,只需要判断是否可以构造对应的程序 S 即可。可计算函数经过原始递归运算还是可计算函数。 给出了通用程序的概念， 任意程序和输入x 1 , x 2 , …( y = # ( ) ), 存在通用程序以 x 1 , x 2 , …, x n 和y 作为输入 ，计算结果恰好等于程序的计算结果。“ 参数定理” 、“ 递归定理”提供了判断一个函数是否可计算的方法，从基本的可计算函数推道出其他函数是否可计算，而不需要构造程序证明其可计算 。
另一个计算模型是语言 hn, 该模型为字符串运算设计的。 设字母表 A 中有 n 个符号, 如果 A上的m 元部分函数能用程序计算, 则这个函数是可计算的。 Post-Turing 语言也是面向字符串运算的程序设计语言, 要处理的字符串存在一条带上。Post-Turing 程序ζ计算的 A 上m 元部分函数定义为对任意给定的输入 x 1 , x 2 , …, x n ∈A, 从初始带格局开始, 如果计算最终停止, 则部分函数等于计算停止时从带的内容中删除不属于 A 的符号后得到的字符串; 如果计算不停止, 则部分函数无定义。 图灵机 μ由六部分组成：( 1) 有穷状态集,，( 2) 字母表，( 3) 动作函数， ( 4)输入字母表，( 5) 空白符 B， ( 6) 初始态 q1。 上述计算模型等价性的证明， 主要采用将一种模型用另一种模型表示的方法证明。 可计算理论中，计算模型很多, 如有穷自动机, 正则算法在本质上都与图灵机相似。 Church-Turing 论题指出： 通常说的能行可计算函数等同于部分递归函数, 也等同于Turing 机计算的部分函数； 也就是说， Turing 机可计算性与递归性是等价的。 因此, 把递归函数、Turing 机( 部分) 可计算函数及其等价的概念作为可计算函数的严格定义。 [1]
在数学中，可计算性是函数的一个特性。定义域为D和范 围为R的函数f有一个确定的对应关系。通过这个 对应关系使R范围的单个元素f(x) (称为 值) 和D定义域的每个元素x(称为变元)联系起来。 如果存在这样一种算法，给定D中的任意的x，就 能给出f(x)的值，那么说函数f是可计算的。 [3]
在计算机中，可计算性（calculability）是指一个实际问题是否可以使用计算机来解决．从广义上讲如“为我烹制一个汉堡”这样的问题是无法用计算机来解决的（至少在目前）。而计算机本身的优势在于数值计算，因此可计算性通常指这一类问题是否可以用计算机解决．事实上，很多非数值问题（比如文字识别，图象处理等）都可以通过转化成为数值问题来交给计算机处理，但是一个可以使用计算机解决的问题应该被定义为“可以在有限步骤内被解决的问题”，故哥德巴赫猜想这样的问题是不属于“可计算问题”之列的，因为计算机没有办法给出数学意义上的证明，因此也没有任何理由期待计算机能解决世界上所有的问题。分析某个问题的可计算性意义重大，它使得人们不必浪费时间在不可能解决的问题上（因而可以尽早转而使用除计算机以外更加有效的手段），集中资源在可以解决的问题上。
这样我们可以定义可计算性等级：所有的语言的集合，记为All；递归可枚举语言，即可以被图灵机枚举的语言的集合，记为RE；递归语言，即可以被图灵机决定的语言的集合，记为R。可见，即形成可计算性等级。那么产生相关的问题即是两个包含关系是不是严格的，即是否有在All而不在RE中的语言，以及在RE而不在R中的语言。阿兰·图灵在1930年代的工作表明这两个包含关系都是不严格的，即可以证明存在语言L_d，是不能被图灵机所枚举的，以及存在语言L_u，是不能被图灵机所决定的。证明的主要思想是对角线法。
停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：给定一个程序P和输入w，程序P在输入w下是否能够最终停止。
不可解度的概念定义了不可解的集合之间的相对计算难度。例如，不可解的停机问题显然比任何可解的集合都要难，然而同样不可解的“元停机问题”（即所有具备停机问题的预言机的停机问题）却要难过停机问题，因为具备元停机问题的预言机可以解出停机问题，然而具备停机问题的预言机却不能解出元停机问题。
一种定义函数的形式演算系统，是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不终止。
由于可计算理论的建立，才出现了现代的计算机系统，此学科无疑是计算机科学的基础。 计算机科学分为计算机理论和计算机应用。 计算机基础理论包含以下几部分：
( 1) 程序理论( 程序逻辑、程序正确性验证、形式开发方法等)
( 2) 计算理论( 算法设计与分析、复杂性理论、可计算性理论等)
( 4) 人工智能( 知识工程、机器学习、模式识别、机器人等)
( 7) 计算机数学( 符号计算、数学定理证明、计算几何等）
( 8) 并行计算( 网络计算、分布式并行计算、大规模并行计算、演化算法等) [1]
