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

套用计算性理论是计算机科学的理论基础之一。早在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 机( 部分) 可计算函式及其等价的概念作为可计算函式的严格定义。

在数学中，可计算性是函式的一个特性。定义域为D和范 围为R的函式f有一个确定的对应关係。通过这个 对应关係使R範围的单个元素f(x) (称为 值) 和D定义域的每个元素x(称为变元)联繫起来。 如果存在这样一种算法，给定D中的任意的x，就 能给出f(x)的值，那幺说函式f是可计算的。

在计算机中，可计算性（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) 计算理论( 算法设计与分析、複杂性理论、可计算性理论等)

( 3) 语言理论( 形式语言理论、自动机理论、形式语义学、计算语言学等)

( 4) 人工智慧( 知识工程、机器学习、模式识别、机器人等)

( 5) 逻辑基础( 数理逻辑、多值逻辑、模糊逻辑、模态逻辑、直觉主义逻辑、组合逻辑等)

( 6) 数据理论( 演绎资料库、关係资料库、面向对象资料库等)

( 7) 计算机数学( 符号计算、数学定理证明、计算几何等）

( 8) 并行计算( 网路计算、分散式并行计算、大规模并行计算、演化算法等)